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.
Message To Sponsor
SURF Math Team Fellowship gave me an unparalleled research experience in my undergraduate studies. It provided a platform to support dynamic peer interactions, individual contemplations, and insights from the professor. During the summer, we worked closely as a team daily to discuss new findings and progress, solving each others' dilemmas and inspiring new ideas. This experience has definitely helped me better understand my passion and interests in mathematics and opened a new field of possibilities for me to further investigate in my future academic endeavor.