CMX Student/Postdoc Seminar

The shifted QR algorithm is a powerful and widely used iterative method for computing the eigenvalues and eigenvectors of a matrix (both in the symmetric and non-symmetric case). In the 60s, the effectiveness of this algorithm on symmetric inputs was fully explained after a sequence of papers (by different authors) showed that Wilkinson's variant of the algorithm converges rapidly on any (symmetric) input.

Since then, despite its sustained use, the convergence properties of the shifted QR algorithm on non-symmetric inputs has remained elusive. From the practical side, a complex but empirically reliable and practical version of the algorithm has been obtained over the decades by addressing non-convergent cases with heuristic modifications and improvements. In this talk I will present recent theoretical work that proves that a relatively simple randomized version of the shifted QR algorithm converges rapidly on any (possibly non-symmetric) input.

_{This is joint work with Jess Banks and Nikhil Srivastava.}