Pelle Andersson: Introduction to Faster Matrix Multiplication

Abstract.

Applying the definition of matrix multiplication directly, the time complexity of computing the product of two \(n \times n\) matrices is \(\mathcal{O}(n^3)\), assuming arithmetic operations of numbers taking constant time. In the 1960s, faster methods were discovered for the first time, leading to further research in how low the time complexity could go. It is popularly conjectured to be \(\mathcal{O}(n^2)\) — as low as addition of matrices. The general method of the developments has been viewing the bilinear mapping that matrix multiplication is as a three-dimensional tensor, where there is a natural correspondence between time complexity of the multiplication algorithm and tensor rank. This talk will act as an introduction to the history of achieving faster matrix multiplication.