Collaborative Research: AF: Fine-Grained Theory for Matrix Computations

Throughout the sciences, engineering, data sciences, and essentially all other quantitative fields, numerical information is organized into two-dimensional arrays of numbers called matrices. Computations involving matrices are the driving force behind a huge range of economically and socially impactful applications, including machine learning and generative artificial intelligence, large-scale simulation of physical systems, and statistical analysis needed to advance the basic sciences and healthcare. Based on applications in machine learning alone, a conservative estimate is that 15 to 20 percent of all data center usage in the U.S. is devoted to computations involving matrices, with that number growing rapidly. Despite this, and despite the fact that matrix computations have been studied for centuries, many of the algorithms currently used for core matrix routines are not believed by researchers to be the fastest possible. This is most famously true for the basic problem of matrix-matrix multiplication, which arises in all of the applications discussed above. It is also the case for other central problems, like eigen decomposition, low-rank approximation, and linear system solving. Indeed, faster algorithms for all of these problems have been found in just the last 15 years. This project seeks to understand for what problems further progress is possible, and what algorithmic techniques will be necessary to make this progress. Even modest improvements in current state-of-the-art matrix routines could massively reduce computing costs for scientists, private companies, and government organizations. The project's goal is to build the knowledge needed to make such improvements possible. To achieve this goal, the investigators will draw on tools from the rapidly developing field of fine-grained complexity theory. This field seeks to understand the precise asymptotic complexity of problems that, like most matrix problems, are solvable in polynomial time, but for which optimal runtimes are not known. In recent years, fine-grained complexity has significantly improved understanding of many problems involving discrete structures like graphs, strings, and beyond. However, applications to matrix problems have been limited. The project aims to fill this gap. The first thrust of the work will study efficient reductions between matrix problems, in order to better understand their complexity. When can one leverage progress on one matrix problem to make progress on others? Alternatively, when do barriers preventing progress on one problem apply to others? As an example, for many basic problems like determinant computation, eigen decomposition, and linear system solving, the best-known algorithms for worst-case instances are as slow as matrix-matrix multiplication. One goal will be to prove via reductions that this barrier is inherent. In other words, to prove that these problems cannot be solved in less time than matrix-matrix multiplication. The second thrust of the work will focus on the importance of randomness, which in recent years has driven progress on problems like matrix norm estimation and linear system solving. The work will aim to show that randomization is necessary for further progress on certain problems by proving that faster deterministic methods would lead to progress on classic problems like derandomizing matrix product testing. At the same time, the project will investigate new deterministic approaches that at least partially close existing gaps with randomized methods. Finally, the third thrust will focus on finer-grained notions of efficiency beyond asymptotic complexity, like instance optimality and Pareto optimality. This thrust will drive progress on new algorithms and analytic techniques. Overall, the project will bring a new complexity-theoretic perspective to numerical linear algebra that will shape the search for faster algorithms going forward. It will advance interdisciplinary research in applied mathematics and theoretical computer science, and train graduate and undergraduate students who are able to work across these areas, driving critical progress on efficient algorithms for matrix problems and beyond. 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.