Mathematics · 5 October 2022
New algorithms for multiplying matrices
AlphaTensor discovered matrix-multiplication algorithms that beat known records for several sizes, including a method for 4×4 matrices over a finite field that uses 47 scalar multiplications, improving on Strassen’s two-level algorithm of 49.
- Field
- Mathematics
- Date
- 5 October 2022
- AI system
- AlphaTensor
- Institution
- DeepMind
- Published in
- Nature
- Identifier
- 10.1038/s41586-022-05172-4
Matrix multiplication sits underneath a vast amount of scientific computing. In 1969, Volker Strassen showed that two 2×2 matrices can be multiplied with 7 scalar multiplications instead of 8, and that the same idea can be applied recursively. Finding still better algorithms is hard: the search space is enormous, and even the optimal way to multiply 3×3 matrices remains unknown.
AlphaTensor, published in Nature on 5 October 2022, is a deep reinforcement-learning agent, built on AlphaZero, trained to play a single-player game whose moves are steps in a tensor decomposition. A correct, short game is a provably correct multiplication algorithm that uses fewer scalar multiplications.
The agent discovered algorithms that match or improve on the best known complexity for many matrix sizes. A headline result is a 4×4 algorithm over the finite field Z₂ that uses 47 multiplications, improving on Strassen’s two-level algorithm, which uses 7² = 49 — the first such improvement, the authors write, since 1969. In standard arithmetic it also found, among other results, a rank-76 decomposition for multiplying 4×5 by 5×5 matrices, improving on a previous bound of 80. Because the algorithms are explicit decompositions, they can be used in practice, not only as existence proofs.