{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T21:03:58Z","timestamp":1791407038726,"version":"4.3.3"},"reference-count":67,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2011,7,1]]},"abstract":"<jats:p>In 1981 Hong and Kung proved a lower bound on the amount of communication (amount of data moved between a small, fast memory and large, slow memory) needed to perform dense, [Formula: see text]-by-[Formula: see text] matrix multiplication using the conventional [Formula: see text] algorithm, where the input matrices were too large to fit in the small, fast memory. In 2004 Irony, Toledo, and Tiskin gave a new proof of this result and extended it to the parallel case (where communication means the amount of data moved between processors). In both cases the lower bound may be expressed as [Formula: see text], where [Formula: see text] is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization, Cholesky factorization, [Formula: see text] factorization, QR factorization, the Gram\u2013Schmidt algorithm, and algorithms for eigenvalues and singular values, i.e., essentially all direct methods of linear algebra. The proof works for dense or sparse matrices and for sequential or parallel algorithms. In addition to lower bounds on the amount of data moved (bandwidth cost), we get lower bounds on the number of messages required to move it (latency cost). We extend our lower bound technique to compositions of linear algebra operations (like computing powers of a matrix) to decide whether it is enough to call a sequence of simpler optimal algorithms (like matrix multiplication) to minimize communication, or whether we can do better. We give examples of both. We also show how to extend our lower bounds to certain graph-theoretic problems. We point out recently designed algorithms that attain many of these lower bounds.<\/jats:p>","DOI":"10.1137\/090769156","type":"journal-article","created":{"date-parts":[[2011,9,9]],"date-time":"2011-09-09T22:11:14Z","timestamp":1315606274000},"page":"866-901","source":"Crossref","is-referenced-by-count":185,"title":["Minimizing Communication in Numerical Linear Algebra"],"prefix":"10.1137","volume":"32","author":[{"given":"Grey","family":"Ballard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olga","family":"Holtz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oded","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,9,8]]},"reference":[{"key":"R1","unstructured":"E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov and D. Sorensen,\n                      LAPACK\u2019s User\u2019s Guide\n                      , SIAM, Philadelphia,  1992."},{"key":"R1","unstructured":"Also available from http:\/\/www.netlib.org\/lapack\/."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.395.0575"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/383738.383741"},{"key":"R4","unstructured":"N. Ahmed and K. Pingali, Automatic generation of block-recursive codes, in  Euro-Par \u201900: Proceedings of the 6th International Euro-Par Conference on Parallel Processing, London, UK, Springer-Verlag, Berlin, 2000, pp.\u00a0368\u2013378."},{"key":"R5","unstructured":"C. Ashcraft,  A Taxonomy of Distributed Dense LU Factorization Methods, Boeing Computer Services Technical Report ECA-TR-161, 1991."},{"key":"R6","unstructured":"C. Ashcraft, The fan-both family of column-based distributed Cholesky factorization algorithms, in\n                      Graph Theory and Sparse Matrix Computation\n                      , IMA Volumes in Mathematics and Its Applications  56, J. R. Gilbert,  A. George and  J. W. H. Liu, eds. Springer-Verlag, Berlin,  1993, pp.\u00a0159\u2013190"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"R8","unstructured":"M. A. Bender, G. S. Brodal, R. Fagerberg, R. Jacob and E. Vicari, Optimal sparse matrix dense vector multiplication in the I\/O-model, in  SPAA \u201907: Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 2007, pp.\u00a061\u201370."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384573"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384585"},{"key":"R11","unstructured":"L. S. Blackford, J. Choi, A. Cleary, E. DAzevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker and R. C. Whaley,\n                      ScaLAPACK Users\u2019 Guide\n                      , SIAM, Philadelphia,  1997."},{"key":"R11","unstructured":"Also available from http:\/\/www.netlib.org\/scalapack\/."},{"key":"R12","first-page":"1","volume":"15","author":"Blackford L. S.","year":"2001","journal-title":"Int. J. Supercomput. Appl. High Perform. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0890-2720","issn-type":"print"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567807"},{"key":"R14","unstructured":"G. Ballard, J. Demmel and I. Dumitriu,  Communication-Optimal Parallel and Sequential Eigenvalue and Singular Value Algorithms, EECS Technical Report EECS-2011-14, University of California\u2013Berkeley, 2011."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/090760969"},{"key":"R16","unstructured":"G. Ballard, J. Demmel, O. Holtz and O. Schwartz,  Graph expansion and communication costs of fast matrix multiplication, in Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011), 2011, to appear."},{"key":"R17","unstructured":"G. Ballard, J. Demmel, O. Holtz and O. Schwartz,  Minimizing Communication in Linear Algebra, EECS Technical Report EECS-2011-15, University of California\u2013Berkeley, 2011."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0428694-0"},{"key":"R19","unstructured":"A. Buttari, J. Langou, J. Kurzak and J. J. Dongarra,  A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures, Technical Report 191, LAPACK Working Note, 2007."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365736"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365735"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0908009"},{"key":"R23","unstructured":"Y. D. Burago and V. A. Zalgaller,\n                      Geometric Inequalities\n                      , Grundlehren Math. Wiss.  285, Springer, Berlin, 1988."},{"key":"R24","unstructured":"L. Cannon,  A Cellular Computer to Implement the Kalman Filter Algorithm, Ph.D. thesis, Montana State University, Bozeman, MT, 1969."},{"key":"R25","unstructured":"T. Cormen, C. Leiserson, R. Rivest and C. Stein,\n                      Introduction to Algorithms\n                      , 2nd ed., MIT Press, Cambridge, MA,  2001."},{"key":"R26","unstructured":"R. A. Chowdhury and V. Ramachandran, Cache-oblivious dynamic programming, in  Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, ACM, New York, 2006, pp.\u00a0591\u2013600."},{"key":"R27","unstructured":"P.Y. David, J. Demmel, L. Grigori and S. Peyronnet, Brief announcement: Lower bounds on communication for sparse Cholesky factorization of a model problem, in  Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2010."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-007-0114-x"},{"key":"R29","unstructured":"J. Demmel,  CS 267 Course Notes: Applications of Parallel Processing, Computer Science Division, University of California, 1996."},{"key":"R29","unstructured":"http:\/\/www.cs.berkeley.edu\/\u223cdemmel\/cs267."},{"key":"R30","unstructured":"J. Demmel,\n                      Applied Numerical Linear Algebra\n                      , SIAM, Philadelphia,  1997."},{"key":"R31","unstructured":"J. Demmel, L. Grigori, M. Hoemmen and J. Langou,  Communication-Optimal Parallel and Sequential QR and LU Factorizations, EECS Technical Report EECS-2008-89, University of California\u2013Berkeley, 2008, to appear in SIAM. J. Sci. Comput."},{"key":"R32","unstructured":"J. Demmel, L. Grigori, M. Hoemmen and J. Langou,  Implementing communication-optimal parallel and sequential QR and LU factorizations, 2008, available from http:\/\/arxiv.org\/abs\/0809.2407."},{"key":"R33","unstructured":"J. Demmel, L. Grigori and H. Xiang, Communication\u2014Avoiding Gaussian elimination,  Supercomputing 08, ACM\/IEEE, Austin, TX, 2008."},{"key":"R34","unstructured":"J. Demmel, L. Grigori and H. Xiang,  CALU: A Communication Optimal LU Factorization Algorithm, EECS Technical Report EECS-2010-29, University of California\u2013Berkeley, 2010, submitted to SIAM J. Matrix Anal. Appl."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/0210049"},{"key":"R36","unstructured":"E. Elmroth and F. Gustavson, New serial and parallel recursive QR factorization algorithms for SMP systems, in\n                      Applied Parallel Computing. Large Scale Scientific and Industrial Problems\n                      , Lecture Notes in Comput. Sci.  1541, B. K\u00e5gstr\u00f6met al., eds. Springer, Berlin,  1998, pp.\u00a0120\u2013128."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1147\/rd.444.0605"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503428693"},{"key":"R39","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop and S. Ramachandran, Cache-Oblivious algorithms, in  Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1999, pp.\u00a0285\u2013297."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/966049.781525"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1145\/1055531.1055534"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1145\/504210.504213"},{"key":"R44","unstructured":"G. H. Golub, R. J. Plemmons and A. Sameh, Parallel block schemes for large-scale least-squares computations, in\n                      High-Speed Computing: Scientific Applications and Algorithm Design\n                      University of Illinois Press, Champaign, IL,  1988, pp.\u00a0171\u2013179."},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396660"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1147\/rd.416.0737"},{"key":"R47","unstructured":"G. Golub and C. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., Johns Hopkins University Press, Baltimore, MD,  1996."},{"key":"R48","unstructured":"J. W. Hong and H. T. Kung, I\/O complexity: The red-blue pebble game, in  Proceedings of the 13th Annual ACM Symposium on Theory of Computing, ACM, New York, 1981, pp.\u00a0326\u2013333."},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/0710033"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626402000847"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1949-09320-5"},{"key":"R53","unstructured":"J. P. Michael, M. Penner and V. K. Prasanna, Optimizing graph algorithms for improved cache performance, in  Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2002), Fort Lauderdale, FL, 2002, pp.\u00a0769\u2013782."},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008264"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1137\/0913042"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(86)90174-6"},{"key":"R57","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , PWS Publishing Co., Boston,  1996."},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030842"},{"key":"R59","unstructured":"E. Solomonik and J. Demmel,  Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms, EECS Technical Report EECS-2011-10, University of California\u2013Berkeley, 2011, to appear in EURO-PAR 2011."},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1137\/0910005"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896297744"},{"key":"R62","unstructured":"R. van de Geijn,  PLAPACK: Parallel Linear Algebra Package, www.cs.utexas.edu\/users\/plapack."},{"key":"R63","unstructured":"R. Vuduc, J. Demmel and K. Yelick, OSKI: A library of automatically tuned sparse matrix kernels, in  Proceedings of SciDAC 2005, J. of Physics: Conference Series, Institute of Physics Publishing, London, 2005."},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077466"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090769156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:19:13Z","timestamp":1787325553000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090769156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,1]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7,1]]}},"alternative-id":["10.1137\/090769156"],"URL":"https:\/\/doi.org\/10.1137\/090769156","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,1]]}}}