{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:13:06Z","timestamp":1773277986380,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"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":["1937301,2028602,CCF-1563078,1563113"],"award-info":[{"award-number":["1937301,2028602,CCF-1563078,1563113"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Application Driving Architectures Research Center"},{"name":"Stanford Data Analytics for What's Next"},{"DOI":"10.13039\/100000015","name":"Us Department of Energy","doi-asserted-by":"crossref","award":["DE-SC0008923,DE-SC0018121"],"award-info":[{"award-number":["DE-SC0008923,DE-SC0018121"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR0011-18-3-0007,HR0011-20-9-0017"],"award-info":[{"award-number":["HR0011-18-3-0007,HR0011-20-9-0017"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,10,20]]},"abstract":"<jats:p>This paper shows how to compile sparse array programming languages. A sparse array programming language is an array programming language that supports element-wise application, reduction, and broadcasting of arbitrary functions over dense and sparse arrays with any fill value. Such a language has great expressive power and can express sparse and dense linear and tensor algebra, functions over images, exclusion and inclusion filters, and even graph algorithms.<\/jats:p>\n          <jats:p>Our compiler strategy generalizes prior work in the literature on sparse tensor algebra compilation to support any function applied to sparse arrays, instead of only addition and multiplication. To achieve this, we generalize the notion of sparse iteration spaces beyond intersections and unions. These iteration spaces are automatically derived by considering how algebraic properties annotated onto functions interact with the fill values of the arrays. We then show how to compile these iteration spaces to efficient code.<\/jats:p>\n          <jats:p>When compared with two widely-used Python sparse array packages, our evaluation shows that we generate built-in sparse array library features with a performance of 1.4\u00d7 to 53.7\u00d7 when measured against PyData\/Sparse for user-defined functions and between 0.98\u00d7 and 5.53\u00d7 when measured against SciPy\/Sparse for sparse array slicing. Our technique outperforms PyData\/Sparse by 6.58\u00d7 to 70.3\u00d7, and (where applicable) performs between 0.96\u00d7 and 28.9\u00d7 that of a dense NumPy implementation, on end-to-end sparse array applications. We also implement graph linear algebra kernels in our system with a performance of between 0.56\u00d7 and 3.50\u00d7 compared to that of the hand-optimized SuiteSparse:GraphBLAS library.<\/jats:p>","DOI":"10.1145\/3485505","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Compilation of sparse array programming models"],"prefix":"10.1145","volume":"5","author":[{"given":"Rawn","family":"Henry","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4195-8106","authenticated-orcid":false,"given":"Olivia","family":"Hsu","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Rohan","family":"Yadav","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Stephen","family":"Chou","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Kunle","family":"Olukotun","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Saman","family":"Amarasinghe","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Fredrik","family":"Kjolstad","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467.","author":"Abadi Mart\u00edn","year":"2016","unstructured":"Mart\u00edn Abadi , Ashish Agarwal , Paul Barham , Eugene Brevdo , Zhifeng Chen , Craig Citro , Greg S Corrado , Andy Davis , Jeffrey Dean , and Matthieu Devin . 2016 . Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467. Mart\u00edn Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, and Matthieu Devin. 2016. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.25080\/Majora-4af1f417-00a"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455567.1455599"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/060676489"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/165939.166023"},{"key":"e_1_2_2_6_1","unstructured":"Navoneel Chakrabarty. 2019. Brain MRI Images for Brain Tumor Detection. https:\/\/www.kaggle.com\/navoneel\/brain-mri-images-for-brain-tumor-detection  Navoneel Chakrabarty. 2019. Brain MRI Images for Brain Tumor Detection. https:\/\/www.kaggle.com\/navoneel\/brain-mri-images-for-brain-tumor-detection"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385963"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322125"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_2_11_1","volume-title":"Array programming with NumPy. Nature, 585, 7825","author":"Harris Charles R","year":"2020","unstructured":"Charles R Harris , K Jarrod Millman , St\u00e9fan J van der Walt , Ralf Gommers , Pauli Virtanen , David Cournapeau , Eric Wieser , Julian Taylor , Sebastian Berg , and Nathaniel J Smith . 2020. Array programming with NumPy. Nature, 585, 7825 ( 2020 ), 357\u2013362. Charles R Harris, K Jarrod Millman, St\u00e9fan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, and Nathaniel J Smith. 2020. Array programming with NumPy. Nature, 585, 7825 (2020), 357\u2013362."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356506"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10278-005-9247-6"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the","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. 345\u2013351. Kenneth E Iverson. 1962. A programming language. In Proceedings of the May 1-3, 1962, spring joint computer conference. 345\u2013351."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761646"},{"key":"e_1_2_2_16_1","volume-title":"Graph Algorithms in the Language of Linear Algebra","author":"Kepner Jeremy","year":"1990","unstructured":"Jeremy Kepner and John Gilbert . 2011. Graph Algorithms in the Language of Linear Algebra . Society for Industrial and Applied Mathematics , USA. isbn:08987 1990 9 Jeremy Kepner and John Gilbert. 2011. Graph Algorithms in the Language of Linear Algebra. Society for Industrial and Applied Mathematics, USA. isbn:0898719909"},{"key":"e_1_2_2_17_1","volume-title":"Cai","author":"Kim Jinman","year":"2000","unstructured":"Jinman Kim , David D. Feng , and Tom W . Cai . 2000 . A Web Based Medical Image Data Processing and Management System. In Selected Papers from the Pan-Sydney Workshop on Visualisation - Volume 2 (VIP \u201900). Australian Computer Society , Inc., AUS. 89\u201391. isbn:0909925801 Jinman Kim, David D. Feng, and Tom W. Cai. 2000. A Web Based Medical Image Data Processing and Management System. In Selected Papers from the Pan-Sydney Workshop on Visualisation - Volume 2 (VIP \u201900). Australian Computer Society, Inc., AUS. 89\u201391. isbn:0909925801"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2019.8661185"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_2_20_1","volume-title":"Sparse tensor algebra compilation. Ph. D. Dissertation","author":"Kj\u00f8lstad Fredrik Berg","unstructured":"Fredrik Berg Kj\u00f8lstad . 2020. Sparse tensor algebra compilation. Ph. D. Dissertation . Massachusetts Institute of Technology . Fredrik Berg Kj\u00f8lstad. 2020. Sparse tensor algebra compilation. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0002751"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/360827.360844"},{"key":"e_1_2_2_23_1","volume-title":"International Workshop on Languages and Compilers for Parallel Computing. 96\u2013114","author":"Lin Calvin","year":"1993","unstructured":"Calvin Lin and Lawrence Snyder . 1993 . ZPL: An array sublanguage . In International Workshop on Languages and Compilers for Parallel Computing. 96\u2013114 . Calvin Lin and Lawrence Snyder. 1993. ZPL: An array sublanguage. In International Workshop on Languages and Compilers for Parallel Computing. 96\u2013114."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670338"},{"key":"e_1_2_2_25_1","volume-title":"PyTorch: An Imperative Style","author":"Paszke Adam","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, H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8024\u20138035. http:\/\/papers.neurips.cc\/paper\/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf 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, H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8024\u20138035. http:\/\/papers.neurips.cc\/paper\/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf"},{"key":"e_1_2_2_26_1","volume-title":"SciPy Roadmap V1.6.2. https:\/\/docs.scipy.org\/doc\/scipy-1.6.2\/reference\/roadmap.html [Online","author":"Py.","year":"2021","unstructured":"Sci Py. 2021. SciPy Roadmap V1.6.2. https:\/\/docs.scipy.org\/doc\/scipy-1.6.2\/reference\/roadmap.html [Online ; accessed 04\/12\/ 2021 ] SciPy. 2021. SciPy Roadmap V1.6.2. https:\/\/docs.scipy.org\/doc\/scipy-1.6.2\/reference\/roadmap.html [Online; accessed 04\/12\/2021]"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428226"},{"key":"e_1_2_2_28_1","volume-title":"FROSTT: The Formidable Repository of Open Sparse Tensors and Tools","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith , Jee W. Choi , Jiajia Li , Richard Vuduc , Jongsoo Park , Xing Liu , and George Karypis . 2017 . FROSTT: The Formidable Repository of Open Sparse Tensors and Tools . http:\/\/frostt.io\/ Shaden Smith, Jee W. Choi, Jiajia Li, Richard Vuduc, Jongsoo Park, Xing Liu, and George Karypis. 2017. FROSTT: The Formidable Repository of Open Sparse Tensors and Tools. http:\/\/frostt.io\/"},{"key":"e_1_2_2_29_1","unstructured":"Edgar Solomonik and Torsten Hoefler. 2015. Sparse tensor algebra as a parallel programming model. arXiv preprint arXiv:1512.00066.  Edgar Solomonik and Torsten Hoefler. 2015. Sparse tensor algebra as a parallel programming model. arXiv preprint arXiv:1512.00066."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBME.2010.2091129"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738003"},{"key":"e_1_2_2_32_1","volume-title":"fundamental algorithms for scientific computing in Python. Nature methods, 17, 3","author":"Virtanen Pauli","year":"2020","unstructured":"Pauli Virtanen , Ralf Gommers , Travis E Oliphant , Matt Haberland , Tyler Reddy , David Cournapeau , Evgeni Burovski , Pearu Peterson , Warren Weckesser , and Jonathan Bright . 2020. SciPy 1.0 : fundamental algorithms for scientific computing in Python. Nature methods, 17, 3 ( 2020 ), 261\u2013272. Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, and Jonathan Bright. 2020. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature methods, 17, 3 (2020), 261\u2013272."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1186\/1751-0473-8-20"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485505","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":33,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485505"],"URL":"https:\/\/doi.org\/10.1145\/3485505","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}