Nathan Cheng L&S Sciences
Analysis of Matrix Multiplication Complexity Using Properties of Tensors
Matrix multiplication is one of the most foundational mathematical operations, and has deep connections to many areas of math, including algebra, geometry, and combinatorics. There is huge incentive to improve the speed of matrix multiplication as well as understand the inherent bounds on its complexity, due to its importance in applied mathematics and the computational sciences.
Many of the questions concerning the complexity of matrix multiplication are still unsettled, namely: how can we make it faster and how fast can it go? It is thought that intrinsic mathematical properties of matrices constrain the algorithmic possibilities for operations on them. This is the thesis of algebraic complexity theory. Such properties include the dimensions of certain functions of matrices, many of which are not known. The purpose of this project is to perform a systematic application of known techniques from algebraic complexity theory to understand simple cases which are still poorly understood (which to date has not been performed). We hope to use techniques such as border rank bounds, basis transformations, tensor-flattening approaches, and group-theoretic algorithms, and demonstrate either the power or the limitations of such techniques.