Matrix multiplication sits at the core of scientific computing, econometrics, and modern deep learning. Conceptually, multiplying two matrices and represents the composition of two linear transformations.
From to Strassen’s Algorithm
Using the standard row-by-column definition for two matrices:
computing all entries requires scalar multiplications. For over a century, was widely assumed to be optimal.
In 1969, Volker Strassen proved this assumption wrong by showing that two matrices can be multiplied using 7 scalar multiplications instead of 8, at the cost of extra additions. Applying this block decomposition recursively yields an asymptotic complexity of:
Reinforcement Learning & AlphaTensor
Decades of algebraic research pushed the matrix multiplication exponent lower (Coppersmith–Winograd and subsequent refinements). In 2022, DeepMind introduced AlphaTensor, framing the search for low-rank tensor decompositions of the matrix multiplication tensor as a single-player reinforcement learning game.
AlphaTensor discovered faster practical multiplication algorithms for small matrix sizes—including improving upon Strassen’s two-level algorithm for matrices in modular arithmetic—followed shortly by further heuristic improvements in .
References
- Strassen, V. Gaussian elimination is not optimal. Numer. Math. 13, 354–356 (1969). https://doi.org/10.1007/BF02165411
- Fawzi, A., Balog, M., Huang, A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610, 47–53 (2022). https://doi.org/10.1038/s41586-022-05172-4
- Manuel Kauers and Jakob Moosbauer. The FBHHRBNRSSSHK-algorithm for multiplication in is still not the end of the story. Technical Report 2210.04045, arXiv (2022).