Fast Divide-and-Conquer for the Structured Generalized Eigenvalue Problem

We present an inverse-free, randomized, and highly parallellizable algorithm for solving a structured generalized eigenvalue problem involving a Hermitian pencil (A,B) whose Crawford number is positive. The method is an efficient, structured modification of the divide-and-conquer approach for the general case, based on the idea of randomization as a regularization factor (in the manner of smoothed analysis). This is joint work with James Demmel and Ryan Schneider.