{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T23:24:43Z","timestamp":1770247483606,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2318970"],"award-info":[{"award-number":["2318970"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,1,7]]},"abstract":"<jats:p>\n                    <jats:italic toggle=\"yes\">Reductions<\/jats:italic>\n                    combine collections of input values with an associative and often commutative operator to produce collections of results. When the\n                    <jats:italic toggle=\"yes\">same<\/jats:italic>\n                    input value contributes to\n                    <jats:italic toggle=\"yes\">multiple<\/jats:italic>\n                    outputs, there is an opportunity to\n                    <jats:italic toggle=\"yes\">reuse<\/jats:italic>\n                    partial results, enabling\n                    <jats:italic toggle=\"yes\">reduction simplification<\/jats:italic>\n                    . Simplification often produces a program with lower asymptotic complexity. Typical compiler optimizations yield, at best, a constant fold speedup, but a complexity improvement from, say, cubic to quadratic complexity yields unbounded speedup for sufficiently large problems. It is well known that reductions in polyhedral programs may be simplified\n                    <jats:italic toggle=\"yes\">automatically<\/jats:italic>\n                    , but previous methods cannot exploit all available reuse. This paper resolves this long-standing open problem, thereby attaining minimal asymptotic complexity in the simplified program. We propose extensions to prior work on simplification to support any independent commutative reduction. At the heart of our approach is piece-wise simplification, the notion that we can split an arbitrary reduction into pieces and then independently simplify each piece. However, the difficulty of using such piece-wise transformations is that they typically involve an infinite number of choices. We give constructive proofs to deal with this and select a finite number of pieces for simplification.\n                  <\/jats:p>","DOI":"10.1145\/3704839","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:48:42Z","timestamp":1736401722000},"page":"67-94","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximal Simplification of Polyhedral Reductions"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-3298-5282","authenticated-orcid":false,"given":"Louis","family":"Narmour","sequence":"first","affiliation":[{"name":"Colorado State University, Fort Collins, USA"},{"name":"University of Rennes, Rennes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5737-6178","authenticated-orcid":false,"given":"Tomofumi","family":"Yuki","sequence":"additional","affiliation":[{"name":"Unaffiliated, Yokohama, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4246-6066","authenticated-orcid":false,"given":"Sanjay","family":"Rajopadhye","sequence":"additional","affiliation":[{"name":"Colorado State University, Fort Collins, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,1,9]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"243","volume-title":"Convex and Discrete Geometry,","author":"Gruber Peter M","year":"2007","unstructured":"2007. Convex Polytopes. In Convex and Discrete Geometry, Peter M. Gruber (Ed.). Springer, Berlin, Heidelberg, 243\u2013351. https:\/\/doi.org\/10.1007\/978-3-540-71133-9_3 10.1007\/978-3-540-71133-9_3"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.825794"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155102"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Uday Bondhugulan Vinayaka Bandishti Albert Cohen Guillain Potron and Nicolas Vasilache. 2014. Tiling and optimizing time-iterated computations over periodic domains. In 2014 23rd International Conference on Parallel Architecture and Compilation Techniques (PACT). 39\u201350. https:\/\/doi.org\/10.1145\/2628071.2628106 10.1145\/2628071.2628106","DOI":"10.1145\/2628071.2628106"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkv1479"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M112720X"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","unstructured":"Hamidreza Chitsaz Rolf Backofen and S.Cenk Sahinalp. 2009. biRNA: Fast RNA-RNA Binding Sites Prediction. In Workshop on Algorithms in Bioinformatics (WABI) (LNBI) Vol. 5724 S.L. Salzberg and T. Warnow (Eds.). Springer-Verlag Berlin Heidelberg 25\u201336.","DOI":"10.1007\/978-3-642-04241-6_3"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133898"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/49418"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01379404"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1355838200992161"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/773453.808186"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/965145.801264"},{"key":"e_1_3_2_15_2","first-page":"30","volume-title":"Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL \u201806)","author":"Rajopadhye S","year":"2006","unstructured":"Gautam and S. Rajopadhye. 2006. Simplifying reductions. In Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL \u201806). Association for Computing Machinery, New York, NY, USA, 30\u201341. https:\/\/doi.org\/10.1145\/1111037.1111041 10.1145\/1111037.1111041"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007516818651"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz375"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73588"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3607096"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/534785"},{"key":"e_1_3_2_22_2","unstructured":"HERVE LE VERGE. 1992. Un environnement de transformations de programmes pour la synthese d'architectures regulieres. These de doctorat. Rennes 1. https:\/\/theses.fr\/1992REN10139"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/132970.2812991"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57208-2_28"},{"key":"e_1_3_2_25_2","first-page":"434","volume-title":"International Conference on Parallel Processing, ICPP'85.","author":"Li Guo-Jie","year":"1985","unstructured":"Guo-Jie Li and Benjamin W. Wah. 1985. Systolic Processing for Dynamic Programming Problems. In International Conference on Parallel Processing, ICPP'85. IEEE Computer Society Press, 434\u2013441."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025117523902"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-6-26"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-016-0070-z"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/15.6.440"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sbi.2006.05.010"},{"key":"e_1_3_2_31_2","unstructured":"Christophe Mauras. 1989. Alpha : un langage equationnel pour la conception et la programmation d'architectures paralleles synchrones. These de doctorat.Rennes 1. https:\/\/theses.fr\/1989REN10116"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-543457-7.50059-0"},{"key":"e_1_3_2_33_2","unstructured":"Louis Narmour. 2024. MaximalSimplification of Polyhedral Reductions. https:\/\/doi.org\/10.5281\/zenodo.13943008 10.5281\/zenodo.13943008"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.77.11.6309"},{"key":"e_1_3_2_35_2","unstructured":"OpenMP Architecture Review Board. 2021. {OpenMP} Application Program Interface Version 5.2. 124\u2013140. https:\/\/www.openmp.org\/wp-content\/uploads\/OpenMP-API-Specification-5-2.pdf"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/534975"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.033315"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125848"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02477176"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01558666"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/VLSISP.1992.641069"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/DMCC.1990.556321"},{"key":"e_1_3_2_43_2","unstructured":"Harenome Razanajato Vincent Loechner and Cedric Bastoul. 2017. Splitting Polyhedra to Generate More Efficient Code. https:\/\/inria.hal.science\/hal-01505764"},{"key":"e_1_3_2_44_2","unstructured":"Gerald Sabin and P. Sadayappan. 2021. Tensor Contraction and Operation Minimization forExtreme Scale Computational Chemistry. Technical Report DOE-RNET-20616. RNET Technologies. https:\/\/www.osti.gov\/biblio\/1782724"},{"key":"e_1_3_2_45_2","volume-title":"Automatic blocking of nested loops","author":"Schreiber Robert","year":"1990","unstructured":"Robert Schreiber and Jack J. Dongarra. 1990. Automatic blocking of nested loops. Technical Report NASA-CR-188874. RIACS. https:\/\/ntrs.nasa.gov\/citations\/19910023530 Issue: NASA-CR-188874 NTRS Author Affiliations: Research Inst. for Advanced Computer Science, Tennessee Univ. NTRS Document ID: 19910023530 NTRS Research Center: Legacy CDMS (CDMS)."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531015"},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","unstructured":"Nicolas Vasilache Albert Cohen and Louis-Noel Pouchet. 2007. Automatic Correction of Loop Transformations. In 16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007). 292\u2013304. https:\/\/doi.org\/10.1109\/PACT.2007.4336220 10.1109\/PACT.2007.4336220","DOI":"10.1109\/PACT.2007.4336220"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15582-6_49"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.97902"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/113445.113449"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/645818.669220"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/37\/17\/005"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434301"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37658-0_2"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.21596"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/9.1.133"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704839","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3704839","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T10:18:59Z","timestamp":1770200339000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704839"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,7]]},"references-count":55,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2025,1,7]]}},"alternative-id":["10.1145\/3704839"],"URL":"https:\/\/doi.org\/10.1145\/3704839","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,7]]},"assertion":[{"value":"2024-07-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}