About
A lot of the world's computation is spent on linear algebra problems such as matrix multiplication, Ax = b, and Ax = λx, yet our theoretical understanding of these problems is far from sharp. What is the exponent of matrix multiplication? Which linear systems, other than Laplacians, can we solve in nearly linear time? Is Gaussian elimination numerically stable? Can efficient algorithms for linear algebra be derandomized? We don’t have satisfying answers to these questions. Moreover, there is a large disconnect between theory and practice, exemplified by the fact that all high-performance implementations of matrix multiplication currently in use are variations of the cubic-time algorithm.
Such questions have been intensively studied in several distinct research communities, including theoretical computer science, numerical linear algebra, high-performance computing, symbolic computation, and various branches of mathematics. These fields have had limited interaction and have developed essentially parallel research traditions around the same core problems, with their own models of computation (e.g., exact vs. floating point vs. rational vs. finite field arithmetic), solution concepts (backward vs. forward error), and techniques. This divergence of perspectives has been amplified by researchers from these fields generally publishing in disjoint venues and being housed in different departments.
On the other hand, some interactions that have taken place have been highly productive and paradigm-changing. For instance, combinatorial preconditioning, randomized numerical linear algebra, and smoothed analysis all arose from such interactions. On the more mathematical side, the complexity of matrix multiplication can itself be phrased as a linear algebraic problem, that of tensor rank. Exciting developments over the last decade have shown this problem to be related to algebraic geometry, geometric invariant theory, quantum information, and algebraic complexity, enabling new tools for proving upper and lower bounds. On the more computational side, there have been advances in minimizing communication costs and leading constants in linear algebra algorithms, with the aim of bringing theory closer to practice.
This program will bring together researchers from the research communities mentioned above for a whole semester, for the first time, around the following three themes.
-
Complexity of linear algebra
-
Theory toward practical linear algebra
-
Randomness, invariants, and tensors
This program will feature a boot camp, a workshop on linear equations and eigenvalue problems, a workshop on matrix multiplication, and a workshop on randomness, invariants, and complexity theory.
