Finding the eigenvalues and eigenvectors of a matrix is among the most fundamental computational tasks. These quantities correspond to resonant frequencies and modes of physical, statistical, and mathematical systems and appear in essentially every area of science and engineering. First year college students are taught how to compute them on small examples, and two of the ``top 10 algorithms of the twentieth century'' --- the QR Algorithm and the Arnoldi algorithm --- were designed to do so on large instances. When the matrices involved are symmetric, these methods come with provable guarantees showing that they are accurate, fast, and correct. However, the general non-symmetric case remains poorly understood, and rigorously analyzing these algorithms in general has been a decades-old mystery in numerical analysis, despite their being implemented in standard software packages. The main goal of this project is to solve these and related mysteries using modern tools of random-matrix theory and theoretical computer science. Doing so will put a large branch of computational practice on solid theoretical footing, and ideally foster deeper interaction between the numerical analysis, mathematics, and theoretical computer science research communities.
Specifically, the project will aim to analyze the two (currently heuristic) algorithms mentioned above, with the following concrete major goals: (1) find a shifting strategy for the shifted QR method which provably converges rapidly for every matrix; (2) formalize a widely held belief precisely relating the output of the Arnoldi algorithm to the pseudospectrum of the input matrix. Secondarily, the award will study the adjacent problem of efficiently computing an approximation of the Jordan normal form of a given rational matrix in the variable precision model of computation, for which good complexity bounds are not known. The project will likely use techniques from random-matrix theory, dynamical systems, algebra, and numerical analysis, building on recent progress of the investigator and collaborators in some of these areas.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
