{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T19:48:35Z","timestamp":1783108115178,"version":"3.54.6"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T00:00:00Z","timestamp":1652400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CAREER","award":["1652515"],"award-info":[{"award-number":["1652515"]}]},{"name":"NSF","award":["OAC-1835712, OIA-1937043, CHS-1908767, CHS-1901091"],"award-info":[{"award-number":["OAC-1835712, OIA-1937043, CHS-1908767, CHS-1901091"]}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["DGECR-2021-00461 and RGPIN-2021-03707"],"award-info":[{"award-number":["DGECR-2021-00461 and RGPIN-2021-03707"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["101003104"],"award-info":[{"award-number":["101003104"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>We introduce a code generator that converts unoptimized C++ code operating on sparse data into vectorized and parallel CPU or GPU kernels. Our approach unrolls the computation into a massive expression graph, performs redundant expression elimination, grouping, and then generates an architecture-specific kernel to solve the same problem, assuming that the sparsity pattern is fixed, which is a common scenario in many applications in computer graphics and scientific computing. We show that our approach scales to large problems and can achieve speedups of two orders of magnitude on CPUs and three orders of magnitude on GPUs, compared to a set of manually optimized CPU baselines. To demonstrate the practical applicability of our approach, we employ it to optimize popular algorithms with applications to physical simulation and interactive mesh deformation.<\/jats:p>","DOI":"10.1145\/3520484","type":"journal-article","created":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T11:41:29Z","timestamp":1648813289000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Sparsity-Specific Code Optimization using Expression Trees"],"prefix":"10.1145","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8389-792X","authenticated-orcid":false,"given":"Philipp","family":"Herholz","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2505-6727","authenticated-orcid":false,"given":"Xuan","family":"Tang","sequence":"additional","affiliation":[{"name":"New York University, New York, NY USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5969-636X","authenticated-orcid":false,"given":"Teseo","family":"Schneider","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5965-3717","authenticated-orcid":false,"given":"Shoaib","family":"Kamil","sequence":"additional","affiliation":[{"name":"Adobe Research, Cambridge, MA USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1183-2454","authenticated-orcid":false,"given":"Daniele","family":"Panozzo","sequence":"additional","affiliation":[{"name":"New York University, New York, NY USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8089-3974","authenticated-orcid":false,"given":"Olga","family":"Sorkine-Hornung","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,5,13]]},"reference":[{"key":"e_1_3_2_2_1","volume-title":"Compilers: Pearson New International Edition: Principles, Techniques, and Tools","author":"Aho A. V.","year":"2013","unstructured":"A. V. Aho, Monica S. Lam, R. Sethi, and J. D. Ullman. 2013. Compilers: Pearson New International Edition: Principles, Techniques, and Tools. Pearson."},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14068"},{"key":"e_1_3_2_4_1","unstructured":"AMD. 2020. rocmSPARSE. (2020). Retrieved from https:\/\/rocsparse.readthedocs.io\/en\/master\/."},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/323215"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314615"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/266469.266486"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280821"},{"key":"e_1_3_2_9_1","article-title":"Automatic differentiation in machine learning: A survey","volume":"18","author":"Baydin Atilim Gunes","year":"2017","unstructured":"Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. 2017. Automatic differentiation in machine learning: A survey. Journal of Machine Learning Research 18, 1 (2017), 5595\u20135637.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892632"},{"key":"e_1_3_2_11_1","unstructured":"Jeff Bezanson Stefan Karpinski Viral B. Shah and Alan Edelman. 2012. Julia: A Fast Dynamic Language for Technical Computing. (2012)."},{"key":"e_1_3_2_12_1","doi-asserted-by":"crossref","unstructured":"Aart J. C. Bik and Harry A. G. Wijshoff. 1993. Compilation techniques for sparse matrix computations. In Proceedings of the 1993 International Conference on Supercomputing . ACM 416\u2013424.","DOI":"10.1145\/165939.166023"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57659-2_4"},{"key":"e_1_3_2_14_1","doi-asserted-by":"crossref","unstructured":"Matthias Bollh\u00f6fer Olaf Schenk Radim Janalik Steve Hamm and Kiran Gullapalli. 2020. State-of-the-art sparse direct solvers. Parallel Algorithms in Computational Science and Engineering.","DOI":"10.1007\/978-3-030-43736-7_1"},{"key":"e_1_3_2_15_1","article-title":"Autotuning sparse matrix-vector multiplication for multicore","author":"Byun Jong-Ho","year":"2012","unstructured":"Jong-Ho Byun, Richard Lin, Katherine A. Yelick, and James Demmel. 2012. Autotuning sparse matrix-vector multiplication for multicore. EECS, UC Berkeley, Tech. Rep (2012).","journal-title":"EECS, UC Berkeley, Tech. Rep"},{"key":"e_1_3_2_16_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis","author":"Cheshmi Kazem","year":"2018","unstructured":"Kazem Cheshmi, Shoaib Kamil, Michelle Mills Strout, and Maryam Mehri Dehnavi. 2018. ParSy: Inspection and transformation of sparse matrix computations for parallelism. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE Press, Piscataway, NJ, Article 62, 15 pages. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3291656.3291739."},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.softx.2021.100901"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132188"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55406"},{"key":"e_1_3_2_21_1","article-title":"TensorFlow Sparse Tensors","year":"2017","unstructured":"Google. 2017. TensorFlow Sparse Tensors. Retrieved 27 Sept., 2021 from https:\/\/www.tensorflow.org\/api_guides\/python\/sparse_ops. (2017).","journal-title":"R"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356052.1356053"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717761"},{"key":"e_1_3_2_24_1","article-title":"Eigen v3","author":"Guennebaud Ga\u00ebl","year":"2010","unstructured":"Ga\u00ebl Guennebaud and Beno\u00eet Jacob. 2010. Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org. (2010).","journal-title":"R"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCSim.2012.6266939"},{"key":"e_1_3_2_26_1","volume-title":"Developer Reference for Intel oneAPI Math Kernel Library - C","year":"2021","unstructured":"Intel. 2021. Developer Reference for Intel oneAPI Math Kernel Library - C. Technical Report. Retrieved from https:\/\/software.intel.com\/content\/dam\/develop\/external\/us\/en\/documents\/onemkl-developerreference-c.pdf."},{"key":"e_1_3_2_27_1","unstructured":"Wenzel Jakob. 2010. Mitsuba Renderer. (2010). Retrieved 27 Sept. 2021 from http:\/\/www.mitsuba-renderer.org."},{"key":"e_1_3_2_28_1","doi-asserted-by":"crossref","unstructured":"Fredrik Kjolstad Peter Ahrens Shoaib Kamil and Saman Amarasinghe. 2019. Tensor algebra compilation with workspaces. In Proceedings of the 2019 IEEE\/ACM International Symposium on Code Generation and Optimization . IEEE Press 180\u2013192. 180\u2013192. DOI:http:\/\/dl.acm.org\/citation.cfm?id=3314872.3314894","DOI":"10.1109\/CGO.2019.8661185"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2866569"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0002751"},{"key":"e_1_3_2_32_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","author":"Liu Baoyuan","year":"2015","unstructured":"Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. 2015. Sparse convolutional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition."},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459748"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453986"},{"key":"e_1_3_2_35_1","volume-title":"version 8.3.0 (R2014a)","year":"2014","unstructured":"MATLAB. 2014. version 8.3.0 (R2014a). The MathWorks Inc., Natick, Massachusetts."},{"key":"e_1_3_2_36_1","volume-title":"Computing the Singular Value Decomposition of 3x3 Matrices with Minimal Branching and Elementary Floating Point Operations","author":"McAdams Aleka","year":"2011","unstructured":"Aleka McAdams, Andrew Selle, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Computing the Singular Value Decomposition of 3x3 Matrices with Minimal Branching and Elementary Floating Point Operations. Technical Report. University of Wisconsin-Madison Department of Computer Sciences."},{"key":"e_1_3_2_37_1","volume-title":"cuSPARSE Library","year":"2020","unstructured":"Nvidia. 2020. cuSPARSE Library. Technical Report. Retrieved from https:\/\/docs.nvidia.com\/cuda\/pdf\/CUSPARSE_Library.pdf."},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/109025.109108"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185528"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462176"},{"key":"e_1_3_2_41_1","volume-title":"Armadillo: An Open Source C++ Linear Algebra Library for Fast Prototyping and Computationally Intensive Experiments","author":"Sanderson Conrad","year":"2010","unstructured":"Conrad Sanderson. 2010. Armadillo: An Open Source C++ Linear Algebra Library for Fast Prototyping and Computationally Intensive Experiments. Technical Report. NICTA."},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428226"},{"key":"e_1_3_2_43_1","first-page":"109","volume-title":"Proceedings of EUROGRAPHICS\/ACM SIGGRAPH Symposium on Geometry Processing","author":"Sorkine Olga","year":"2007","unstructured":"Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Proceedings of EUROGRAPHICS\/ACM SIGGRAPH Symposium on Geometry Processing. 109\u2013116."},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58604-1_41"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14080"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2011.37"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764454"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738003"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.40"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/16\/1\/071"},{"key":"e_1_3_2_52_1","unstructured":"Joerg Walter and Mathias Koch. 2007. uBLAS. (2007). Retrieved from http:\/\/www.boost.org\/libs\/numeric\/ublas\/doc\/index.htm."},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.1998.10004"},{"key":"e_1_3_2_54_1","unstructured":"Katja Wolff Philipp Herholz Verena Ziegler Frauke Link Nico Br\u00fcgel and Olga Sorkine-Hornung. 2021. 3D Custom Fit Garment Design with Body Movement. arxiv:cs.GR\/2102.05462. Retrieved from https:\/\/arxiv.org\/abs\/2102.05462."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3520484","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3520484","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3520484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:32Z","timestamp":1750183772000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3520484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,13]]},"references-count":53,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3520484"],"URL":"https:\/\/doi.org\/10.1145\/3520484","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,13]]},"assertion":[{"value":"2021-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}