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.
Message To Sponsor
I thank Mr.Sherrill for his generous support for our project. Because of his donations, my teammates and I could have the opportunity to really dive into some of the most difficult areas of mathematics. This past summer has been an invaluable experience to me and this fellowship reshaped for understanding of rigorous mathematical research. Thank you again, Mr. Sherrill.