{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:28:27Z","timestamp":1787333307308,"version":"build-2736575974"},"reference-count":55,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"ACENET"},{"DOI":"10.13039\/501100021202","name":"Digital Research Alliance of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021202","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006168","name":"National Nuclear Security Administration","doi-asserted-by":"publisher","award":["DE-NA0003963"],"award-info":[{"award-number":["DE-NA0003963"]}],"id":[{"id":"10.13039\/100006168","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Sparse matrices are ubiquitous in computational science, enabling significant reductions in both compute time and memory overhead for problems with local connectivity. Simultaneously, recent work in automatic differentiation has lead to explosive growth in the adoption of accessible frameworks, such as PyTorch, TensorFlow, and JAX, which allow for the rapid development of optimization problems in computational settings. However, these existing tools lack support for sparse linear algebra, severely limiting their use in settings such as scientific machine-learning (SciML) and numerical PDEs, where the use of sparsity is often a necessity for achieving efficient algorithms. In this paper, we develop a set of performant kernels that allow for efficient automatic differentiation of expressions with sparse matrix values; fine-grained parallelism is exploited and performance is highlighted on massively-parallel graphics processing units (GPUs). We also present several applications that are enhanced by the use of these kernels, such as computing optimal transmission conditions for optimized Schwarz methods or finding sparse preconditioners for conjugate gradients. The use of backpropagation with these sparse operations results in massive speed gains when compared to their dense counterparts, with speedups ranging from [Formula: see text] to [Formula: see text] (or more), and enabling computation on larger problems than is possible using dense operations.<\/jats:p>\n                  <jats:p>Reproducibility of computational results. This paper has been awarded the \u201cSIAM Reproducibility Badge: Code and data available\u201d as recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https:\/\/github.com\/nicknytko\/numml\/tree\/main and in the supplementary materials ( numml-main.zip [85.0KB]). [Formula: see text]<\/jats:p>","DOI":"10.1137\/24m1711832","type":"journal-article","created":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:23:02Z","timestamp":1760080982000},"page":"C1115-C1143","source":"Crossref","is-referenced-by-count":0,"title":["Optimized Sparse Matrix Operations for Reverse Mode Automatic Differentiation"],"prefix":"10.1137","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8388-7908","authenticated-orcid":true,"given":"Nicolas","family":"Nytko","sequence":"first","affiliation":[{"name":"Siebel School of Computing and Data Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Taghibakhshi","sequence":"additional","affiliation":[{"name":"NVIDIA Corporation, 11001 Lakeline Blvd., Suite #100, Bldg.\u00a02, Austin, TX 78717, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6527-8212","authenticated-orcid":true,"given":"Tareq Uz","family":"Zaman","sequence":"additional","affiliation":[{"name":"Department of Process Engineering, Memorial University of Newfoundland, St.\u00a0Johns, NL A1C 5S7, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6364-0684","authenticated-orcid":true,"given":"Scott","family":"MacLachlan","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Memorial University of Newfoundland, St. Johns, NL A1C 5S7, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5283-6104","authenticated-orcid":true,"given":"Luke N.","family":"Olson","sequence":"additional","affiliation":[{"name":"Siebel School of Computing and Data Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7605-0050","authenticated-orcid":true,"given":"Matthew","family":"West","sequence":"additional","affiliation":[{"name":"Department of Mechanical Science and Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,10,10]]},"reference":[{"key":"ref1","unstructured":"M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng, TensorFlow: A system for large-scale machine learning, in 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), USENIX Association, Savannah, GA, 2016, pp. 265\u2013283, https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/abadi."},{"key":"ref2","first-page":"5595","volume":"18","author":"Baydin A. G.","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/110838844"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2015.12.008"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.03.016"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TMTT.1974.1128209"},{"key":"ref7","unstructured":"J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang, JAX: Composable Transformations of Python+NumPy Programs, 2018, http:\/\/github.com\/google\/jax."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719505"},{"key":"ref9","unstructured":"O. Br\u00f6ker, Parallel Multigrid Methods Using Sparse Approximate Inverses, Ph.D. thesis, ETH Zurich, 2003, https:\/\/doi.org\/10.3929\/ETHZ-A-004617648."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/19M1308669"},{"key":"ref11","unstructured":"J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, Spectral Networks and Locally Connected Networks on Graphs, http:\/\/arxiv.org\/abs\/1312.6203, 2013."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(01)00110-6"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/140968896"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"S. Dalton, S. Baxter, D. Merrill, L. Olson, and M. Garland, Optimizing sparse matrix operations on GPUs using merge path, in Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International, IEEE, New York, NY, 2015, pp. 407\u2013416, https:\/\/doi.org\/10.1109\/IPDPS.2015.98.","DOI":"10.1109\/IPDPS.2015.98"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/2699470"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2306"},{"key":"ref19","unstructured":"M. Fey and J. E. Lenssen, Fast Graph Representation Learning with PyTorch Geometric, 2019, https:\/\/github.com\/pyg-team\/pytorch_geometric."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3090316"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/110837218"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1334"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8369-7"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68942-3_4"},{"key":"ref25","unstructured":"D. Greenfeld, M. Galun, R. Basri, I. Yavneh, and R. Kimmel, Learning to optimize multigrid PDE solvers, in Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research 97, K. Chaudhuri and R. Salakhutdinov, eds. PMLR, 2019, pp. 2415\u20132423, https:\/\/proceedings.mlr.press\/v97\/greenfeld19a.html."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594276552"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1177\/1094342015593156"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/21M1430030"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023988426844"},{"key":"ref30","unstructured":"T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks, in International Conference on Learning Representations, 2017."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(20000530)48:3<401::AID-NME880>3.0.CO;2-D"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/0614004"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/18M1173769"},{"key":"ref34","unstructured":"J. F. Nolan, Analytical Differentiation on a Digital Computer, Ph.D. thesis, Massachusetts Institute of Technology, 1953, https:\/\/dspace.mit.edu\/handle\/1721.1\/12297."},{"key":"ref35","unstructured":"R. Okuta, Y. Unno, D. Nishino, S. Hido, and C. Loomis, CuPY: A NumPy-compatible library for NVIDIA GPU calculations, in Proceedings of Workshop on Machine Learning Systems (LearningSys) in The Thirty-First Annual Conference on Neural Information Processing Systems (NIPS), 2017, http:\/\/learningsys.org\/nips17\/assets\/papers\/paper_16.pdf."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827501397950"},{"key":"ref37","unstructured":"A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. K\u00f6pf, E. Z. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, PyTorch: An Imperative Style, High-Performance Deep Learning Library, CoRR, https:\/\/arxiv.org\/abs\/1912.01703, 2019."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/MDAT.2020.2974910"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(64)90137-5"},{"key":"ref40","series-title":"Texts in Applied Mathematics","volume-title":"Numerical Mathematics","author":"Quarteroni A.","year":"2006","edition":"2"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"ref42","doi-asserted-by":"crossref","unstructured":"J. Su, F. Zhang, W. Liu, B. He, R. Wu, X. Du, and R. Wang, CapelliniSpTRSV: A thread-level synchronization-free sparse triangular solve on GPUs, in Proceedings of the 49th International Conference on Parallel Processing, ICPP \u201920, Association for Computing Machinery, New York, NY, 2020, https:\/\/doi.org\/10.1145\/3404397.3404400.","DOI":"10.1145\/3404397.3404400"},{"key":"ref43","first-page":"7222","volume-title":"Advances in Neural Information Processing Systems","volume":"35","author":"Taghibakhshi A.","year":"2022"},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"Y. Tao, Y. Deng, S. Mu, M. Zhu, L. Xiao, L. Ruan, and Z. Huang, Atomic reduction based sparse matrix-transpose vector multiplication on GPUs, in Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS, 2014, pp. 987\u2013992, https:\/\/doi.org\/10.1109\/PADSW.2014.7097920.","DOI":"10.1109\/PADSW.2014.7097920"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/21M1431199"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/b137868"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"ref48","unstructured":"M. Wang, D. Zheng, Z. Ye, Q. Gan, M. Li, X. Song, J. Zhou, C. Ma, L. Yu, Y. Gai, T. Xiao, T. He, G. Karypis, J. Li, and Z. Zhang, Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks, https:\/\/arxiv.org\/abs\/1909.01315, 2020."},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/j.tbench.2021.100007"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1201\/9781420034998"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"ref52","unstructured":"Z. Yang, W. Cohen, and R. Salakhudinov, Revisiting semi-supervised learning with graph embeddings, in Proceedings of the 33rd International Conference on Machine Learning, Proceedings of Machine Learning Research 48, M. F. Balcan and K. Q. Weinberger, eds. PMLR, New York, NY, 2016, pp. 40\u201348, https:\/\/proceedings.mlr.press\/v48\/yanga16.html."},{"key":"ref53","unstructured":"H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna, GraphSAINT: Graph sampling based inductive learning method, in International Conference on Learning Representations, 2020, https:\/\/openreview.net\/forum?id=BJe8pkHFwS."},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18074.2021.9586141"},{"key":"ref55","doi-asserted-by":"crossref","unstructured":"K. \u015awirydowicz, N. Koukpaizan, T. Ribizel, F. G\u00f6bel, S. Abhyankar, H. Anzt, and S. Pele\u0161, GPU-Resident Sparse Direct Linear Solvers for Alternating Current Optimal Power Flow Analysis, http:\/\/arxiv.org\/abs\/2306.14337, 2023.","DOI":"10.1016\/j.ijepes.2023.109517"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1711832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:49:53Z","timestamp":1787330993000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1711832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,10]]},"references-count":55,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1137\/24M1711832"],"URL":"https:\/\/doi.org\/10.1137\/24m1711832","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,10]]}}}