Maximal Simplification of Polyhedral Reductions
summary
Proposes an algorithm that always attains minimal asymptotic complexity for polyhedral commutative reductions by splitting domains and simplifying each piece, turning many quadratic reductions into linear-time code; gives constructive proofs that a finite set of pieces suffices even when naive splits are unbounded; implements a proof-of-concept artifact (Java 11, runs on Linux/Mac with bash) that transforms parametric loop nests into simplified code and handles higher-dimensional simplices via piece-wise simplification.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:42Simplification in polyhedral reductions
- 3:07Reductions in computing
- 4:50Polyhedral model
- 7:18Limitations of prior techniques
- 8:00Redundancy and reuse spaces
- 9:27Geometric interpretation
- 12:59Residual computations
- 14:45Non-invertible operators
- 15:26Splitting domains
- 17:35Higher-dimensional cases
- 19:01Recursive code generation
- 20:03Artifact demo and future work
- 21:05Q&A
related talks
24mSimplifying Multiple-Statement Reductions with the Polyhedral Model
23mVerified Code Generation for the Polyhedral Model
55mNon-commutative Computation
55mInequalities and Reductions for Nonzero Kronecker Coefficients
23mLet Generalization, Polymorphic Recursion, and Variable Minimization in Boolean-Kinded(…)
18mCylindrical Algebraic Decomposition in Coq/Rocq
23mVerifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach
17mSatisfiability Algorithms Based on Concentrated Shrinkage