2025/05/28 by James Demmel, Ioana Dumitriu, Demmel, James +3 · 1 citation
Computer Science · Mathematics · #15A22 #15B57 #65F15 #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2505.21917
openalex publication_date 2025/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 |xH(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.