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, Archit Kulkarni, 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.