{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:13:43Z","timestamp":1787382823714,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network connecting processors (in the parallel case). Communication costs often dominate arithmetic costs, so it is of interest to design algorithms minimizing communication. In this paper we first extend known lower bounds on the communication cost (both for bandwidth and for latency) of conventional ($O(n^3)$) matrix multiplication to Cholesky factorization, which is used for solving dense symmetric positive definite linear systems. Second, we compare the costs of various Cholesky decomposition implementations to these lower bounds and identify the algorithms and data structures that attain them. In the sequential case, we consider both the two-level and hierarchical memory models. Combined with prior results in [J. Demmel et al., Communication-optimal Parallel and Sequential QR and LU Factorizations, Technical report EECS-2008-89, University of California, Berkeley, CA, 2008], [J. Demmel et al., Implementing Communication-optimal Parallel and Sequential QR and LU Factorizations, SIAM. J. Sci. Comp., submitted], and [J. Demmel, L. Grigori, and H. Xiang, Communication-avoiding Gaussian Elimination, Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing, 2008] this gives a set of communication-optimal algorithms for $O(n^3)$ implementations of the three basic factorizations of dense linear algebra: LU with pivoting, QR, and Cholesky. But it goes beyond this prior work on sequential LU by optimizing communication for any number of levels of memory hierarchy.<\/jats:p>","DOI":"10.1137\/090760969","type":"journal-article","created":{"date-parts":[[2010,12,2]],"date-time":"2010-12-02T18:09:05Z","timestamp":1291313345000},"page":"3495-3523","source":"Crossref","is-referenced-by-count":27,"title":["Communication-optimal Parallel and Sequential Cholesky Decomposition"],"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":[[2010,12,2]]},"reference":[{"key":"R1","unstructured":"IEEE standard for floating-point arithmetic\n                      , IEEE Std. 754-2008, (2008), pp. 1\u201358."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"N. Ahmed and K. Pingali,\n                      Automatic generation of block-recursive codes\n                      , in Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing, London, UK, 2000, Springer-Verlag, pp. 368\u2013378.","DOI":"10.1007\/3-540-44520-X_48"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/383738.383741"},{"key":"R5","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. Ostrouchov, and D. Sorensen,\n                      LAPACK Users Guide\n                      , 3rd ed., SIAM, Philadelphia, 1999; also available from http:\/\/www.netlib.org\/lapack\/.","DOI":"10.1137\/1.9780898719604"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Bader, R. Franz, S. Guenther, and A. Heinecke,\n                      Hardware-oriented implementation of cache oblivious matrix operations based on space-filling curves\n                      , in Parallel Processing and Applied Mathematics, 7th International Conference, PPAM 2007, Lecture Notes in Comput. Sci. 4967, Springer-Verlag, New York, 2008, pp. 628\u2013638.","DOI":"10.1007\/978-3-540-68111-3_66"},{"key":"R7","unstructured":"G. Ballard, J. Demmel, O. Holtz, and O. Schwartz,\n                      Minimizing communication in linear algebra\n                      , SIAM J. Matrix Anal. Appl., submitted; also available at http:\/\/arxiv.org\/abs\/0905.2485."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"G. Ballard, J. Demmel, O. Holtz, and O. Schwartz,\n                      Communication-optimal parallel and sequential Cholesky decomposition\n                      , in SPAA '09: Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures, 2009, pp. 245\u2013252.","DOI":"10.1145\/1583991.1584054"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9285-4"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/06067256X"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley,\n                      ScaLAPACK Users' Guide\n                      , SIAM, Philadelphia, 1997; also available from http:\/\/www.netlib.org\/scalapack\/.","DOI":"10.1137\/1.9780898719642"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"R. A. Chowdhury and V. Ramachandran,\n                      Cache-oblivious dynamic programming\n                      , in SODA '06: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, 2006, ACM, pp. 591\u2013600.","DOI":"10.1145\/1109557.1109622"},{"key":"R13","unstructured":"J. Demmel, L. Grigori, M. Hoemmen, and J. Langou,\n                      Communication-optimal Parallel and Sequential QR and LU Factorizations\n                      , Technical report EECS-2008-89, University of California Berkeley, Berkeley, CA, 2008, SIAM. J. Sci. Comput., submitted."},{"key":"R14","unstructured":"J. Demmel, L. Grigori, M. Hoemmen, and J. Langou,\n                      Implementing communication-optimal parallel and sequential QR and LU factorizations\n                      , SIAM. J. Sci. Comput., submitted."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"J. Demmel, L. Grigori, and H. Xiang,\n                      Communication-avoiding Gaussian elimination\n                      , in Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing, 2008.","DOI":"10.1109\/SC.2008.5214287"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503428693"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran,\n                      Cache-oblivious algorithms\n                      , in FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, Washington, DC, 1999, IEEE Computer Society, pp. 285\u2013297.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"R18","unstructured":"S. L. Graham, M. Snir, and C. A. Patterson, eds.\n                      Getting up to Speed: The Future of Supercomputing\n                      , Report of the National Research Council of the National Academies of Sciences, The National Academies Press, Washington, D.C., 2004; also available online from http:\/\/www.nap.edu."},{"key":"R19","unstructured":"L. Grigori.\n                      Personal communication\n                      , 2009."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1147\/rd.416.0737"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"F. G. Gustavson and I. Jonsson,\n                      High performance Cholesky factorization via blocking and recursion that uses minimal storage\n                      , in PARA '00: Proceedings of the 5th International Workshop on Applied Parallel Computing, New Paradigms for HPC in Industry and Academia, London, UK, 2001, Springer-Verlag, pp. 82\u201391.","DOI":"10.1007\/3-540-70734-4_12"},{"key":"R22","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":"R23","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":"R24","unstructured":"D. Irony and S. Toledo,\n                      Communication-efficient parallel dense LU using a 3-dimensional approach\n                      , in Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing, 2001."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"J. E. Savage,\n                      Extending the Hong-Kung model to memory hierarchies\n                      , in COCOON, 1995, pp. 270\u2013281.","DOI":"10.1007\/BFb0030842"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"I. Simecek and P. Tvrdik,\n                      Analytical model for analysis of cache behavior during Cholesky factorization and its variants\n                      , in ICPPW '04: Proceedings of the 2004 International Conference on Parallel Processing Workshops, Washington, DC, 2004, IEEE Computer Society, pp. 190\u2013197.","DOI":"10.1109\/ICPPW.2004.1328017"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896297744"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"D. Wise,\n                      Ahnentafel indexing into Morton-ordered arrays, or matrix locality for free\n                      , in Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing, London, UK, 2000, Springer-Verlag, pp. 774\u2013783.","DOI":"10.1007\/3-540-44520-X_108"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"C.Q. Yang and B.P. Miller,\n                      Critical path analysis for the execution of parallel and distributed programs\n                      , in Proceedings from the 8th International Conference on Distributed Computing Systems, IEEE Computer Society, 1988, pp. 366\u2013373.","DOI":"10.1109\/DCS.1988.12538"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090760969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:35:20Z","timestamp":1787330120000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090760969"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090760969"],"URL":"https:\/\/doi.org\/10.1137\/090760969","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}