Collaborative Research: AF: Small: The Query Complexity of Linear Algebra

Mathematical problems involving matrices, such as systems of linear equations and eigenvalue problems, arise in a huge number of applications across machine learning, statistics, scientific computing, engineering, and beyond. More efficient algorithms for solving these problems can thus have widespread practical impact, significantly accelerating the pace of scientific discovery, decreasing the cost of data analysis, and facilitating simulations of large-scale, complex systems.

Developing efficient algorithms for matrix problems is the central goal of the field of numerical linear algebra. Unfortunately, it can often be difficult to understand the limits of algorithmic research. How close are the current best algorithms to being optimal?

Are there inherent barriers to developing faster algorithms? This project will tackle these questions by studying fast matrix algorithms through the lens of “query complexity”. Specifically, the goal is to develop algorithms that access, or “query”, the input matrix as few times as possible in order to solve a given problem.

Algorithms with small query complexity are frequently efficient in practice, so focusing on query complexity will lead to the development of faster algorithms for applications. At the same time, unlike more general models of computation, it is often possible to prove impossibility results for query complexity, i.e., to show that no algorithm can solve a given problem with too small of query complexity.

Thus, the project will improve understanding of the limits of algorithmic research and of the optimality or sub-optimality of existing methods. The work will produce general-purpose algorithmic tools and lower-bound techniques that can be applied to algorithms research at large. The project will also expand the dialogue between research communities, including theoretical computer science, numerical analysis, and quantum computing communities.

Concretely, the research team will study linear algebraic computation through the lens of query complexity by 1) developing new, query-efficient algorithms for core matrix problems and 2) proving unconditional lower bounds on the number of queries required to solve these problems. The research will center on two important query models: entrywise matrix queries and matrix-vector product queries.

Entrywise queries are perhaps the simplest query model for linear algebraic computation, although the complexity of many basic problems in the model, from eigenvalue approximation to matrix norm computation, remains unresolved. By studying the model, the project will explore broad themes, such as the importance of randomness and query adaptivity, and the power of “augmented” entrywise query models that rise in quantum-inspired numerical linear algebra, spectral graph theory, and beyond.

The project’s second focus on matrix-vector product queries is motivated by the fact that matrix-vector products often dominate the runtime of linear algebraic methods in practice. As such, understanding the number of matrix-vector products required to solve central problems like structured matrix approximation, norm approximation, and spectral density estimation is a key goal.

The matrix-vector product model generalizes the widely studied matrix sketching and Krylov subspace models, so proving lower bounds in this model will require new techniques. Overall, the project will strengthen the theoretical foundations of computational linear algebra, with the goal of establishing query complexity as a central framework for developing faster algorithms and computational lower bounds.

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.