Speaker
Description
The fastest method for diagonalizing a nonsymmetric matrix or matrix pencil is pseudospectral divide-and-conquer. This two-step algorithm diagonalizes a matrix/pencil by (1) randomly perturbing the input(s) and (2) running fast (and highly-parallel) spectral divide-and-conquer. The key to this approach is the random perturbation, which with high probability implies a guarantee of pseudospectral shattering – i.e., that the spectrum and pseudospectrum of the perturbed problem is sufficiently well-behaved for divide-and-conquer to succeed and to run efficiently. In this talk, we present the most general formulation of pseudospectral divide-and-conquer and discuss efforts to specialize the algorithm to structured problems (e.g., definite pencils).