Maximal Simplification of Polyhedral Reductions

This conference talk from POPL 2025 presents groundbreaking research on achieving maximal simplification of polyhedral reductions in program optimization. Learn how researchers Louis Narmour, Tomofumi Yuki, and Sanjay Rajopadhye tackle a long-standing open problem in polyhedral compilation by introducing piece-wise simplification techniques that can transform program complexity from higher orders (like cubic) to lower ones (like quadratic), yielding unbounded speedups for large problems. Discover how their approach extends previous work to support any independent commutative reduction, constructively proving how to select a finite number of pieces for simplification despite seemingly infinite choices. The 22-minute presentation includes functional artifacts that have been evaluated and are available for reference, along with supplementary materials accessible via DOI links. Particularly valuable for those interested in polyhedral compilation, algorithmic complexity optimization, and advanced program transformation techniques.