{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T12:01:12Z","timestamp":1726920072758},"reference-count":33,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2021,3,8]],"date-time":"2021-03-08T00:00:00Z","timestamp":1615161600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Numerical Linear Algebra App"],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>Based on the spectral divide\u2010and\u2010conquer algorithm by Nakatsukasa and Higham [SIAM J. Sci. Comput., 35(3):A1325\u2013A1349, 2013], we propose a new algorithm for computing all the eigenvalues and eigenvectors of a symmetric banded matrix with small bandwidth, with the eigenvectors given implicitly as a product of orthonormal matrices stored in the so\u2010called hierarchically off\u2010diagonal low\u2010rank (HODLR) format. For this purpose, we combine our previous work on the fast computation of spectral projectors in the HODLR format, with a novel technique for extracting a basis for the range of such a HODLR matrix. Preliminary numerical experiments demonstrate that our algorithm exhibits quasi\u2010linear complexity for matrices that can be efficiently represented in the HODLR format throughout the divide\u2010and\u2010conquer algorithm, and allows for conveniently dealing with such large\u2010scale matrices.<\/jats:p>","DOI":"10.1002\/nla.2365","type":"journal-article","created":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T06:35:35Z","timestamp":1615271735000},"update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A fast spectral divide\u2010and\u2010conquer method for banded matrices"],"prefix":"10.1002","volume":"28","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-1435-040X","authenticated-orcid":false,"given":"Ana","family":"\u0160u\u0161njara","sequence":"first","affiliation":[{"name":"MATH\u2010ANCHP \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne Lausanne Switzerland"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-3369-2958","authenticated-orcid":false,"given":"Daniel","family":"Kressner","sequence":"additional","affiliation":[{"name":"MATH\u2010ANCHP \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne Lausanne Switzerland"}]}],"member":"311","published-online":{"date-parts":[[2021,3,8]]},"reference":[{"key":"e_1_2_10_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/120876605"},{"key":"e_1_2_10_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365735"},{"key":"e_1_2_10_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.05.002"},{"key":"e_1_2_10_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1680"},{"key":"e_1_2_10_6_1","doi-asserted-by":"crossref","unstructured":"HaidarA LtaiefH DongarraJ. Parallel reduction to condensed forms for symmetric eigenvalue problems using aggregated fine\u2010grained and memory\u2010aware kernels. Proceedings of the 2011 International Conference for High Performance Computing Networking Storage and Analysis. New York NY: ACM;2011. p. 8:1\u20138:11.","DOI":"10.1145\/2063384.2063394"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38750-0_6"},{"key":"e_1_2_10_8_1","doi-asserted-by":"crossref","unstructured":"SolomonikE BallardG J.Demmel HoeflerT. A communication\u2010avoiding parallel algorithm for the symmetric eigenvalue problem. Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures SPAA '17. New York NY: ACM;2017. p. 111\u2013121.","DOI":"10.1145\/3087556.3087561"},{"key":"e_1_2_10_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(92)90059-G"},{"key":"e_1_2_10_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827501399432"},{"key":"e_1_2_10_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/110823699"},{"key":"e_1_2_10_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087278"},{"key":"e_1_2_10_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-013-9714-z"},{"key":"e_1_2_10_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47324-5"},{"key":"e_1_2_10_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396757"},{"key":"e_1_2_10_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892241287"},{"key":"e_1_2_10_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2014.01.005"},{"key":"e_1_2_10_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1018812"},{"key":"e_1_2_10_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1288048"},{"key":"e_1_2_10_20_1","unstructured":"MasseiS. Exploiting rank structures in the numerical solution of Markov chains and matrix functions [Doctoral thesis]. Scuola Normale Superiore di Pisa;2017."},{"key":"e_1_2_10_21_1","doi-asserted-by":"crossref","DOI":"10.1353\/book.3417","volume-title":"Matrix computations and semiseparable matrices","author":"Vandebril R","year":"2008"},{"key":"e_1_2_10_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49887-4_3"},{"key":"e_1_2_10_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/090774999"},{"key":"e_1_2_10_24_1","unstructured":"KressnerD \u0160u\u0161njaraA. Fast QR decomposition of HODLR matrices;2018. arXiv:1809.10585 [math.NA]."},{"key":"e_1_2_10_25_1","unstructured":"\u0160u\u0161njaraA. Fast hierarchical solvers for symmetrical eigenvalue problems [Doctoral thesis]. EPFL;2018."},{"key":"e_1_2_10_26_1","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"volume-title":"Accuracy and stability of numerical algorithms","year":"1996","author":"Higham NJ","key":"e_1_2_10_27_1"},{"key":"e_1_2_10_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(78)90048-7"},{"key":"e_1_2_10_29_1","unstructured":"LintnerM. L\u00f6sung der 2D wellengleichung mittels hierarchischer Matrizen [Doctoral thesis]. Technische Universit\u00e4t M\u00fcnchen;2002."},{"key":"e_1_2_10_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"e_1_2_10_31_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400833887"},{"key":"e_1_2_10_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377603.1377611"},{"key":"e_1_2_10_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"key":"e_1_2_10_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0707001"}],"container-title":["Numerical Linear Algebra with Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2365","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/nla.2365","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2365","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T17:42:18Z","timestamp":1724607738000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/nla.2365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,8]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1002\/nla.2365"],"URL":"https:\/\/doi.org\/10.1002\/nla.2365","archive":["Portico"],"relation":{},"ISSN":["1070-5325","1099-1506"],"issn-type":[{"type":"print","value":"1070-5325"},{"type":"electronic","value":"1099-1506"}],"subject":[],"published":{"date-parts":[[2021,3,8]]},"assertion":[{"value":"2018-01-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}