Computational Linear Algebra is the study of algorithms for solving mathematical problems involving matrices and other linear-algebraic objects. It is one of the oldest and most practically applicable subfields of algorithms research. Linear-algebraic routines lie at the core of many large-scale scientific and engineering simulations, signal-processing methods, statistical- and machine-learning algorithms, and beyond. Recently, the field has been revolutionized by work on algorithms that make carefully chosen random choices during the course of their execution, allowing much faster approximate solutions for very large-scale problems. This project aims to build on the success of these randomized methods and extend their reach. The work will also identify fundamental limits on the potential for faster algorithms and on today's most popular techniques. Beyond impact in the above mentioned application areas, the project will deepen the theoretical foundations of computational linear algebra and strengthen ties to theoretical computer science, approximation theory, optimization, machine learning, and other fields. The work is interdisciplinary in nature, and will be complemented with curriculum development focused on preparing students with an interdisciplinary mathematical and computing toolkit.
The project breaks down into three main thrusts. The first will consider the computational complexity of fundamental linear-algebraic problems, which is not well understood. In the process, the work will explore the role of randomization and approximation in fast linear algebra and endow the field with missing complexity-theoretic structure to guide algorithmic progress. The second thrust will focus on algorithms and lower bounds within the restricted matrix-vector query model of linear-algebraic computation. This model encompasses a large fraction of known approaches, and the project aims to both explain its dominance in practice, and to develop new algorithmic tools. Finally, the third thrust will focus on applying randomized methods to structured matrix problems arising in machine learning, signal processing, and beyond. Randomized methods have led to breakthroughs for computation on general unstructured matrices, but their potential in solving structured problems is under-explored. The project will address this gap, broadening the practical impact of randomized methods, and strengthening theoretical connections to diverse areas of computer science and applied mathematics.
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.
