{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,13]],"date-time":"2026-09-13T12:53:48Z","timestamp":1789304028242,"version":"build-2803163510"},"reference-count":87,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["818252"],"award-info":[{"award-number":["818252"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Cyprus Institute","award":["135"],"award-info":[{"award-number":["135"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1354\/23"],"award-info":[{"award-number":["1354\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Matrix multiplication is one of the most extensively used kernels in scientific computing. Although subcubic algorithms exist, most high performance implementations are based on the classical [Formula: see text] matrix multiplication. Designing an algorithm that obtains even modest improvements in performance over existing implementations, requires carefully addressing challenges such as reducing computation costs, communication costs, and memory footprint. We provide the first high performance general matrix-matrix multiplication that utilizes the alternative basis method on Strassen\u2019s algorithm. We reduce the basis transformation overheads and decrease the memory footprint of the bilinear phase by using the pebbling game optimization scheme, consequentially improving both arithmetic and communication costs. Our algorithm outperforms DGEMM on feasible matrix dimensions starting at [Formula: see text]. It obtains an increasing speedup of up to nearly [Formula: see text] speedup for larger matrix dimensions when running sequentially, and even larger speedups for certain matrix dimensions when running in parallel.<\/jats:p>","DOI":"10.1137\/22m1502719","type":"journal-article","created":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T04:47:07Z","timestamp":1700023627000},"page":"C277-C303","source":"Crossref","is-referenced-by-count":15,"title":["Pebbling Game and Alternative Basis for High Performance Matrix Multiplication"],"prefix":"10.1137","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1309-5566","authenticated-orcid":true,"given":"Oded","family":"Schwartz","sequence":"first","affiliation":[{"name":"The Rachel and Selim Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noa","family":"Vaknin","sequence":"additional","affiliation":[{"name":"The Rachel and Selim Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,11,15]]},"reference":[{"key":"ref1","unstructured":"Tips to Measure the Performance of Matrix Multiplication using Intel\n                      \u00ae\n                      MKL, https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/articles\/technical\/a-simple-example-to-measure-the-performance-of-an-intel-mkl-function.html (2017)."},{"key":"ref2","unstructured":"Intel\n                      \u00ae\n                      oneAPI Math Kernel Library, https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/tools\/oneapi\/onemkl.html (2020)."},{"key":"ref3","unstructured":"AMD Optimizing CPU Libraries (AOCL), https:\/\/developer.amd.com\/amd-aocl\/#documentationl (2022)."},{"key":"ref4","unstructured":"Nvidia cuBLAS, https:\/\/developer.nvidia.com\/cublas (2022)."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1147\/rd.395.0575"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-015-0378-1"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"J. Alman and V. V. Williams, A refined laser method and faster matrix multiplication, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 522\u2013539.","DOI":"10.1137\/1.9781611976465.32"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719604"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68111-3_66"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/0909040"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF00129836"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032168"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz, Brief announcement: Strong scaling of matrix multiplication algorithms and memory-independent communication lower bounds, in Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2012, pp. 77\u201379.","DOI":"10.1145\/2312005.2312021"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz, Communication-optimal parallel algorithm for Strassen\u2019s matrix multiplication, in Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2012, pp. 193\u2013204.","DOI":"10.1145\/2312005.2312044"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395121"},{"key":"ref17","unstructured":"G. Beniamini, N. Cheng, O. Holtz, E. Karstadt, and O. Schwartz, Sparsifying the Operators of Fast Matrix Multiplication Algorithms, preprint, arXiv:2008.03759, 2020."},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"G. Beniamini and O. Schwartz, Faster matrix multiplication via sparse decomposition, in The 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2019, pp. 11\u201322.","DOI":"10.1145\/3323165.3323188"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/2858788.2688513"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90091-4"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_16"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719642"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"B. Boyer, J.G. Dumas, C. Pernet, and W. Zhou, Memory efficient scheduling of Strassen-Winograd\u2019s matrix multiplication algorithm, in Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 55\u201362.","DOI":"10.1145\/1576702.1576713"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"R. P. Brent, Algorithms for Matrix Multiplication, Technical report Stan-CS-70-157, Department of Computer Science, Stanford University, Stanford, CA, 1970.","DOI":"10.21236\/AD0705509"},{"key":"ref25","unstructured":"L. E. Cannon, A Cellular Computer to Implement the Kalman Filter Algorithm, Ph.D. thesis, Montana State University, Bozeman, MT, 1969."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2016.07.004"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268135"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/0211038"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049664"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-007-0114-x"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"J. Demmel, D. Eliahu, A. Fox, S. Kamil, B. Lipshitz, O. Schwartz, and O. Spillinger, Communication-optimal parallel recursive rectangular matrix multiplication, in 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, IEEE, Piscataway, NJ, 2013, pp. 261\u2013272.","DOI":"10.1109\/IPDPS.2013.80"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.791"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1994.1001"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050348"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503428693"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-022-05172-4"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, Cache-oblivious algorithms, in 40th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 285\u2013297.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2012.04.014"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626496000029"},{"key":"ref42","doi-asserted-by":"crossref","unstructured":"T. Hadas and O. Schwartz, Towards practical fast matrix multiplication based on trilinear aggregation, in Proceedings of the 48th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2023.","DOI":"10.1145\/3597066.3597099"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/0120004"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"J. Huang, L. Rice, D. A. Matthews, and R. A. van de Geijn, Generating families of practical fast matrix multiplication algorithms, in 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, Piscataway, NJ, 2017, pp. 656\u2013667.","DOI":"10.1109\/IPDPS.2017.56"},{"key":"ref46","doi-asserted-by":"crossref","unstructured":"J. Huang, T. M. Smith, G. M. Henry, and R. A. Van De Geijn, Strassen\u2019s algorithm reloaded, in SC\u201916:\u00a0Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, Piscataway, NJ, 2016, pp. 690\u2013701.","DOI":"10.1109\/SC.2016.58"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1145\/3372419"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"S. Huss-Lederman, E. M. Jacobson, J. R. Johnson, A. Tsao, and T. Turnbull, Implementation of Strassen\u2019s algorithm for matrix multiplication, in Supercomputing\u201996: Proceedings of the 1996 ACM\/IEEE Conference on Supercomputing, IEEE, Piscataway, NJ, 1996, pp. 32\u201332.","DOI":"10.1145\/369028.369096"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"S. Huss-Lederman, E. M. Jacobson, J. R. Johnson, A. Tsao, and T. Turnbull, Strassen\u2019s algorithm for matrix multiplication: Modeling, analysis, and implementation, in Proceedings of Supercomputing, IEEE, Piscataway, NJ, 1996, pp. 31\u2013es.","DOI":"10.1145\/369028.369096"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/0215043"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"N. P. Jouppi, D. H. Yoon, M. Ashcraft, M. Gottscho, T. B. Jablin, G. Kurian, J. Laudon, S. Li, P. Ma, X. Ma, et\u00a0al., Ten lessons from three generations shaped Google\u2019s TPUv4i, in 2021 ACM\/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), IEEE, Piscataway, NJ, 2021, pp. 1\u201314.","DOI":"10.1109\/ISCA52012.2021.00010"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.01.004"},{"key":"ref54","unstructured":"M. Karppa and P. Kaski, Engineering Boolean Matrix Multiplication for Multiple-Accelerator Shared-Memory Architectures, preprint, arXiv:1909.01554, 2019."},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1145\/3364504"},{"key":"ref56","doi-asserted-by":"crossref","unstructured":"A. Kreczmar, On memory requirements of Strassen\u2019s algorithms, in International Symposium on Mathematical Foundations of Computer Science, Springer, Berlin, 1976, pp. 404\u2013407.","DOI":"10.1007\/3-540-07854-1_206"},{"key":"ref57","doi-asserted-by":"crossref","unstructured":"A. G. Krishnan and D. Goswami, Multi-stage memory efficient Strassen\u2019s matrix multiplication on GPU, in 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC), IEEE, Piscataway, NJ, 2021, pp. 212\u2013221.","DOI":"10.1109\/HiPC53243.2021.00035"},{"key":"ref58","first-page":"275","volume":"4","author":"Kumar B.","year":"1995","journal-title":"Sci. Program."},{"key":"ref59","doi-asserted-by":"crossref","unstructured":"G. Kwasniewski, M. Kabi\u0107, M. Besta, J. VandeVondele, and R. Solc\u00e0, Red-blue pebbling revisited: Near optimal parallel matrix-matrix multiplication, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201919), Association for Computing Machinery, ACM, New York, 2019, 24.","DOI":"10.1145\/3295500.3356181"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(92)90393-O"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1976-13988-2"},{"key":"ref62","doi-asserted-by":"crossref","unstructured":"P.W. Lai, H. Arafat, V. Elango, and P. Sadayappan, Accelerating Strassen-Winograd\u2019s matrix multiplication algorithm on GPUs, in 20th Annual International Conference on High Performance Computing, IEEE, Piscataway, NJ, 2013, pp. 139\u2013148.","DOI":"10.1109\/HiPC.2013.6799109"},{"key":"ref63","doi-asserted-by":"crossref","unstructured":"F. Le Gall, Powers of tensors and fast matrix multiplication, in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 296\u2013303.","DOI":"10.1145\/2608628.2608664"},{"key":"ref64","doi-asserted-by":"crossref","unstructured":"B. Lipshitz, G. Ballard, J. Demmel, and O. Schwartz, Communication-avoiding parallel Strassen: Implementation and performance, in SC\u201912: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, IEEE, Piscataway, NJ, 2012, pp. 1\u201311.","DOI":"10.1109\/SC.2012.33"},{"key":"ref65","doi-asserted-by":"crossref","unstructured":"Q. Luo and J. B. Drake, A scalable parallel Strassen\u2019s matrix multiplication algorithm for distributed-memory computers, in Proceedings of the 1995 ACM Symposium on Applied Computing, ACM, New York, 1995, pp. 221\u2013226.","DOI":"10.1145\/315891.315965"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008264"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2020.2975185"},{"key":"ref68","doi-asserted-by":"crossref","unstructured":"R. Nissim and O. Schwartz, Revisiting the I\/O-complexity of fast matrix multiplication with recomputations, in 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, Piscataway, NJ, 2019, pp. 482\u2013490.","DOI":"10.1109\/IPDPS.2019.00058"},{"key":"ref69","doi-asserted-by":"crossref","unstructured":"V. Y. Pan, Strassen\u2019s algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations, in 19th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Long Beach, CA, 1978, pp. 166\u2013176.","DOI":"10.1109\/SFCS.1978.34"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1137\/0209027"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(82)90037-2"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1137\/0205016"},{"key":"ref73","doi-asserted-by":"crossref","unstructured":"J. Scott, O. Holtz, and O. Schwartz, Matrix multiplication I\/O-complexity by path routing, in Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2015, pp. 35\u201345.","DOI":"10.1145\/2755573.2755594"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1134\/S0965542513120129"},{"key":"ref75","unstructured":"A. V. Smirnov, Several Bilinear Algorithms for Matrix Multiplication, Technical report, 2017, https:\/\/www.researchgate.net\/publication\/313064941_Several_bilinear_algorithms_for_matrix_multiplication."},{"key":"ref76","doi-asserted-by":"crossref","unstructured":"E. Solomonik, A. Bhatele, and J. Demmel, Improving communication performance in dense linear algebra via topology aware collectives, in SC\u201911: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, Piscataway, NJ, 2011, pp. 1\u201311.","DOI":"10.1145\/2063384.2063487"},{"key":"ref77","doi-asserted-by":"crossref","unstructured":"E. Solomonik and J. Demmel, Communication-optimal parallel 2.5D matrix multiplication and lu factorization algorithms, in European Conference on Parallel Processing, Springer, Berlin, 2011, pp. 90\u2013109.","DOI":"10.1007\/978-3-642-23397-5_10"},{"key":"ref78","unstructured":"A. J. Stothers, On the Complexity of Matrix Multiplication, Ph.D. thesis, University of Edinburgh, Edingburgh, UK, 2010."},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"ref80","doi-asserted-by":"crossref","unstructured":"V. Strassen, The asymptotic spectrum of tensors and the exponent of matrix multiplication, in 27th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Angeles, CA, 1986, pp. 49\u201354.","DOI":"10.1109\/SFCS.1986.52"},{"key":"ref81","doi-asserted-by":"crossref","unstructured":"Y. Tang, Balanced partitioning of several cache-oblivious algorithms, in Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2020, pp. 575\u2013577.","DOI":"10.1145\/3350755.3400214"},{"key":"ref82","doi-asserted-by":"crossref","unstructured":"M. Thottethodi, S. Chatterjee, and A. R. Lebeck, Tuning Strassen\u2019s matrix multiplication for memory efficiency, in SC\u201998: Proceedings of the 1998 ACM\/IEEE Conference on Supercomputing, IEEE, Piscataway, NJ, 1998, pp. 36\u201336.","DOI":"10.1109\/SC.1998.10045"},{"key":"ref83","volume-title":"Numerical Linear Algebra","author":"Trefethen L. N.","year":"2022"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2"},{"key":"ref85","doi-asserted-by":"crossref","unstructured":"V. V. Williams, Multiplying matrices faster than Coppersmith-Winograd, in Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887\u2013898.","DOI":"10.1145\/2213977.2214056"},{"key":"ref86","unstructured":"S. Winograd, Private communication with R. Probert, 1976."},{"key":"ref87","doi-asserted-by":"crossref","unstructured":"D. S. Wise, Ahnentafel indexing into Morton-ordered arrays, or matrix locality for free, in European Conference on Parallel Processing, Springer, Berlin, 2000, pp. 774\u2013783.","DOI":"10.1007\/3-540-44520-X_108"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1502719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:20:53Z","timestamp":1787332853000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1502719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,15]]},"references-count":87,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/22M1502719"],"URL":"https:\/\/doi.org\/10.1137\/22m1502719","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,15]]}}}