The Department of Applied Mathematics weekly seminar is given by scholars and researchers working in applied mathematics, broadly interpreted.
Title: Proving rapid global convergence for the shifted QR algorithm
Abstract: The design of efficient and reliable algorithms for computing the eigenvalues and eigenvectors of a matrix (i.e. solving the eigenvalue problem) is critically important in both science and engineering. Despite significant advancements in various practical aspects, fundamental theoretical questions about the eigenvalue problem remain poorly understood.
In this talk, I will present joint work with Jess Banks and Nikhil Srivastava, in which we provide nearly optimal rigorous guarantees, on all inputs, for the most widely used diagonalization algorithm: the shifted QR algorithm. Similar results were established by Wilkinson in 1968 and Dekker and Traub in 1971 for Hermitian matrices; however, despite sustained interest and several attempts, the non-Hermitian case remained elusive for the last five decades.