AF: Small: The complexity of matrix multiplication

Texas A&M University, College Station TX

Investigators

Abstract

Linear algebra, which includes computing the solutions to a system of linear equations, is at the heart of all scientific computation. The core computation of linear algebra is matrix multiplication. In 1968 V. Strassen discovered that the widely used and assumed best algorithm for matrix multiplication is not optimal. Since then there has been intense research in both determining just how efficiently matrices may be multiplied and determining the limits of how much Strassen's algorithm can be improved. This project will address both efficiency and limits. Both parts will be approached using theoretical mathematics not traditionally utilized in the study of these questions, namely representation theory and algebraic geometry. The novel use of modern mathematical techniques will enrich both theoretical computer science and pure mathematics, as they will open new questions in mathematics and provide new techniques to computer science. The exponent of matrix multiplication, denoted omega, is the fundamental constant that governs the complexity of matrix multiplication and all basic operations in linear algebra. It is currently known that omega is somewhere between 2 and 2.38. After Strassen's 1968 discovery, which led to the definition of the exponent and proof that it is at most 2.81, over the next twenty years it was steadily lowered to 2.38. In the past 33 years, it has been improved by less than .004. All improvements since 1987 have been made indirectly through the use of auxiliary tensors and in the past 10 years explanations for why progress became incremental have emerged: the utility of auxiliary tensors currently being used is limited. The upper bound part of this project will discover (using geometric methods) and utilize new auxiliary tensors that are not subject to such utility limits. The lower bound part of the project will bound border rank of tensors. There are no nontrivial lower bounds on the exponent, and in order to prove one, one would have to prove a super-linear lower bound on the border rank of some tensor, a goal that is out of reach with current technology. The current technology can barely prove border rank bounds of 2N for (N,N,N)-tensors. This project will significantly improve lower bound technology by introducing further new tools to the area from modern algebraic geometry such as deformation theory. 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.