Caltech Logo

Special CMX Seminar

Friday, September 1, 2023
4:00pm to 5:00pm
Add to Cal
Annenberg 213
Pseudospectral Divide-and-Conquer for Matrix Pencil Diagonalization
Ryan Schneider, Graduate Student, Department of Mathematics, University of California San Diego,

Banks, Garza Vargas, Kulkarni, and Srivastava recently developed a randomized algorithm that (with high probability) approximately diagonalizes a matrix in nearly matrix multiplication time [Foundations of Computational Math 2022]. Central to their work is the phenomenon of pseudospectral shattering, in which a small Gaussian perturbation regularizes the pseudospectra of a matrix. The key idea is remarkably simple: with high probability, perturbing a matrix breaks its pseudospectra into disjoint components, allowing a classical divide-and-conquer eigensolver to run successfully. In this talk, we generalize both pseudospectral shattering and a divide-and-conquer algorithm based on it to the generalized eigenvalue problem. The result is a randomized, inverse-free, and highly parallel algorithm for diagonalizing a matrix pencil that - like the single matrix version - runs in nearly matrix multiplication time.  Along the way, we explore a number of interesting questions in numerical linear algebra and random matrix theory:  How do we define the pseudospectra of a matrix pencil? What effect do independent Gaussian perturbations to a pair of matrices have on the corresponding set of generalized eigenvalues? And finally, can the generalized algorithm offer improved stability over its single matrix counterpart?

For more information, please contact Jolene Brink by phone at (626)395-2813 or by email at [email protected] or visit CMX Website.