CAREER: Complexity of Matrix Operations

Matrices are rectangular grids of numbers that can represent data in many forms, including geometric transformations, statistical models, physical systems, and relationships between data points. Because of this, computational tasks involving matrices appear throughout the theory and practice of computation, especially in areas like optimization, scientific computing, signal processing, data compression, and modern machine learning. Quickly performing matrix operations is frequently the key to designing efficient algorithms for understanding and manipulating data in these areas. The overarching goal of this project is to study these matrix operations: Can we design faster algorithms for them? Can we prove that further improvements are unlikely or impossible? Can we exploit their many connections with other areas or establish new connections? Since matrices are so ubiquitous, this project includes an educational goal of teaching and disseminating research results across many levels, from local high school students to a wide range of research communities in theory and practice who study different facets of matrix operations. The project particularly aims to train undergraduate and graduate students in the theory and applications of matrix operations through research opportunities and the development of a new course.This project focuses more specifically on two fundamental problems which form the backbone for most other computational tasks involving matrices. The first problem is fast matrix multiplication: How quickly can one multiply two input matrices? Matrix multiplication is used in the fastest known algorithms for many fundamental computational problems. It is frequently known to be the bottleneck, meaning faster matrix multiplication is required to speed up the best algorithms. The second problem is fast linear transformation: How quickly can one multiply an input vector times a matrix of interest, such as a Fourier matrix? Algorithms like the Fast Fourier transform and the Fast Walsh-Hadamard transform have been some of the most applicable and impactful algorithms. These transforms also underlie prominent topics throughout computational complexity theory. The investigator has recently proven results about formal barriers to designing faster algorithms for both matrix multiplication and linear transforms. One of the main insights that this project pursues is that ideas from these barrier results can help to make new progress on algorithms.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.