AF:Small: Algorithms and Limitations for Matrix Multiplication

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Matrix multiplication is among the most basic and fundamental mathematical operations. It finds applications throughout science, technology and beyond. For instance, matrices need to be multiplied whenever trajectories or changes of coordinates need to be computed: in graphics, computer animation, physics and chemistry simulations, map routing computations, machine learning, economics and more. The study of matrix multiplication algorithms seeks to develop the fastest methods for computers to multiply matrices. With today's world of big data, the matrices of interest are larger than ever, and very fast matrix multiplication methods are of great importance. An important educational goal of the project is to mentor undergraduate and graduate students in research, with a particular emphasis on building expertise in matrix algorithms and their applications. The investigator will also continue developing courses on the topics of this project, with a large research component. The lecture notes and project materials will be available on the course website for the general public. For decades the trivial approach to multiplying matrices was thought to be optimal until a 1969 breakthrough by Strassen and the subsequent development of deep theory led to significant improvements. The theoretical study of matrix multiplication algorithms aims to pinpoint the exponent omega of matrix multiplication: the smallest real number for which there is an algorithm that multiplies two n-by-n matrices over a field using n^{omega+o(1)} operations (additions and multiplications of field elements). Since the output is of size n^2, in the worst case, omega is at least 2. The best known published upper bound omega<2.37286 was obtained by Alman and the investigator, and a recent preprint on the arXiv gives an improvement to omega<2.372. The main goal of this project is to investigate new approaches to improving the bound on omega and related parameters, and to design a practical algorithm with a provably low runtime exponent. To complement this, the investigator will also explore the limitations of the new approaches, aiming to pinpoint both their strengths and weaknesses. A second goal of the project is to consider variants of the matrix multiplication problem, such as multiplying matrices over other algebraic structures with applications in graph algorithms. Both algorithms and conditional lower bounds will be considered. 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.