Estimating Eigenvalues and Matrix Functions with a Krylov Subspace

Krylov subspace methods are among the most popular classes of algorithms in computational mathematics, particularly when dealing with high-dimensional problems — an increasingly important subject in all areas of engineering, science, and modern technology. Their advantages are simple: they tend to be very fast and relatively accurate. But despite their ubiquity, many questions regarding their behavior and their approximation quality remain unanswered. This project, will further understanding of the behavior and robustness of existing Krylov subspace algorithms and create new algorithms for fundamental computational tasks for which no robust algorithm currently exists. Several of the research projects are suitable for training undergraduate and graduate students. A new computational math seminar at MIT, focused on numerical linear algebra, will draw more students to the field. This project investigates Krylov subspace methods through four specific problems: (1) A complex moment method: Examine the theoretical and practical feasibility of a potential new technique that builds upon theoretical work on the truncated complex moment problem in analysis. (2) Estimating matrix functions: Develop efficient algorithms for computing matrix functions for a variety of graph-related problems by applying recently developed fast Laplacian linear system solvers to rational Krylov subspace methods. (3) Constructing extremal polynomials: Introduce a class of problems that will provide insight into error estimates for Krylov subspace methods for non-Hermitian matrices. (4) Recovering a matrix from its moments: Given a finite moment sequence, when does there exist an orthogonal matrix with those moments? The PI will introduce an algorithm to answer this question for a large class of moment sequences. 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.