Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.21917 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908382089183232 |
|---|---|
| author | Demmel, James Dumitriu, Ioana Schneider, Ryan |
| author_facet | Demmel, James Dumitriu, Ioana Schneider, Ryan |
| contents | This paper presents a fast, randomized divide-and-conquer algorithm for the definite generalized eigenvalue problem, which corresponds to pencils $(A,B)$ in which $A$ and $B$ are Hermitian and the Crawford number $γ(A,B) = \min_{||x||_2 = 1} |x^H(A+iB)x|$ is positive. Adapted from the fastest known method for diagonalizing arbitrary matrix pencils [Foundations of Computational Mathematics 2024], the algorithm is both inverse-free and highly parallel. As in the general case, randomization takes the form of perturbations applied to the input matrices, which regularize the problem for compatibility with fast, divide-and-conquer eigensolvers -- i.e., the now well-established phenomenon of pseudospectral shattering. We demonstrate that this high-level approach to diagonalization can be executed in a structure-aware fashion by (1) extending pseudospectral shattering to definite pencils under structured perturbations (either random diagonal or sampled from the Gaussian Unitary Ensemble) and (2) formulating the divide-and-conquer procedure in a way that maintains definiteness. The result is a specialized solver whose complexity, when applied to definite pencils, is provably lower than that of general divide-and-conquer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21917 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Structured Divide-and-Conquer for the Definite Generalized Eigenvalue Problem Demmel, James Dumitriu, Ioana Schneider, Ryan Numerical Analysis 15A22, 15B57, 65F15 This paper presents a fast, randomized divide-and-conquer algorithm for the definite generalized eigenvalue problem, which corresponds to pencils $(A,B)$ in which $A$ and $B$ are Hermitian and the Crawford number $γ(A,B) = \min_{||x||_2 = 1} |x^H(A+iB)x|$ is positive. Adapted from the fastest known method for diagonalizing arbitrary matrix pencils [Foundations of Computational Mathematics 2024], the algorithm is both inverse-free and highly parallel. As in the general case, randomization takes the form of perturbations applied to the input matrices, which regularize the problem for compatibility with fast, divide-and-conquer eigensolvers -- i.e., the now well-established phenomenon of pseudospectral shattering. We demonstrate that this high-level approach to diagonalization can be executed in a structure-aware fashion by (1) extending pseudospectral shattering to definite pencils under structured perturbations (either random diagonal or sampled from the Gaussian Unitary Ensemble) and (2) formulating the divide-and-conquer procedure in a way that maintains definiteness. The result is a specialized solver whose complexity, when applied to definite pencils, is provably lower than that of general divide-and-conquer. |
| title | Structured Divide-and-Conquer for the Definite Generalized Eigenvalue Problem |
| topic | Numerical Analysis 15A22, 15B57, 65F15 |
| url | https://arxiv.org/abs/2505.21917 |