Content area
Abstract
Over the last two decades, randomization has emerged as a leading tool for pursuing efficiency in numerical linear algebra. Its benefits can be explained in part by smoothed analysis, where an algorithm that fails spectacularly in certain cases may be unlikely to do so on random – or randomly perturbed – inputs. This observation implies a simple framework for developing accurate and efficient randomized algorithms: apply a random perturbation and run an existing method, whose worst-case error (or run-time) can be avoided with high probability.
Recent work of Banks, Garza-Vargas, Kulkarni, and Srivastava applied this framework to the standard eigenvalue problem, developing a randomized algorithm that (with high probability) 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 pseudospectrum of a matrix, with high probability breaking it into disjoint components and allowing classical, divide-and-conquer eigensolvers to run successfully. Prior to their work, no way of accessing the benefits of divide-and-conquer’s natural parallelization was known in general.
In this thesis, we extend the work of Banks et al. to the generalized eigenvalue problem – e.g., Av = λBv for matrices A, B ∈ ℂn×n. Our main contributions can be summarized as follows.
1. First, we show that pseudospectral shattering generalizes directly: randomly perturbing A and B has a similar regularizing effect on the pseudospectra of the corresponding matrix pencil (A, B) with high probability.
2. Building on pseudospectral shattering, we construct and analyze a fast, randomized, divide-and-conquer algorithm for diagonalizing (A, B), which begins by randomly perturbing the inputs.
3. Finally, we demonstrate that both pseudospectral shattering and the corresponding diagonalization algorithm can be adapted to definite pencils, further pursuing efficiency by preserving and exploiting symmetry.
The resulting algorithm, which we call pseudospectral divide-and-conquer, is the first general, sub-O(n3 ) solver for the generalized eigenvalue problem. It is not only highly parallel and capable of accommodating structure, but also promotes stability by avoiding matrix inversion. In essence, this thesis is a handbook for understanding, adapting, and implementing the method.
