{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T00:00:57Z","timestamp":1791331257208,"version":"4.3.1"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2011,10]]},"abstract":"<jats:p>Since the cost of communication (moving data) greatly exceeds the cost of doing arithmetic on current and future computing platforms, we are motivated to devise algorithms that communicate as little as possible, even if they do slightly more arithmetic, and as long as they still get the right answer. This paper is about getting the right answer for such an algorithm. It discusses CALU, a communication avoiding LU factorization algorithm based on a new pivoting strategy, that we refer to as tournament pivoting. The reason to consider CALU is that it does an optimal amount of communication, and asymptotically less than Gaussian elimination with partial pivoting (GEPP), and so will be much faster on platforms where communication is expensive, as shown in previous work. We show that the Schur complement obtained after each step of performing CALU on a matrix A is the same as the Schur complement obtained after performing GEPP on a larger matrix whose entries are the same as the entries of A (sometimes slightly perturbed) and zeros. More generally, the entire CALU process is equivalent to GEPP on a large, but very sparse matrix, formed by entries of A and zeros. Hence we expect that CALU will behave as GEPP and it will also be very stable in practice. In addition, extensive experiments on random matrices and a set of special matrices show that CALU is stable in practice. The upper bound on the growth factor of CALU is worse than that of GEPP. However, there are Wilkinson-like matrices for which GEPP has exponential growth factor, but not CALU, and vice-versa.<\/jats:p>","DOI":"10.1137\/100788926","type":"journal-article","created":{"date-parts":[[2011,11,10]],"date-time":"2011-11-10T18:09:16Z","timestamp":1320948556000},"page":"1317-1350","source":"Crossref","is-referenced-by-count":64,"title":["CALU: A Communication Optimal LU Factorization Algorithm"],"prefix":"10.1137","volume":"32","author":[{"given":"Laura","family":"Grigori","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James W.","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hua","family":"Xiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,11,10]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen,\n                      LAPACK Users' Guide\n                      , SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719604"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/3.1.28"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.10.002"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1155\/1996\/483083"},{"key":"R6","unstructured":"J. Demmel, L. Grigori, M. Hoemmen, and J. Langou,\n                      Communication-Optimal Parallel and Sequential QR and LU Factorizations\n                      , Technical report UCB\/EECS-2008-89, UC Berkeley, Berkeley, CA, 2008."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J. W. Demmel,\n                      Applied Numerical Linear Algebra\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611971446"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"S. Donfack, L. Grigori, and A. Kumar Gupta,\n                      Adapting communication-avoiding LU and QR factorizations to multicore architectures\n                      , Proceedings of IPDPS, 2010.","DOI":"10.1109\/IPDPS.2010.5470348"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.728"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"T. Endo and K. Taura,\n                      Highly Latency Tolerant Gaussian Elimination\n                      , in Proceedings of 6th IEEE\/ACM International Workshop on Grid Computing, 2005, pp. 91\u201398.","DOI":"10.1109\/GRID.2005.1542729"},{"key":"R11","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":"R12","unstructured":"L. Grigori, J. W. Demmel, and H. Xiang,\n                      CALU: A Communication Optimal LU Factorization Algorithm\n                      , Technical report UCB\/EECS-2010-29, EECS Department, University of California, Berkeley, Berkeley, CA, 2010."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1147\/rd.416.0737"},{"key":"R14","unstructured":"N. J. Higham,\n                      The Matrix Function Toolbox\n                      ; available online at http:\/\/www.ma.man.ac.uk\/~higham\/mftoolbox."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0610012"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"N. J. Higham,\n                      Accuracy and Stability of Numerical Algorithms\n                      , 2nd ed., SIAM, Philadelphia 2002.","DOI":"10.1137\/1.9780898718027"},{"key":"R17","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 Thirteenth Annual ACM Symposium on Theory of Computing, New York, 1981, ACM, pp. 326\u2013333.","DOI":"10.1145\/800076.802486"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"T. Joffrain, E. S. Quintana-Ort\u00ed, and R. A. van de Geijn,\n                      Rapid development of high-performance out-of-core solvers\n                      , in Proceedings of PARA 2004, Lecture Notes in Comput. Sci. 3732, Springer-Verlag, Berlin, Heidelberg, 2005, pp. 413\u2013422.","DOI":"10.1007\/11558958_49"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/1377612.1377615"},{"key":"R21","unstructured":"G. Quintana-Orti, E. S. Quintana-Orti, E. Chan, F. G. Van Zee, and R. van de Geijn,\n                      Programming Algorithms-By-Blocks for Matrix Computations on Multithreaded Architectures\n                      , Technical report TR-08-04, University of Texas at Austin, Austin, TX, 2008."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1980-0572859-4"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676570"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896297744"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2009.12.005"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0611023"},{"key":"R27","unstructured":"V. Volkov,\n                      Private communication\n                      ."},{"key":"R28","unstructured":"E. L. Yip,\n                      Subroutines for Out of Core Solutions of Large Complex Linear Systems\n                      , Technical report NASA-CR-159142, NASA, Washington, DC, 1979."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100788926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:20:19Z","timestamp":1787325619000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100788926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1137\/100788926"],"URL":"https:\/\/doi.org\/10.1137\/100788926","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10]]}}}