Special CMX Seminar

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?