A fast spectral divide‐and‐conquer method for banded matrices. Issue 4 (8th March 2021)

• Record Type: Journal Article
• Authors: Šušnjara, Ana; Kressner, Daniel
• Is Part Of: Numerical linear algebra with applications. Volume 28:Issue 4(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2021-03-08
• Subjects: fast methods -- hierarchical matrices -- spectral decomposition -- spectral divide‐and‐conquer; Algebras, Linear -- Periodicals; 512.5
• DOI: 10.1002/nla.2365
• Languages: English
• ISSNs: 1070-5325

Abstract

Abstract: Based on the spectral divide‐and‐conquer algorithm by Nakatsukasa and Higham [SIAM J. Sci. Comput., 35(3):A1325–A1349, 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‐called hierarchically off‐diagonal low‐rank (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‐linear complexity for matrices that can be efficiently represented in the HODLR format throughout the divide‐and‐conquer algorithm, and allows for conveniently dealing with such large‐scale matrices.