{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T17:24:56Z","timestamp":1787592296723,"version":"build-2736575974"},"reference-count":104,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:00:00Z","timestamp":1744156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Intel and NSF PPoSS","award":["CCF-2217064"],"award-info":[{"award-number":["CCF-2217064"]}]},{"name":"DARPA PROWESS Award","award":["HR0011-23-C-0101"],"award-info":[{"award-number":["HR0011-23-C-0101"]}]},{"name":"NSF SHF","award":["CCF-2107244"],"award-info":[{"award-number":["CCF-2107244"]}]},{"name":"DoE PSAAP Center","award":["DE-NA0003965"],"award-info":[{"award-number":["DE-NA0003965"]}]},{"name":"DARPA SBIR","award":["HR001123C0139"],"award-info":[{"award-number":["HR001123C0139"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,4,9]]},"abstract":"<jats:p>From FORTRAN to NumPy, tensors have revolutionized how we express computation. However, tensors in these, and almost all prominent systems, can only handle dense rectilinear integer grids. Real world tensors often contain underlying structure, such as sparsity, runs of repeated values, or symmetry. Support for structured data is fragmented and incomplete. Existing frameworks limit the tensor structures and program control flow they support to better simplify the problem.<\/jats:p>\n                  <jats:p>\n                    In this work, we propose a new programming language, Finch, which supports\n                    <jats:italic toggle=\"yes\">both<\/jats:italic>\n                    flexible control flow and diverse data structures. Finch facilitates a programming model which resolves the challenges of computing over structured tensors by combining control flow and data structures into a common representation where they can be co-optimized. Finch automatically specializes control flow to data so that performance engineers can focus on experimenting with many algorithms. Finch supports a familiar programming language of loops, statements, ifs, breaks, etc., over a wide variety of tensor structures, such as sparsity, run-length-encoding, symmetry, triangles, padding, or blocks. Finch reliably utilizes the key properties of structure, such as structural zeros, repeated values, or clustered non-zeros. We show that this leads to dramatic speedups in operations such as SpMV and SpGEMM, image processing, and graph analytics.\n                  <\/jats:p>","DOI":"10.1145\/3720473","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T13:48:26Z","timestamp":1744206506000},"page":"1042-1072","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Finch: Sparse and Structured Tensor Programming with Control Flow"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4963-0869","authenticated-orcid":false,"given":"Willow","family":"Ahrens","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7578-7683","authenticated-orcid":false,"given":"Teodoro Fields","family":"Collin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7715-1322","authenticated-orcid":false,"given":"Radha","family":"Patel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2267-3276","authenticated-orcid":false,"given":"Kyle","family":"Deeds","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9069-8374","authenticated-orcid":false,"given":"Changwan","family":"Hong","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7231-7643","authenticated-orcid":false,"given":"Saman","family":"Amarasinghe","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,9]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2024. Developer Reference for Intel\u00ae oneAPI Math Kernel Library for Fortran. (April 2024). https:\/\/www.intel.com\/content\/www\/us\/en\/docs\/onemkl\/developer-reference-fortran\/2024-0\/overview.html"},{"key":"e_1_3_2_3_2","first-page":"265","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Abadi Mart\u00edn","year":"2016","unstructured":"Mart\u00edn Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2016. TensorFlow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). 265\u2013283. https:\/\/www.usenix.org\/system\/files\/conference\/osdi16\/osdi16-abadi.pdf"},{"key":"e_1_3_2_4_2","unstructured":"Hameer Abbasi. 2023. Plans for new sparse compilation backend \u00b7 pydata\/sparse \u00b7 Discussion #618. https:\/\/github.com\/pydata\/sparse\/discussions\/618"},{"key":"e_1_3_2_5_2","volume-title":"Structure and Interpretation of Computer Programs","author":"Abelson Harold","year":"1996","unstructured":"Harold Abelson and Gerald Jay Sussman. 1996. Structure and Interpretation of Computer Programs. The MIT Press. https:\/\/library.oapen.org\/handle\/20.500.12657\/26092"},{"key":"e_1_3_2_6_2","unstructured":"Shrirang Abhyankar Getnet Betrie Daniel A Maldonado Lois C McInnes Barry Smith and Hong Zhang.[n. d.]. PETSc DMNetwork: A Scalable Network PDE-Based Multiphysics Simulator.([n. d)]."},{"key":"e_1_3_2_7_2","unstructured":"Willow Ahrens and Erik G Boman. 2021. On Optimal Partitioning For Sparse Matrices In Variable Block Row Format.https:\/\/doi.org\/10.48550\/arXiv.2005.12414 arXiv:2005.12414 [cs]."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3579990.3580020"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523442"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"Willow Ahrens Radha Patel Teodoro Fields. Collin Kyle Deeds Changwan Hong and Saman Amarasinghe. 2025. Finch: Sparse and Structured Tensor Programming with Control Flow: The Artifact. https:\/\/doi.org\/10.5281\/zenodo.14735207","DOI":"10.1145\/3720473"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/323215"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1455567.1455599"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2019.8661197"},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","unstructured":"S. Balay S. Abhyankar Mark F Adams J. Brown P. Brune K. Buschelman L. Dalcin A. Dener V. Eijkhout W. Gropp and others. 2020. PETSc Users Manual (Rev.3.13). Technical Report. Argonne National Lab.(ANL) Argonne IL USA(United States.","DOI":"10.2172\/1814627"},{"key":"e_1_3_2_15_2","first-page":"7:3.7","article-title":"An experimental investigation of set intersection algorithms for text searching","volume":"14","author":"Barbay J\u00e9r\u00e9mie","year":"2010","unstructured":"J\u00e9r\u00e9mie Barbay, Alejandro L\u00f3pez-Ortiz, Tyler Lu, and Alejandro Salinger. 2010. An experimental investigation of set intersection algorithms for text searching. ACM Journal of Experimental Algorithmics 14 (Jan. 2010), 7:3.7\u20137:3.24. https:\/\/doi.org\/10.1145\/1498698.1564507","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-020-00399-2"},{"key":"e_1_3_2_17_2","first-page":"1","author":"Beamer Scott","year":"2012","unstructured":"Scott Beamer, Krste Asanovic, and David Patterson. 2012. Direction-optimizing breadth-first search. In SC'12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. IEEE, 1\u201310.","journal-title":"SC'12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1345448.1345465"},{"issue":"2","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2892632","article-title":"Ebb: A DSL for physical simulation on CPUs and GPUs","volume":"35","author":"Bernstein Gilbert Louis.","year":"2016","unstructured":"Gilbert Louis. Bernstein,Chinmayee Shah,Crystal Lemire,Zachary Devito,Matthew Fisher,Philip Levis,andPat Hanrahan. 2016. Ebb: A DSL for physical simulation on CPUs and GPUs. ACM Transactions on Graphics (TOG) 35, 2 (2016), 1\u201312.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Jeff Bezanson Stefan Karpinski Viral B Shah andAlan Edelman. 2012. Julia: A Fast Dynamic Language for Technical Computing. arXiv:1209.5145 [cs] (Sept. 2012).. https:\/\/doi.org\/10.48550\/arXiv.1209.514510.48550\/arXiv.1209.5145.","DOI":"10.48550\/arXiv.1209.5145."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3544559"},{"issue":"1","key":"e_1_3_2_22_2","first-page":"21","article-title":"Vectorwise: Beyond column stores","volume":"35","author":"Boncz PA","year":"2012","unstructured":"PA Boncz and M. Zukowski. 2012. Vectorwise: Beyond column stores. IEEE Data Engineering Bulletin 35, 1 (2012), 21\u201327.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"issue":"2","key":"e_1_3_2_24_2","article-title":"OpenCV","volume":"3","author":"Bradski Gary","year":"2000","unstructured":"Gary Bradski,Adrian Kaehler, and others. 2000. OpenCV. Dr. Dobb\u2019s Journal of Software Tools 3, 2 (2000).","journal-title":"Dr. Dobb\u2019s Journal of Software Tools"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2017.117"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.2.023068"},{"key":"e_1_3_2_27_2","volume-title":"USC Computer Science Technical Report","author":"Chen Chun","year":"2008","unstructured":"Chun Chen, Jacqueline Chame, and Mary Hall. 2008. A framework for composing high-level loop transformations. USC Computer Science Technical Report Technical Report (2008)."},{"key":"e_1_3_2_28_2","first-page":"578","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Chen Tianqi","year":"2018","unstructured":"Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), 578\u2013594. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/chen"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3563338"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_3_2_31_2","first-page":"4690","volume-title":"International Conference on Machine Learning","author":"Dao Tri","year":"2022","unstructured":"Tri Dao, Beidi Chen, Nimit S Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher R\u00e9. 2022. Monarch: Expressive structured matrices for efficient and accurate training. In International Conference on Machine Learning, PMLR, 4690\u20134721."},{"key":"e_1_3_2_32_2","volume-title":"A Guide to the SQL Standard","author":"Date Chris J","year":"1989","unstructured":"Chris J Date. 1989. A Guide to the SQL Standard. Addison-Wesley Longman Publishing Co., Inc.."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3524059.3532386"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO53902.2022.9741282"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.05.138"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185540"},{"key":"e_1_3_2_38_2","unstructured":"Pratik Fegade. 2022. The CoRa Tensor Compiler: Compilation for Ragged Tensors with Minimal Padding. https:\/\/doi.org\/10.5281\/zenodo.6326456"},{"key":"e_1_3_2_39_2","first-page":"721","volume-title":"Proceedings of Machine Learning and Systems","author":"Fegade Pratik","year":"2022","unstructured":"Pratik Fegade, Tianqi Chen, Phillip Gibbons, and Todd Mowry. 2022. The CoRa Tensor Compiler: Compilation for Ragged Tensors with Minimal Padding. In Proceedings of Machine Learning and Systems, Vol. 4, 721-747.https:\/\/proceedings.mlsys.org\/paper_files\/paper\/2022\/file\/afe8a4577080504b8bec07bbe4b2b9cc-paper.pdf"},{"key":"e_1_3_2_40_2","first-page":"118","volume-title":"Hypermedia Image Processing Reference","author":"Fisher Robert","year":"1996","unstructured":"Robert Fisher, Simon Perkins, Ashley Walker, and Erik Wolfart. 1996. Hypermedia Image Processing Reference. John Wiley & Sons Ltd, 118-130."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03034-5_18"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2873289"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3622804"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053907"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/1076432"},{"issue":"4","key":"e_1_3_2_46_2","article-title":"Polly-performing polyhedral optimizations on a low-level intermediate representation","volume":"22","author":"Grosser Tobias","year":"2012","unstructured":"Tobias Grosser, Armin Groesslinger, and Christian Lengauer. 2012. Polly-performing polyhedral optimizations on a low-level intermediate representation. Parallel Processing Letters 22, 4(2012),1250010.","journal-title":"Parallel Processing Letters"},{"key":"e_1_3_2_47_2","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob and others. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3408974"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485505"},{"key":"e_1_3_2_51_2","doi-asserted-by":"crossref","unstructured":"Olivia Hsu Maxwell Strange Ritvik Sharma Jaeyeon Won Kunle Olukotun Joel S. Emer Mark A. Horowitz and Fredrik Kj\u00f8lstad. 2023. The Sparse Abstract Machine. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems Volume 3 (ASPLOS 2023). Association for Computing Machinery New York NY USA 710-726. https:\/\/doi.org\/10.1145\/3582016.3582051","DOI":"10.1145\/3582016.3582051"},{"issue":"6","key":"e_1_3_2_52_2","first-page":"201:1","article-title":"Taichi: a language for high-performance computation on spatially sparse data structures","volume":"38","author":"Anderson Luke","year":"2019","unstructured":"Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Ragan-Kelley, and Fr\u00e9do Durand. 2019. Taichi: a language for high-performance computation on spatially sparse data structures. ACM Transactions on Graphics 38, 6 (Nov. 2019), 201:1-201:16. https:\/\/doi.org\/10.1145\/3355089.3356506","journal-title":"ACM Transactions on Graphics"},{"key":"e_1_3_2_53_2","doi-asserted-by":"crossref","unstructured":"Dylan Hutchison Bill Howe and Dan Suciu. 2017. LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation. In Proceedings of the 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond (BeyondMR\u201917). Association for Computing Machinery New York NY USA 1-10. https:\/\/doi.org\/10.1145\/3070607","DOI":"10.1145\/3070607.3070608"},{"key":"e_1_3_2_54_2","doi-asserted-by":"crossref","unstructured":"Yuka Ikarashi Gilbert Louis Bernstein Alex Reinking Hasan Genc and Jonathan Ragan-Kelley. 2022. Exocompilation for productive programming of hardware accelerators. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery New York NY USA 703-718. https:\/\/doi.org\/10.1145\/3519939.3523446","DOI":"10.1145\/3519939.3523446"},{"key":"e_1_3_2_55_2","doi-asserted-by":"crossref","unstructured":"Eun-Jin Im and Katherine Yelick. 2001. Optimizing Sparse Matrix Computations for Register Reuse in SPARSITY. In Computational Science - ICCS 2001 (Lecture Notes in Computer Science). Springer Berlin Heidelberg 127-136. https:\/\/doi.org\/10.1007\/3-540-45545-0_22","DOI":"10.1007\/3-540-45545-0_22"},{"key":"e_1_3_2_56_2","doi-asserted-by":"crossref","unstructured":"U Kang Hanghang Tong Jimeng Sun Ching-Yung Lin and Christos Faloutsos. 2011. GBASE: a scalable and general graph management system. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge Discovery and data mining 1091-1099.","DOI":"10.1145\/2020408.2020580"},{"key":"e_1_3_2_57_2","doi-asserted-by":"crossref","unstructured":"Jeremy Kepner Peter Aaltonen David Bader Aydin Bulu\u00e7 Franz Franchetti John Gilbert Dylan Hutchison Manoj Kumar Andrew Lumsdaine Henning Meyerhenke Scott McMillan Carl Yang John D. Owens Marcin Zalewski Timothy Mattson and Jose Moreira. 2016. Mathematical foundations of the GraphBLAS. In 2016 IEEE High Performance Extreme Computing Conference (HPEC) 1-9. https:\/\/doi.org\/10.1109\/HPEC.2016.7761646","DOI":"10.1109\/HPEC.2016.7761646"},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","unstructured":"Fredrik Kjolstad Willow Ahrens Shoaib Kamil and Saman Amarasinghe. 2019. Tensor Algebra Compilation with Workspaces. In 2019 IEEE\/ACM International Symposium on Code Generation and Optimization (CGO) 180-192. https:\/\/doi.org\/10.1109\/CGO.2019.8661185","DOI":"10.1109\/CGO.2019.8661185"},{"issue":"1","key":"e_1_3_2_59_2","first-page":"29","article-title":"The Tensor Algebra Compiler","volume":"77","author":"Kamil Shoaib","year":"2017","unstructured":"Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017. The Tensor Algebra Compiler. Proc. ACM Program. Lang. 1, OOPSLA (Oct. 2017), 77:1-77:29. https:\/\/doi.org\/10.1145\/3133901","journal-title":"Proc. ACM Program. Lang"},{"key":"e_1_3_2_60_2","unstructured":"Donald E. Knuth. 1997. The Art of Computer Programming: Fundamental Algorithms Volume 1. Addison-Wesley Professional. Google-Books-ID: x9AsAwAAQBAJ."},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0002751"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aab3050"},{"key":"e_1_3_2_63_2","doi-asserted-by":"crossref","unstructured":"Daniel Langr and Pavel Tvrd\u00edk. 2016. Evaluation Criteria for Sparse Matrix Storage Formats. IEEE Transactions on Parallel and Distributed Systems 27 2 (Feb. 2016) 428-440. https:\/\/doi.org\/10.1109\/TPDS.2015.2401575.","DOI":"10.1109\/TPDS.2015.2401575"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.726791"},{"key":"e_1_3_2_65_2","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Kevin J. Lang and Michael Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th International Conference on World Wide Web (WWW \u201910). Association for Computing Machinery New York NY USA 631-640. https:\/\/doi.org\/10.1145\/1772690.1772755.","DOI":"10.1145\/1772690.1772755"},{"key":"e_1_3_2_66_2","first-page":"55:1","article-title":"Verified tensor-program optimization via high-level scheduling rewrites","author":"Liu Amanda","year":"2022","unstructured":"Amanda Liu, Gilbert Louis. Bernstein, Adam Chlipala, and Jonathan Ragan-Kelley. 2022. Verified tensor-program optimization via high-level scheduling rewrites. Proceedings of the ACM on Programming Languages 6, POPL (Jan. 2022), 55:1-55:28. https:\/\/doi.org\/10.1145\/3498717.","journal-title":"Proceedings of the ACM on Programming Languages 6"},{"key":"e_1_3_2_67_2","doi-asserted-by":"crossref","unstructured":"Weifeng Liu and Brian Vinter. 2015. CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication. In Proceedings of the 29th ACM International Conference on Supercomputing (ICS \u201915). Association for Computing Machinery New York NY USA 339-350. https:\/\/doi.org\/10.1145\/2751205.2751209.","DOI":"10.1145\/2751205.2751209"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3277006.3277013"},{"key":"e_1_3_2_69_2","doi-asserted-by":"crossref","unstructured":"Tim Mattson Timothy A. Davis Manoj Kumar Aydin Buluc Scott McMillan Jos\u00e9 Moreira and Carl Yang. 2019. LAGraph: A community effort to collect graph algorithms built on top of the GraphBLAS. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE 276-284.","DOI":"10.1109\/IPDPSW.2019.00053"},{"key":"e_1_3_2_70_2","doi-asserted-by":"crossref","unstructured":"Julian McAuley and Jure Leskovec. 2013. Hidden factors and hidden topics: understanding rating dimensions with review text. In Proceedings of the 7th ACM conference on Recommender systems (RecSys \u201913). Association for Computing Machinery New York NY USA 165-172. https:\/\/doi.org\/10.1145\/2507157.2507163","DOI":"10.1145\/2507157.2507163"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO57630.2024.10444817"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3386331"},{"issue":"3","key":"e_1_3_2_73_2","first-page":"16:1","article-title":"Worst-case Optimal Join Algorithms","volume":"65","author":"Ngo Hung Q.","year":"2018","unstructured":"Hung Q. Ngo, Ely Porat, Christopher R\u00e9, and Atri Rudra. 2018. Worst-case Optimal Join Algorithms. ACM Transactions on Database Systems 65, 3 (March 2018), 16:1\u201316:40. https:\/\/doi.org\/10.1145\/3180143","journal-title":"ACM Transactions on Database Systems"},{"key":"e_1_3_2_74_2","doi-asserted-by":"crossref","unstructured":"Dianne P. O'Leary. 2009. Scientific Computing with Case Studies. SIAM.","DOI":"10.1137\/9780898717723"},{"key":"e_1_3_2_75_2","unstructured":"Adam Paszke Sam Gross Francisco Massa Adam Lerer James Bradbury Gregory Chanan Trevor Killeen Zeming Lin Natalia Gimelshein Luca Antiga Alban Desmaison Andreas Kopf Edward Yang Zachary DeVito Martin Raison Alykhan Tejani Sasank Chilamkurthy Benoit Steiner Lu Fang Junjie Bai and Soumith Chintala. 2019. PyTorch: An Imperative Style High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32. Curran Associates Inc. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/bdbca288fee7f92f2bfa9f7012727740-Abstract.html"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/3549935"},{"key":"e_1_3_2_77_2","doi-asserted-by":"crossref","unstructured":"Jonathan Ragan-Kelley Connelly Barnes Andrew Adams Sylvain Paris Fr\u00e9do Durand and Saman Amarasinghe. 2013. Halide: a language and compiler for optimizing parallelism locality and recomputation in image processing pipelines. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI \u201913). Association for Computing Machinery New York NY USA 519-530. https:\/\/doi.org\/10.1145\/2491956.2462176 https:\/\/doi.org\/10.1145\/2491956.2462176","DOI":"10.1145\/2491956.2462176"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.21105\/joss.03051"},{"key":"e_1_3_2_79_2","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems (2nd ed.). SIAM Philadelphia PA USA.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588717"},{"key":"e_1_3_2_81_2","first-page":"158:1","volume-title":"Proceedings of the ACM on Programming Languages","author":"Senanayake Ryan","year":"2020","unstructured":"Ryan Senanayake, Changwan Hong, Ziheng Wang, Amalee Wilson, Stephen Chou, Shoaib Kamil, Saman Amarasinghe, and Fredrik Kjolstad. 2020. A sparse iteration space transformation framework for sparse tensor algebra. Proceedings of the ACM on Programming Languages 4, OOPSLA (Nov. 2020), 158:1-158:30. https:\/\/doi.org\/10.1145\/3428226"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/3527333"},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384413"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.27"},{"key":"e_1_3_2_85_2","first-page":"1512.00066","article-title":"Sparse Tensor Algebra as a Parallel Programming Model","author":"Solomonik Edgar","year":"2015","unstructured":"Edgar Solomonik and Torsten Hoefler. 2015. Sparse Tensor Algebra as a Parallel Programming Model. arXiv (Nov. 2015). 1512.00066.","journal-title":"arXiv"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.112"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2013.19"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2857721"},{"key":"e_1_3_2_89_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01766-7"},{"key":"e_1_3_2_90_2","first-page":"302","article-title":"TorchSparse: Efficient Point Cloud Inference Engine","volume":"4","author":"Tang Haotian","year":"2022","unstructured":"Haotian Tang, Zhijian Liu, Xiuyu Li, Yujun Lin, and Song Han. 2022. TorchSparse: Efficient Point Cloud Inference Engine. Proceedings of Machine Learning and Systems 4 (April 2022), 302\u2013315.","journal-title":"Proceedings of Machine Learning and Systems"},{"key":"e_1_3_2_91_2","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614303"},{"key":"e_1_3_2_92_2","doi-asserted-by":"crossref","unstructured":"Odysseas G. Tsatalos Marvin H. Solomon and Yannis E. Ioannidis. 1996. The GMAP: A versatile tool for physical data independence. The VLDB Journal 5 (1996) 101\u2013118.","DOI":"10.1007\/s007780050018"},{"key":"e_1_3_2_93_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764454"},{"key":"e_1_3_2_94_2","first-page":"96","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT 2014)","author":"Veldhuizen Todd","year":"2014","unstructured":"Todd Veldhuizen. 2014. Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In Proceedings of the 17th International Conference on Database Theory (ICDT 2014). 96\u2013106. https:\/\/doi.org\/10.5441\/002\/icdt.2014.13"},{"key":"e_1_3_2_95_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_2_96_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2002.10025"},{"key":"e_1_3_2_97_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/16\/1\/071"},{"key":"e_1_3_2_98_2","first-page":"666","article-title":"Unified Convolution Framework: A compiler-based approach to support sparse convolutions","volume":"5","author":"Won Jaeyeon","year":"2023","unstructured":"Jaeyeon Won, Changwan Hong, Charith Mendis, Joel Emer, and Saman Amarasinghe. 2023. Unified Convolution Framework: A compiler-based approach to support sparse convolutions. Proceedings of Machine Learning and Systems 5 (March 2023), 666\u2013679. https:\/\/proceedings.mlsys.org\/paper_files\/paper\/2023\/hash\/ccf7262fb986e4367ccd3903960c57a0-Abstract-mlsys2023.html","journal-title":"Proceedings of Machine Learning and Systems"},{"key":"e_1_3_2_99_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00064"},{"key":"e_1_3_2_100_2","doi-asserted-by":"publisher","DOI":"10.1145\/3225058.3225122"},{"key":"e_1_3_2_101_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582047"},{"key":"e_1_3_2_102_2","first-page":"17","volume-title":"International Workshop on Languages and Compilers for Parallel Computing","author":"Yuki Tomofumi","year":"2012","unstructured":"Tomofumi Yuki, Gautam Gupta, DaeGon Kim, Tanveer Pathan, and Sanjay Rajopadhye. 2012. Alphaz: A system for design space exploration in the polyhedral model. In International Workshop on Languages and Compilers for Parallel Computing. Springer, 17\u201331."},{"key":"e_1_3_2_103_2","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446702"},{"key":"e_1_3_2_104_2","doi-asserted-by":"publisher","DOI":"10.1145\/3566054"},{"key":"e_1_3_2_105_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2932931"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720473","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T16:30:21Z","timestamp":1787589021000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":104,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2025,4,9]]}},"alternative-id":["10.1145\/3720473"],"URL":"https:\/\/doi.org\/10.1145\/3720473","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-10-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}