BIRS Workshop — Perspectives on Matrix Computations: Theoretical Computer Science Meets Numerical Analysis

Computations with matrices, such as their multiplication, are fundamental operations that are executed on millions of devices, from smartphones to supercomputers, every day. But what is the minimum number of operations it takes to multiply two matrices? Surprisingly, the answer is currently unknown. The problem of determining the complexity, or the number of operations required to perform a certain computation, goes back to the very origins of computing. In the age of large-scale scientific computing, big data, and machine learning, understanding the complexity of computations is crucial for designing algorithms that are efficient in terms of both time and energy. There are two distinct research communities in computer science and mathematics working to answer these questions. Each community brings different perspectives and different approaches, but they rarely interact with each other to the detriment of both. To truly advance the state-of-the-art and tackle huge computational problems, cooperation and collaboration is needed. This workshop will bring together a diverse group of researchers in theoretical computer science and numerical analysis to shape the future of research on the complexity of matrix computations.