Fast and Inverse-Free Algorithms for Deflating Subspaces
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912835431301120 |
|---|---|
| author | Demmel, James Dumitriu, Ioana Schneider, Ryan |
| author_facet | Demmel, James Dumitriu, Ioana Schneider, Ryan |
| contents | This paper explores a key question in numerical linear algebra: how can we compute projectors onto the deflating subspaces of a regular matrix pencil $(A,B)$, in particular without using matrix inversion or defaulting to an expensive Schur decomposition? We focus specifically on spectral projectors, whose associated deflating subspaces correspond to sets of eigenvalues/eigenvectors. In this work, we present a high-level approach to computing these projectors, which combines rational function approximation with an inverse-free arithmetic of Benner and Byers [Numerische Mathematik 2006]. The result is a numerical framework that captures existing inverse-free methods, generates an array of new options, and provides straightforward tools for pursuing efficiency on structured problems (e.g., definite pencils). To exhibit the efficacy of this framework, we consider a handful of methods in detail, including Implicit Repeated Squaring and iterations based on the matrix sign function. In an appendix, we demonstrate that recent, randomized divide-and-conquer eigensolvers -- which are built on fast methods for individual projectors -- can be adapted to produce the generalized Schur form of any matrix pencil in nearly matrix multiplication time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_00193 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast and Inverse-Free Algorithms for Deflating Subspaces Demmel, James Dumitriu, Ioana Schneider, Ryan Numerical Analysis 65F60, 65F60 This paper explores a key question in numerical linear algebra: how can we compute projectors onto the deflating subspaces of a regular matrix pencil $(A,B)$, in particular without using matrix inversion or defaulting to an expensive Schur decomposition? We focus specifically on spectral projectors, whose associated deflating subspaces correspond to sets of eigenvalues/eigenvectors. In this work, we present a high-level approach to computing these projectors, which combines rational function approximation with an inverse-free arithmetic of Benner and Byers [Numerische Mathematik 2006]. The result is a numerical framework that captures existing inverse-free methods, generates an array of new options, and provides straightforward tools for pursuing efficiency on structured problems (e.g., definite pencils). To exhibit the efficacy of this framework, we consider a handful of methods in detail, including Implicit Repeated Squaring and iterations based on the matrix sign function. In an appendix, we demonstrate that recent, randomized divide-and-conquer eigensolvers -- which are built on fast methods for individual projectors -- can be adapted to produce the generalized Schur form of any matrix pencil in nearly matrix multiplication time. |
| title | Fast and Inverse-Free Algorithms for Deflating Subspaces |
| topic | Numerical Analysis 65F60, 65F60 |
| url | https://arxiv.org/abs/2310.00193 |