{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T10:39:37Z","timestamp":1791974377309,"version":"4.4.0"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erd\u00f6s--R\u00e9nyi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first implementation of the 3D SpGEMM formulation that exploits multiple (intranode and internode) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research.<\/jats:p>","DOI":"10.1137\/15m104253x","type":"journal-article","created":{"date-parts":[[2016,11,8]],"date-time":"2016-11-08T10:40:56Z","timestamp":1478601656000},"page":"C624-C651","source":"Crossref","is-referenced-by-count":87,"title":["Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication"],"prefix":"10.1137","volume":"38","author":[{"given":"Ariful","family":"Azad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Grey","family":"Ballard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aydin","family":"Bulu\u00e7","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura","family":"Grigori","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oded","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel","family":"Williams","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,11,8]]},"reference":[{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/13092589X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.75"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.21236\/ADA580140"},{"key":"atypb6","first-page":"86","volume-title":"Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM","author":"Ballard G.","year":"2015"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/110838844"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/120870761"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503293"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2014.03.012"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2008.45"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/110848244"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719918.ch13"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1206"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/2699470"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881"},{"key":"atypb20","first-page":"1","volume":"38","author":"Davis T. A.","year":"2011","journal-title":"ACM Trans. Math. Softw."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0210049"},{"key":"atypb23","first-page":"255","volume":"9","author":"Geijn R. A. V. D.","year":"1997","journal-title":"Concurr. Comput."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2008.45"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/130948811"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355796"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224228"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089021"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719918"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2013.95"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.3168"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1099"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626414420055"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.010"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.08.010"},{"key":"atypb39","volume-title":"J. Poulson, Scalable Universal Matrix Multiplication Algorithms: $2$D and $3$D Variations on a Theme, Tech. report","author":"R.","year":"2013"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670338"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/13093426X"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20119-1_4"},{"key":"atypb43","unstructured":"V. B. Shah,\n                      An Interactive System for Combinatorial Scientific Computing with an Emphasis on Programmer Productivity\n                      , Ph.D. thesis, University of California, Santa Barbara, 2007."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23397-5_10"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9668-0_39"},{"key":"atypb47","unstructured":"S. van Dongen,\n                      Graph Clustering by Flow Simulation\n                      , Ph.D. thesis, University of Utrecht, Utrecht, The Netherlands, 2000."},{"key":"atypb48","series-title":"Lecture Notes in Comput","first-page":"421","volume-title":"High Performance Computing for Computational Science \u0096 VECPAR","author":"Yamazaki I.","year":"2010"},{"key":"atypb49","first-page":"254","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04)","author":"Yuster R.","year":"2004"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M104253X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:12:58Z","timestamp":1787328778000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M104253X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/15M104253X"],"URL":"https:\/\/doi.org\/10.1137\/15m104253x","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}