{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:45:51Z","timestamp":1780994751098,"version":"3.54.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2143061"],"award-info":[{"award-number":["CCF-2143061"]}],"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":[[2024,10,8]]},"abstract":"<jats:p>\n                    We show how to build a compiler for a sparse array language that supports shape operators such as reshaping or concatenating arrays, in addition to compute operators. Existing sparse array programming systems implement generic shape operators for only some sparse data structures, reduce shape operators on other data structures to those, and do not support fusion. Our system compiles sparse array expressions to code that efficiently iterates over reshaped views of irregular sparse data structures, without needing to materialize temporary storage for intermediates. Our evaluation shows that our approach generates sparse array code competitive with popular sparse array libraries: our generated shape operators achieve geometric mean speed-ups of 1.66\u00d7\u201315.3\u00d7 when compared to hand-written kernels in\n                    <jats:monospace>scipy.sparse<\/jats:monospace>\n                    and 1.67\u00d7\u2013651\u00d7 when compared to generic implementations in\n                    <jats:monospace>pydata\/sparse<\/jats:monospace>\n                    . For operators that require data structure conversions in these libraries, our generated code achieves geometric mean speed-ups of 7.29\u00d7\u201313.0\u00d7 when compared to\n                    <jats:monospace>scipy.sparse<\/jats:monospace>\n                    and 21.3\u00d7\u2013511\u00d7 when compared to\n                    <jats:monospace>pydata\/sparse<\/jats:monospace>\n                    . Finally, our evaluation demonstrates that fusing shape and compute operators improves the performance of several expressions by geometric mean speed-ups of 1.22\u00d7\u20132.23\u00d7.\n                  <\/jats:p>","DOI":"10.1145\/3689752","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T03:23:04Z","timestamp":1728357784000},"page":"1162-1188","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Compilation of Shape Operators on Sparse Arrays"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6221-1389","authenticated-orcid":false,"given":"Alexander J","family":"Root","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6792-6222","authenticated-orcid":false,"given":"Bobby","family":"Yan","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6752-3274","authenticated-orcid":false,"given":"Peiming","family":"Liu","sequence":"additional","affiliation":[{"name":"Google Research, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8493-1133","authenticated-orcid":false,"given":"Christophe","family":"Gyurgyik","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0333-7413","authenticated-orcid":false,"given":"Aart J.C.","family":"Bik","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2267-903X","authenticated-orcid":false,"given":"Fredrik","family":"Kjolstad","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"265","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (Savannah, GA, USA) (OSDI\u201916)","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 Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (Savannah, GA, USA) (OSDI\u201916). USENIX Association, USA, 265\u2013283."},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Hameer Abbasi. 2018. Sparse: a more modern sparse array library. In Proceedings of the 17th python in science conference. 27\u201330.","DOI":"10.25080\/Majora-4af1f417-00a"},{"key":"e_1_3_1_4_2","first-page":"41","volume-title":"Proceedings of the 21st ACM\/IEEE International Symposium on Code Generation and Optimization (Montr\u00e9al, QC, Canada) (CGO 2023)","author":"Ahrens Willow","year":"2023","unstructured":"Willow Ahrens, Daniel Donenfeld, Fredrik Kjolstad, and Saman Amarasinghe. 2023. Looplets: A Language for Structured Coiteration. In Proceedings of the 21st ACM\/IEEE International Symposium on Code Generation and Optimization (Montr\u00e9al, QC, Canada) (CGO 2023). Association for Computing Machinery, New York, NY, USA, 41\u201354. https:\/\/doi.org\/10.1145\/3579990.3580020 10.1145\/3579990.3580020"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/060676489"},{"issue":"4","key":"e_1_3_1_6_2","first-page":"25","article-title":"Compiler Support for Sparse Tensor Computations in MLIR","volume":"19","author":"Bik Aart","year":"2022","unstructured":"Aart Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng, and Fredrik Kjolstad. 2022. Compiler Support for Sparse Tensor Computations in MLIR. ACM Trans. Archit. Code Optim. 19, 4, Article 50 (sep 2022), 25 pages. https:\/\/doi.org\/10.1145\/3544559 10.1145\/3544559","journal-title":"ACM Trans. Archit. Code Optim"},{"key":"e_1_3_1_7_2","volume-title":"Compiler Support for Sparse Matrix Computations","author":"Bik Aart J.C.","year":"1996","unstructured":"Aart J.C. Bik. 1996. Compiler Support for Sparse Matrix Computations. Ph. D. Dissertation. Department of Computer Science, Leiden University. ISBN 90-9009442-3."},{"key":"e_1_3_1_8_2","first-page":"406","volume-title":"Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing (LCPC \u201994)","author":"Bik Aart J.C.","year":"1994","unstructured":"Aart J.C. Bik, Peter M.W. Knijenburg, and Harry A.G. Wijshoff. 1994. Reshaping Access Patterns for Generating Sparse Codes. In Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing (LCPC \u201994). Springer-Verlag, Berlin, Heidelberg, 406\u2013420."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0917019"},{"key":"e_1_3_1_10_2","first-page":"30","article-title":"Format Abstraction for Sparse Tensor Algebra Compilers","volume":"2","author":"Chou Stephen","year":"2018","unstructured":"Stephen Chou, Fredrik Kjolstad, and Saman Amarasinghe. 2018. Format Abstraction for Sparse Tensor Algebra Compilers. Proc. ACM Program. Lang. 2, OOPSLA, Article 123 (oct 2018), 30 pages. https:\/\/doi.org\/10.1145\/3276493 10.1145\/3276493","journal-title":"Proc. ACM Program. Lang"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_1_12_2","volume-title":"Direct Methods for Sparse Matrices","author":"Duff Iain S.","year":"1990","unstructured":"Iain S. Duff, A.M. Erisman, and J.K. Reid. 1990. Direct Methods for Sparse Matrices. Oxford Science Publications, Oxford."},{"key":"e_1_3_1_13_2","volume-title":"Reference: Racket","author":"Flatt Matthew","year":"2010","unstructured":"Matthew Flatt and PLT. 2010. Reference: Racket. Technical Report PLT-TR-2010-1. PLT Design Inc. https:\/\/racket-lang.org\/tr1\/."},{"key":"e_1_3_1_14_2","volume-title":"Computer Solution of Large Sparse Positive Definite Systems","author":"George Alan","unstructured":"Alan George and Joseph W.H. Liu. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall, Englewood Cliffs, New York."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_3_1_16_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-1-4615-8675-3_4","volume-title":"Sparse Matrices and Their Applications","author":"Gustavson Fred G.","year":"1972","unstructured":"Fred G. Gustavson. 1972. Some Basic Techniques for Solving Sparse Systems of Linear Equations. In Sparse Matrices and Their Applications, Donald J. Rose and Ralph A. Willoughby (Eds.). Plenum Press, New York, NY, 41\u201352."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062354"},{"key":"e_1_3_1_19_2","first-page":"29","article-title":"Compilation of Sparse Array Programming Models","volume":"5","author":"Henry Rawn","year":"2021","unstructured":"Rawn Henry, Olivia Hsu, Rohan Yadav, Stephen Chou, Kunle Olukotun, Saman Amarasinghe, and Fredrik Kjolstad. 2021. Compilation of Sparse Array Programming Models. Proc. ACM Program. Lang. 5, OOPSLA, Article 128 (oct 2021), 29 pages. https:\/\/doi.org\/10.1145\/3485505 10.1145\/3485505","journal-title":"Proc. ACM Program. Lang"},{"key":"e_1_3_1_20_2","first-page":"345","volume-title":"Proceedings of the May 1-3, 1962, Spring Joint Computer Conference (San Francisco, California) (AIEE-IRE \u201962 (Spring))","author":"Iverson Kenneth E.","year":"1962","unstructured":"Kenneth E. Iverson. 1962. A Programming Language. In Proceedings of the May 1-3, 1962, Spring Joint Computer Conference (San Francisco, California) (AIEE-IRE \u201962 (Spring)). Association for Computing Machinery, New York, NY, USA, 345\u2013351. https:\/\/doi.org\/10.1145\/1460833.1460872 10.1145\/1460833.1460872"},{"key":"e_1_3_1_21_2","unstructured":"Wenzel Jakob. 2022. nanobind: tiny and efficient C++\/Python bindings. https:\/\/github.com\/wjakob\/nanobind."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/3314872.3314894"},{"key":"e_1_3_1_23_2","first-page":"29","article-title":"The Tensor Algebra Compiler","volume":"1","author":"Kjolstad Fredrik","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, Article 77 (oct 2017), 29 pages. https:\/\/doi.org\/10.1145\/3133901 10.1145\/3133901","journal-title":"Proc. ACM Program. Lang"},{"key":"e_1_3_1_24_2","first-page":"25","article-title":"Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs","volume":"7","author":"Kovach Scott","year":"2023","unstructured":"Scott Kovach, Praneeth Kolichala, Tiancheng Gu, and Fredrik Kjolstad. 2023. Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs. Proc. ACM Program. Lang. 7, PLDI, Article 154 (jun 2023), 25 pages. https:\/\/doi.org\/10.1145\/3591268 10.1145\/3591268","journal-title":"Proc. ACM Program. Lang"},{"key":"e_1_3_1_25_2","first-page":"28","article-title":"Verified Tensor-Program Optimization via High-Level Scheduling Rewrites","volume":"6","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. Proc. ACM Program. Lang. 6, POPL, Article 55 (jan 2022), 28 pages. https:\/\/doi.org\/10.1145\/3498717 10.1145\/3498717","journal-title":"Proc. ACM Program. Lang"},{"key":"e_1_3_1_26_2","volume-title":"PyTorch: An Imperative Style, High-Performance Deep Learning Library","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas K\u00f6pf, Edward Yang, Zach 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. Curran Associates Inc., Red Hook, NY, USA."},{"key":"e_1_3_1_27_2","volume-title":"Sparse Matrix Technology","author":"Pissanetsky Sergio","year":"1984","unstructured":"Sergio Pissanetsky. 1984. Sparse Matrix Technology. Academic Press, London."},{"key":"e_1_3_1_28_2","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1145\/2491956.2462176","volume-title":"Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Ragan-Kelley Jonathan","year":"2013","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. Association for Computing Machinery, New York, NY, USA, 519\u2013530. https:\/\/doi.org\/10.1145\/2491956.2462176 10.1145\/2491956.2462176"},{"key":"e_1_3_1_29_2","unstructured":"Alexander J Root Bobby Yan Peiming Liu Christophe Gyurgyik Aart Bik and Fredrik Kjolstad. 2024. Artifact for OOPSLA 2024 Paper: Compilation of Shape Operators on Sparse Arrays. https:\/\/doi.org\/10.5281\/zenodo.13381305 10.5281\/zenodo.13381305"},{"key":"e_1_3_1_30_2","article-title":"A Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra","volume":"4","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 (November 2020). Issue OOPSLA.","journal-title":"Proceedings of the ACM on Programming Languages"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1201\/b18657"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2017.7863730"},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1145\/3183713.3196893","volume-title":"Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD \u201918)","author":"Tahboub Ruby Y.","year":"2018","unstructured":"Ruby Y. Tahboub, Gr\u00e9gory M. Essertel, and Tiark Rompf. 2018. How to Architect a Query Compiler, Revisited. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD \u201918). Association for Computing Machinery, New York, NY, USA, 307\u2013322. https:\/\/doi.org\/10.1145\/3183713.3196893 10.1145\/3183713.3196893"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389701"},{"key":"e_1_3_1_35_2","volume-title":"Sparse Matrices","author":"Tewarson Reginal P.","year":"1973","unstructured":"Reginal P. Tewarson. 1973. Sparse Matrices. Academic Press, New York, NY."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1967.6011"},{"key":"e_1_3_1_37_2","first-page":"6000","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS\u201917)","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is All You Need. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS\u201917). Curran Associates Inc., Red Hook, NY, USA, 6000\u20136010."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582047"},{"issue":"1","key":"e_1_3_1_40_2","first-page":"26","article-title":"Polyhedral Specification and Code Generation of Sparse Tensor Contraction with Co-Iteration","volume":"20","author":"Zhao Tuowen","year":"2022","unstructured":"Tuowen Zhao, Tobi Popoola, Mary Hall, Catherine Olschanowsky, and Michelle Strout. 2022. Polyhedral Specification and Code Generation of Sparse Tensor Contraction with Co-Iteration. ACM Trans. Archit. Code Optim. 20, 1, Article 16 (dec 2022), 26 pages. https:\/\/doi.org\/10.1145\/3566054 10.1145\/3566054","journal-title":"ACM Trans. Archit. Code Optim"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-1116-6"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689752","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689752","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T09:13:52Z","timestamp":1770196432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689752"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":40,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2024,10,8]]}},"alternative-id":["10.1145\/3689752"],"URL":"https:\/\/doi.org\/10.1145\/3689752","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}