Rational approximation for new structured methods in numerical linear algebra

This grant supports the development of extremely fast methods for large-scale computing with structured matrices that appear pervasively in applications such as imaging, control theory, and signal processing. The Investigator will leverage new ideas in rational approximation that explain the structures in these matrices and imply the possibility of superfast algorithms. The matrices of primary interest are those with special displacement structures, including Toeplitz, Vandermonde, Hankel, Cauchy, and Loewner matrices, as well as block variants of these matrices. Such matrices and related matrix equations are ubiquitous across the sciences, and improved algorithms are greatly needed to overcome computational bottlenecks that currently impede progress and limit the scale of investigable problems. Collaborating with domain experts, the Investigator will develop open-source software that solves these problems under broader assumptions and at larger scales than what is currently possible. In areas such as MRI imaging, geophysical imaging, Fourier imaging in astrophysics and scattering, and in climate modeling, these improvements will ultimately benefit the public with positive impacts on medical technologies and other technologies deployed in the interest of citizens. The goal and scope of the project is to advance scientific knowledge in two critical ways: (1) It will extend the applicability of rank-structured methods beyond what is currently possible and create new methods for working with rank-structured rectangular matrices. The solvers developed in this work are general and can be applied to any matrix with rectangular hierarchical structure. The work will develop general techniques for efficiently designing preconditioners, solving least squares and minimum norm problems, applying regularization, and solving constrained optimization problems that involve rectangular hierarchical matrices. It will inspire further research into both the design and application of direct methods in settings where previously they were too expensive or underdeveloped to consider. (2) This work tackles a collection of matrix families that lie at the heart of many applications. It supplies a new and general framework from which all of their compression properties can be theoretically understood. The foundation of that framework comes from rational approximation theory. 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.