Yu Ma L&S Sciences
Analysis of Matrix Multiplication Complexity Using Properties of Tensors
Matrix multiplication is one of the most foundational mathematical operations. Understanding this operation is a sophisticated mathematical question, which has been the subject of extensive research over the years. There is huge incentive to improve the speed of matrix multiplication as well as understand the inherent bounds on its complexity.
The rich theory of algebraic computational complexity aims to study the complexity of objects with an intrinsic mathematical structure. In particular, for each n, matrix multiplication of two nxn matrices can be expressed as a bilinear map, which corresponds to a tensor via a well-known isomorphism. The rank of this tensor controls the asymptotic complexity of matrix multiplication of a particular dimensionality.
Despite this powerful relationship, much is still unsettled.To date, a systematic review of applications of known techniques to specific cases has not been performed. We hope to study lower and upper bounds on tensors for small n by looking at border rank bounds, basis transformations, tensor-flattening approaches, and group-theoretic algorithms, and demonstrate either the power or the limitations of such techniques. We believe that an in-depth analysis of specific cases may yield even more general techniques for understanding and designing algorithms.