{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T07:20:41Z","timestamp":1768029641879,"version":"3.49.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,2,18]],"date-time":"2016-02-18T00:00:00Z","timestamp":1455753600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Center for Future Architecture Research"},{"name":"Lockheed Martin Corporation"},{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000015","name":"US DOE","doi-asserted-by":"crossref","award":["DE-SC0003959, DESC0004938, DE-SC0005136, DE-SC0010200, DESC0008700, DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-SC0003959, DESC0004938, DE-SC0005136, DE-SC0010200, DESC0008700, DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"name":"U.S. Department of Energy Contract","award":["DE-AC04-94AL85000"],"award-info":[{"award-number":["DE-AC04-94AL85000"]}]},{"name":"Microsoft","award":["024263"],"award-info":[{"award-number":["024263"]}]},{"name":"ParLab"},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR0011-12-2-0016"],"award-info":[{"award-number":["HR0011-12-2-0016"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Math Works"},{"name":"NSF","award":["ACl-1339676, OCl-1032639"],"award-info":[{"award-number":["ACl-1339676, OCl-1032639"]}]},{"name":"Intel","award":["024894"],"award-info":[{"award-number":["024894"]}]},{"name":"STARnet"},{"DOI":"10.13039\/100013765","name":"National Instruments","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100013765","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Sandia National Laboratories Truman Fellowship in National Security Science and Engineering"},{"name":"Samsung"},{"name":"UC Discovery","award":["DlG07-10227"],"award-info":[{"award-number":["DlG07-10227"]}]},{"DOI":"10.13039\/100004356","name":"Nokia","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100004356","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007065","name":"NVIDIA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007065","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Sandia Corporation"},{"name":"Oracle"},{"DOI":"10.13039\/100000028","name":"Semiconductor Research Corporation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000028","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007245","name":"MARCO","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007245","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2015,2,18]]},"abstract":"<jats:p>The running time of an algorithm depends on both arithmetic and communication (i.e., data movement) costs, and the relative costs of communication are growing over time. In this work, we present sequential and distributed-memory parallel algorithms for tridiagonalizing full symmetric and symmetric band matrices that asymptotically reduce communication compared to previous approaches.<\/jats:p>\n                  <jats:p>The tridiagonalization of a symmetric band matrix is a key kernel in solving the symmetric eigenvalue problem for both full and band matrices. In order to preserve structure, tridiagonalization routines use annihilate-and-chase procedures that previously have suffered from poor data locality and high parallel latency cost. We improve both by reorganizing the computation and obtain asymptotic improvements. We also propose new algorithms for reducing a full symmetric matrix to band form in a communication-efficient manner. In this article, we consider the cases of computing eigenvalues only and of computing eigenvalues and all eigenvectors.<\/jats:p>","DOI":"10.1145\/2686877","type":"journal-article","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T10:32:19Z","timestamp":1424687539000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Avoiding Communication in Successive Band Reduction"],"prefix":"10.1145","volume":"1","author":[{"given":"Grey","family":"Ballard","sequence":"first","affiliation":[{"name":"University of California, Berkeley and Sandia National Laboratories"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"Nicholas","family":"Knight","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]}],"member":"320","published-online":{"date-parts":[[2015,2,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","unstructured":"Agullo E. Dongarra J. Hadri B. Kurzak J. Langou J. Langou J. Ltaief H. Luszczek P. and Yarkhan A. 2009. PLASMA Users' Guide. http:\/\/icl.cs.utk.edu\/plasma\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/130639"},{"key":"e_1_2_1_4_1","unstructured":"Auckenthaler T. 2012. Highly scalable eigensolvers for petaflop applications. Ph.D. thesis Fakult\u00e4t f\u00fcr Informatik Technische Universit\u00e4t M\u00fcnchen."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.05.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2011.05.002"},{"key":"e_1_2_1_7_1","unstructured":"Ballard G. Demmel J. and Dumitriu I. 2011a. Communication-optimal parallel and sequential eigenvalue and singular value algorithms. EECS Tech. Rep. EECS-2011-14 University of California Berkeley."},{"key":"e_1_2_1_8_1","unstructured":"Ballard G. Demmel J. Grigori L. Jacquelin M. Nguyen H. and Solomonik E. 2013a. Reconstructing householder vectors from tall-skinny QR. Tech. Rep. UCB\/EECS-2013-175 EECS Department University of California Berkeley."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145822"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486198"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02162154"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882792.1882839"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Conference on Scalable High-Performance Computing. IEEE, 23--27","author":"Bischof C.","unstructured":"Bischof, C., Lang, B., and Sun, X. 1994. Parallel tridiagonalization through two-step band reduction. In Proceedings of the Conference on Scalable High-Performance Computing. IEEE, 23--27."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365736"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365735"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing.","volume":"1","author":"Bischof C.","unstructured":"Bischof, C., Marques, M., and Sun, X. 1993. Parallel bandreduction and tridiagonalization. In Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing. Vol. 1, SIAM, 383--390."},{"key":"e_1_2_1_18_1","volume-title":"Tech. Rep. MCS-P298-0392, Argonne National Laboratory.","author":"Bischof C.","year":"1992","unstructured":"Bischof, C. and Sun, X. 1992. A framework for symmetric band reduction and tridiagonalization. Tech. Rep. MCS-P298-0392, Argonne National Laboratory."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/265932"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02166681"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384573"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/181014.181756"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/905686"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396757"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/080731992"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/070688778"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.12.028"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90367-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2016691"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Gansterer W. N. Kvasnicka D. F. and Ueberhuber C. W. 1999. Multi-sweep algorithms for the symmetric eigenproblem. In Vector and Parallel Processing V. Hernandez J. Palma and J. J. Dongarra Eds. Lecture Notes in Computer Science vol. 1573 Springer 20--28.","DOI":"10.5555\/647051.715441"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756934"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00041-1"},{"key":"e_1_2_1_33_1","volume-title":"Tech. Rep. YALEU\/DCS\/RR-916","author":"Gu M.","year":"1992","unstructured":"Gu, M. and Eisenstat, S. 1992. A stable algorithm for the rank-1 modification of the symmetric eigenproblem. Tech. Rep. YALEU\/DCS\/RR-916, Yale University."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503292"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063394"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/110823699"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.13"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Haidar A. Tomov S. Dongarra J. Solc\u00e5 R. and Schulthess T. 2013b. A novel hybrid CPU-GPU generalized eigensolver for electronic structure calculations based on fine-grained memory aware tasks. Int. J. High Perform. Comput. Appl.","DOI":"10.1177\/1094342013502097"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802486"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356052.1356055"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.05.001"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/356068.356074"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365733"},{"key":"e_1_2_1_44_1","unstructured":"Lang B. 1991. Parallele reduktion symmetrischer bandmatrizen auf tridiagonalgestalt. Ph.D. thesis Fakult\u00e4t f\u00fcr Informatik Technische Universit\u00e4t M\u00fcnchen."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914078"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00064-X"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00021-6"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450153.2450154"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.91"},{"key":"e_1_2_1_50_1","first-page":"108","article-title":"A new method for the tridiagonalization of the symmetric band matrix","volume":"15","author":"Murata K.","year":"1975","unstructured":"Murata, K. and Horikoshi, K. 1975. A new method for the tridiagonalization of the symmetric band matrix. Inf. Process. Japan 15, 108--112.","journal-title":"Inf. Process. Japan"},{"key":"e_1_2_1_51_1","unstructured":"Rajamanickam S. 2009. Efficient algorithms for sparse singular value decomposition. Ph.D. thesis University of Florida."},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of Symposia in Applied Mathematics.","volume":"15","author":"Rutishauser H.","year":"1963","unstructured":"Rutishauser, H. 1963. On Jacobi rotation patterns. In Proceedings of Symposia in Applied Mathematics. Vol. 15, AMS, 219--239."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0910005"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/366604.366643"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02162505"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 5th SIAM Conference on Applied Linear Algebra. 361--365","author":"Smith C.","unstructured":"Smith, C., Hendrickson, B., and Jessup, E. 1994. A parallel algorithm for householder tridiagonalization. In Proceedings of the 5th SIAM Conference on Applied Linear Algebra. 361--365."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535371"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386332"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.265"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2686877","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2686877","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2686877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:40:30Z","timestamp":1763458830000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2686877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,18]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2,18]]}},"alternative-id":["10.1145\/2686877"],"URL":"https:\/\/doi.org\/10.1145\/2686877","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,18]]},"assertion":[{"value":"2013-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}