Jiahan Du L&S Sciences
Analysis of Matrix Multiplication Complexity Using Properties of Tensors
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 n n 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; for instance, the rank of the tensor corresponding to n = 3 is not even known. But 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.