{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:45:14Z","timestamp":1787330714192,"version":"build-2736575974"},"reference-count":37,"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":[[2014,1]]},"abstract":"<jats:p>We describe and analyze a novel symmetric triangular factorization algorithm. The algorithm is essentially a block version of Aasen's triangular tridiagonalization. It factors a dense symmetric matrix $A$ as the product $A=PLTL^{T}P^{T},$ where $P$ is a permutation matrix, $L$ is lower triangular, and $T$ is block tridiagonal and banded. The algorithm is the first symmetric-indefinite communication-avoiding factorization: it performs an asymptotically optimal amount of communication in a two-level memory hierarchy for almost any cache-line size. Adaptations of the algorithm to parallel computers are likely to be communication efficient as well; one such adaptation has been recently published. The current paper describes the algorithm, proves that it is numerically stable, and proves that it is communication optimal.<\/jats:p>","DOI":"10.1137\/130929060","type":"journal-article","created":{"date-parts":[[2014,11,13]],"date-time":"2014-11-13T12:42:31Z","timestamp":1415882551000},"page":"1364-1406","source":"Crossref","is-referenced-by-count":12,"title":["Communication-Avoiding Symmetric-Indefinite Factorization"],"prefix":"10.1137","volume":"35","author":[{"given":"Grey","family":"Ballard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dulceneia","family":"Becker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jack","family":"Dongarra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Druinsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Inon","family":"Peled","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oded","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ichitaro","family":"Yamazaki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01931804"},{"key":"atypb2","unstructured":"S. Amarasinghe, M. Hall, R. Lethin, K. Pingali, D. Quinlan, V. Sarkar, J. Shalf, R. Lucas, K. Yelick, P. Balaji, P. C. Diniz, A. Koniges, M. Snir, and S. R. Sachs,\n                      Exascale Programming Challenges\n                      , Report of the 2011 Workshop on Exascale Programming Challenges, Marina del Rey, 2011."},{"key":"atypb3","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                      , 3rd ed., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719604"},{"key":"atypb4","unstructured":"G. Ballard,\n                      Avoiding Communication in Dense Linear Algebra\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, 2013."},{"key":"atypb5","first-page":"895","author":"Ballard G.","year":"2013","journal-title":"Proceedings of the IEEE 27th International Parallel & Distributed Processing Symposium (IPDPS)"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"atypb7","first-page":"232","author":"Ballard G.","year":"2013","journal-title":"Algorithms and Architectures"},{"key":"atypb8","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.","DOI":"10.1137\/1.9780898719642"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0428694-0"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/240455.240477"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"atypb13","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran,\n                      Cache-oblivious algorithms\n                      , in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS '99), New York, 1999."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/100788926"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1147\/rd.416.0737"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895290371"},{"key":"atypb17","first-page":"47","author":"Higham N. J.","year":"1999","journal-title":"Heidelberg"},{"key":"atypb18","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":"atypb19","doi-asserted-by":"crossref","unstructured":"J.W. Hong and H. T. Kung,\n                      I\/O complexity: The red-blue pebble game\n                      , in Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981, pp. 326-333.","DOI":"10.1145\/800076.802486"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/040610106"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/nla.529"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/120863691"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165306"},{"key":"atypb25","first-page":"386","volume":"10","author":"Parlett B. N.","year":"1970","journal-title":"BIT"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/2427023.2427030"},{"key":"atypb27","unstructured":"J. Poulson, R. A. van de Geijn, and J. Bennighof,\n                      (Parallel) Algorithms for Two-Sided Triangular Solves and Matrix Multiplication\n                      , unpublished, 2012."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/2049673.2049674"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/1916461.1916462"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436202"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"M. P. Sears, K. Stanley, and G. Henry,\n                      Application of a high performance parallel eigensolver to electronic structure calculations\n                      , in Proceedings of the IEEE\/ACM Conference on Supercomputing, 1998 (CD-ROM).","DOI":"10.1109\/SC.1998.10037"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"B. T. Smith, J. M. Boyle, J. J. Dongarra, B. S. Garbow, Y. Ikebe, V. C. Klema, and C. B. Moler,\n                      Matrix Eigensystem Routines-EISPACK Guide\n                      , 2nd ed., Springer-Verlag, 1976.","DOI":"10.1007\/3-540-07546-1"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896297744"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/0611023"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"J. S. Vitter and E. A. M. Shriver,\n                      Optimal disk I\/O with parallel block transfer\n                      , in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), 1990, pp. 159-169.","DOI":"10.1145\/100216.100234"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185207"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130929060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:22:36Z","timestamp":1787329356000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130929060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/130929060"],"URL":"https:\/\/doi.org\/10.1137\/130929060","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}