{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T21:28:06Z","timestamp":1791235686763,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>We present parallel and sequential dense QR factorization algorithms that are both optimal (up to polylogarithmic factors) in the amount of communication they perform and just as stable as Householder QR. We prove optimality by deriving new lower bounds for the number of multiplications done by \u201cnon-Strassen-like\u201d QR, and using these in known communication lower bounds that are proportional to the number of multiplications. We not only show that our QR algorithms attain these lower bounds (up to polylogarithmic factors), but that existing LAPACK and ScaLAPACK algorithms perform asymptotically more communication. We derive analogous communication lower bounds for LU factorization and point out recent LU algorithms in the literature that attain at least some of these lower bounds. The sequential and parallel QR algorithms for tall and skinny matrices lead to significant speedups in practice over some of the existing algorithms, including LAPACK and ScaLAPACK, for example, up to 6.7 times over ScaLAPACK. A performance model for the parallel algorithm for general rectangular matrices predicts significant speedups over ScaLAPACK.<\/jats:p>","DOI":"10.1137\/080731992","type":"journal-article","created":{"date-parts":[[2012,2,2]],"date-time":"2012-02-02T18:44:07Z","timestamp":1328208247000},"page":"A206-A239","source":"Crossref","is-referenced-by-count":303,"title":["Communication-optimal Parallel and Sequential QR and LU Factorizations"],"prefix":"10.1137","volume":"34","author":[{"given":"James","family":"Demmel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura","family":"Grigori","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Hoemmen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julien","family":"Langou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Blackford, and D. Sorensen,\n                      LAPACK Users' Guide\n                      , 3rd ed., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719604"},{"key":"R2","unstructured":"M. Baboulin, L. Giraud, S. Gratton, and J. Langou,\n                      Parallel Tools for Solving Incremental Dense Least Squares Problems. Application to Space Geodesy\n                      , Technical report UT-CS-06-582, University of Tennessee, Knoxville, 2006."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/838250.838257"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Z. Bai and D. Day,\n                      Block Arnoldi method\n                      , in Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Z. Bai, J. W. Demmel, J. J. Dongarra, A. Ruhe, and H. van der Vorst, eds., SIAM, Philadelphia, 2000, pp. 196\u2013204.","DOI":"10.1137\/1.9780898719581"},{"key":"R5","unstructured":"C. G. Baker, U. L. Hetmaniuk, R. B. Lehoucq, and H. K. Thornquist,\n                      Anasazi webpage\n                      , http:\/\/trilinos.sandia.gov\/packages\/anasazi."},{"key":"R6","unstructured":"G. Ballard, J. Demmel, O. Holtz, and O. Schwartz,\n                      Minimizing Communication in Numerical Linear Algebra\n                      . Technical report UCB\/EECS-2011-15, University of California, Berkeley, CA, 2011."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. W. Demmel, I. Dhillon, J. J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley,\n                      ScaLAPACK Users' Guide\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9780898719642"},{"key":"R9","unstructured":"A. Buttari, J. Langou, J. Kurzak, and J. J. Dongarra,\n                      A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures\n                      , Technical report UT-CS-07-600, University of Tennessee, Knoxville, 2007."},{"key":"R10","unstructured":"A. Buttari, J. Langou, J. Kurzak, and J. J. Dongarra,\n                      Parallel tiled QR factorization for multicore architectures\n                      , Technical report UT-CS-07-598, University of Tennessee, Knoxville, 2007."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389871"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"R. D. D. Cunha, D. Becker, and J. C. Patterson,\n                      New parallel (rank-revealing) QR factorization algorithms\n                      , in Proceedings of the Euro-Par 2002. Parallel Processing: Eighth International Euro-Par Conference, Paderborn, Germany, 2002.","DOI":"10.1007\/3-540-45706-2_94"},{"key":"R14","unstructured":"E. F. D'Azevedo and J. J. Dongarra,\n                      The Design and Implementation of the Parallel Out-of-Core ScaLAPACK LU, QR, and Cholesky Factorization Routines\n                      , Technical report 118 CS-97-247, University of Tennessee, Knoxville, 1997."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/1096-9128(20001225)12:15<1481::AID-CPE540>3.0.CO;2-V"},{"key":"R16","unstructured":"J. W. Demmel, L. Grigori, M. Hoemmen, and J. Langou,\n                      Communication-Avoiding Parallel and Sequential QR and LU Factorizations: Theory and Practice\n                      , Technical report UCB\/EECS-2008-89, University of California, Berkeley, CA, 2008."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/080725763"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"J. W. Demmel, M. Hoemmen, M. Mohiyuddin, and K. A. Yelick,\n                      Minimizing communication in sparse matrix solvers\n                      , in Proceedings of the 2009 ACM\/IEEE Conference on Supercomputing, New York, 2009.","DOI":"10.1109\/IPDPS.2008.4536305"},{"key":"R19","unstructured":"J. W. Demmel,\n                      Trading Off Parallelism and Numerical Stability\n                      , Technical report UT-CS-92-179, University of Tennessee, Knoxville, 1992."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"E. Elmroth and F. Gustavson,\n                      New serial and parallel recursive QR factorization algorithms for SMP systems\n                      , in Proceedings of the Fourth International Workshop on AppliedParallel Computing, Large Scale Scientific and Industrial Problems, B. K\u00e5gstr\u00f6m, E. Elmroth, J. Dongarra, and J. Wasniewski, eds., Lecture Notes in Comput. Sci. 1541, Springer, New York, 1998, pp. 120\u2013128.","DOI":"10.1007\/BFb0095328"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1147\/rd.444.0605"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/966049.781525"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00529-0"},{"key":"R24","unstructured":"G. H. Golub, R. J. Plemmons, and A. Sameh,\n                      Parallel block schemes for large-scale least-squares computations\n                      , in High-Speed Computing: Scientific Applications and Algorithm Design, R. B. Wilhelmson, ed., University of Illinois Press, Chicago, IL, 1988, pp. 171\u2013179."},{"key":"R25","unstructured":"S. L. Graham, M. Snir, and C. A. Patterson, eds.\n                      Getting Up to Speed: The Future of Supercomputing\n                      , National Academies Press, Washington, D.C., 2005."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"L. Grigori, J. W. Demmel, and H. Xiang,\n                      Communication avoiding Gaussian elimination\n                      , Proceedings of the ACM\/IEEE SC08 Conference, 2008.","DOI":"10.1109\/SC.2008.5214287"},{"key":"R27","unstructured":"L. Grigori, J. W. Demmel, and H. Xiang,\n                      CALU: A Communication Optimal LU Factorization Algorithm\n                      , Technical report UCB-EECS-2010-29, INRIA, 2010."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/1055531.1055534"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2006.02.007"},{"key":"R30","unstructured":"M. Hoemmen,\n                      Communication-Avoiding Krylov Subspace Methods\n                      , Ph.D.  thesis, EECS Department, University of California, Berkeley, CA, 2010."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"J. W. Hong and H. T. Kung,\n                      I\/O complexity: The red-blue pebble game\n                      , in STOC '81: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, New York, 1981, pp. 326\u2013333.","DOI":"10.1145\/800076.802486"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"A. V. Knyazev, M. Argentati, I. Lashuk, and E. E. Ovtchinnikov,\n                      Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in HYPRE and PETSc\n                      , Technical report UCDHSC-CCM-251P, University of California, Davis, 2007.","DOI":"10.1137\/060661624"},{"key":"R34","unstructured":"A. V. Knyazev,\n                      BLOPEX\n                      , http:\/\/www-math.cudenver.edu\/~aknyazev\/software\/BLOPEX."},{"key":"R35","unstructured":"J. Kurzak and J. J. Dongarra,\n                      QR Factorization for the CELL Processor\n                      , Technical report UT-CS-08-616, University of Tennessee, Knoxville, 2008."},{"key":"R36","unstructured":"R. Lehoucq and K. Maschhoff,\n                      Block Arnoldi method\n                      , in Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Z. Bai, J. W. Demmel, J. J. Dongarra, A. Ruhe, and H. van der Vorst, eds., SIAM, Philadelphia, 2000, pp. 185\u2013187."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327118"},{"key":"R38","unstructured":"O. Marques,\n                      BLZPACK\n                      , http:\/\/crd.lbl.gov\/~osni."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"R. Nishtala, G. Alm\u00e1si, and C. Ca\u015fcaval,\n                      Performance without pain = productivity: Data layout and collective communication in UPC\n                      , in Proceedings of the ACM SIGPLAN 2008 Symposium on Principles and Practice of Parallel Programming, 2008.","DOI":"10.1145\/1345206.1345224"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90247-5"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/0910067"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"G. Quintana-Ort\u00ed, E. S. Quintana-Ort\u00ed, E. Chan, F. G. V. Zee, and R. A. van de Geijn,\n                      Scheduling of QR factorization algorithms on SMP and multi-core architectures\n                      , in Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, Toulouse, France, 2008.","DOI":"10.1109\/PDP.2008.37"},{"key":"R43","unstructured":"E. Rabani and S. Toledo,\n                      Out-of-core SVD and QR decompositions\n                      , in Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing, Norfolk, VA, 2001."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402147"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1137\/0910005"},{"key":"R46","unstructured":"A. Stathopoulos,\n                      PRIMME\n                      , http:\/\/www.cs.wm.edu\/~andreas\/software."},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896297744"},{"key":"R48","unstructured":"B. Vital,\n                      \u00c9tude de quelques m\u00e9thodes de r\u00e9solution de probl\u00e8mes lin\u00e9aires de grande taille sur multiprocesseur\n                      , Ph.D. thesis, Universit\u00e9 de Rennes I, Rennes, France, 1990."},{"key":"R49","unstructured":"K. Wu and H. D. Simon,\n                      TRLAN\n                      , http:\/\/crd.lbl.gov\/~kewu\/ps\/trlan_.html."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080731992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:41:12Z","timestamp":1787330472000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080731992"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/080731992"],"URL":"https:\/\/doi.org\/10.1137\/080731992","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}