A fast spectral divide‐and‐conquer method for banded matrices
| Autor: | Daniel Kressner, Ana Susnjara |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Divide and conquer algorithms
Algebra and Number Theory Band matrix Basis (linear algebra) Applied Mathematics Computation 010103 numerical & computational mathematics 01 natural sciences Matrix decomposition 010101 applied mathematics Matrix (mathematics) Range (mathematics) 0101 mathematics Algorithm Eigenvalues and eigenvectors Mathematics |
| Zdroj: | Numerical Linear Algebra with Applications. 28 |
| ISSN: | 1099-1506 1070-5325 |
| DOI: | 10.1002/nla.2365 |
| Popis: | 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. For this purpose, we combine our previous work on the fast computation of spectral projectors in the so called HODLR format, with a novel technique for extracting a basis for the range of such a HODLR matrix. The numerical experiments demonstrate that our algorithm exhibits quasilinear complexity and allows for conveniently dealing with large-scale matrices. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text