A Rank 23 Algorithm for Multiplying 3 × 3 3\times 3 Matrices with an Arithmetic Complexity of 59

Erik Mårtensson, Paul Stankovski Wagner, Joshua Stapleton · 2026

Read A Rank 23 Algorithm for Multiplying 3 × 3 3\times 3 Matrices with an Arithmetic Complexity of 59 by Erik Mårtensson, Paul Stankovski Wagner, Joshua Stapleton (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05272.txt.

Introduction

Erik Mårtensson, Paul Stankovski Wagner, and Joshua Stapleton present a faster algorithm for multiplying three-by-three matrices in a 2026 paper. Since Strassen's 1969 surprise, researchers have chased matrix multiplication with fewer scalar multiplications. For three-by-three matrices the fewest multiplications known is in the low twenties, and attention has shifted to cutting the additions, which dominate the arithmetic complexity once multiplications are fixed.

Using a change-of-basis method, the authors give an algorithm at that multiplication count with a reduced total of additions, continuing a line of work that trimmed additions step by step. Matrix multiplication sits inside nearly every scientific and graphics computation, so shaving operations from even the small cases informs the design of larger fast algorithms.

Catalog record

CREATORErik Mårtensson, Paul Stankovski Wagner, Joshua Stapleton
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-05272

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Rank 23 Algorithm for Multiplying 3 × 3 3\times 3 Matrices with an Arithmetic Complexity of 59 Erik Mårtensson, Paul Stankovski Wagner, Joshua Stapleton Abstract In 1969 Strassen showed surprisingly that it is possible to multiply two 2 × 2 2\times 2 matrices using seven multiplications and 18 additions, instead of the naive eight multiplications and four additions. The number of additions was later reduced to 15. Karstadt and Schwartz further reduced the number of additions to 12 using a change-of-basis method. Both the number of multiplications and the number of additions have been shown to be optimal for the 2 × 2 2\times 2 case. For multiplying 3 × 3 3\times 3 matrices, the lowest number of multiplications found so far is 23. Using 23 multiplications, Schwart et al. showed how to reduce the number of additions to 61 using a change-of-basis method. Mårtensson and Stankovski Wagner showed how to achieve 62 additions, without changing basis. Using the optimization method by Mårtensson and Stankovski Wagner, Stapleton found an algorithm requiring only 60 additions. In this work we continue to combine the methods of Mårtensson, Stankovski Wagner and Stapleton, finding an algorithm requiring only 59 additions, still without a basis change. Technical details on the method and tools used for finding this scheme, and a discussion on the impact of this discovery, will come in an upcoming publication. 1 Introduction Multiplying 2\times 2 matrices directly from the definition requires eight multiplications and four additions. In 1969 Strassen [ 11 ] showed how to reduce the number of multiplications to seven, at the cost of increasing the number of additions to 18 1 1 1 When referring to additions, we also implicitly include both additions and subtractions. . The number of multiplications is also called the rank of the algorithm. The rank seven was shown to be optimal in [ 12 ] . For rank 7 algorithms for multiplying 2\times 2 matrices, the number of additions was reduced to 15 in [ 2 ] . The number of additions required is also referred to as the arithmetic complexity of the algorithm. Using a change of basis, Karstadt and Schwartz improved this number to 12 and showed it to be optimal in [ 3 ] . In terms of computational complexity, performing this change of basis introduces lower-order terms that are small compared to the cost of performing an addition. Now consider multiplying an n\times m matrix by an m\times k matrix. For most of the matrix dimensions larger than that of 2\times 2 , both the optimal rank and the optimal arithmetic complexity of matrix multiplication are not known. For a collection of the schemes found for a large number of dimensions, see [ 7 ] . For multiplying 3\times 3 matrices, Laderman found a rank 23 algorithm by hand in 1976 [ 4 ] . After almost half a century of applying increasingly sophisticated search methods, this rank has not been improved. In this work, we introduce a new record for the number of additions for a rank 23 algorithm for multiplying 3\times 3 matrices. In terms of the number of additions required for rank 23 algorithms for multiplying 3\times 3 matrices, Smirnov found an algorithm that naively requires 84 additions [ 8 ] . Smirnov pointed out that the number of additions for his algorithm can be lowered, but he did not perform such an optimization. Karstadt and Schwartz reduced the number of additions to 75 in [ 3 ] . Beniamini et al. reduced this number further to 61 in [ 1 ] . Without performing a change of basis, Mårtensson and Stankovski Wagner showed how to perform Laderman’s original algorithm using only 62 additions, almost matching the result of Beniamini et al. [ 5 ] . Recently, Stapleton developed a method for generating low-rank matrix multiplication schemes using a neural network [ 10 ] . By generating many schemes of rank 23 and reducing the number of additions using the implementations of Mårtensson and Stankovski Wagner, he found a 60-addition algorithm. We further combined Stapleton’s method to generate fast matrix multiplication schemes with Mårtensson and Stankovski Wagner’s method for reducing the number of additions to find a scheme requiring only 59 additions. The naive (unreduced) form of the scheme uses 110 additions and is specified in Table 1 . Our optimized scheme is specified in Table 2 , requiring only 59 additions. We use the compact indexing notation \begin{pmatrix}C_{0}&C_{1}&C_{2}\\ C_{3}&C_{4}&C_{5}\\ C_{6}&C_{7}&C_{8}\end{pmatrix}=\mathbf{C}=\mathbf{A}\mathbf{B}=\begin{pmatrix}A_{0}&A_{1}&A_{2}\\ A_{3}&A_{4}&A_{5}\\ A_{6}&A_{7}&A_{8}\end{pmatrix}\begin{pmatrix}B_{0}&B_{1}&B_{2}\\ B_{3}&B_{4}&B_{5}\\ B_{6}&B_{7}&B_{8}\end{pmatrix} . Finally, for convenience, in the Appendix we have specified the 59-algorithm on a form readable by the the software implementations of Mårtensson [ 6 ] and Stankovski Wagner [ 9 ] in Table 3 . More technical details on how the scheme was found, tools and methods used, as well as implications of the finding, will be included in an upcoming publication. \displaystyle M_{0} \displaystyle= \displaystyle\phantom{(}A_{1}B_{4} \displaystyle M_{1} \displaystyle= \displaystyle\phantom{(}A_{0}B_{1} \displaystyle M_{2} \displaystyle= \displaystyle(A_{3}-A_{4}-A_{5}+A_{6}-A_{7}-A_{8})B_{8} \displaystyle M_{3} \displaystyle= \displaystyle(A_{2}-A_{8})B_{8} \displaystyle M_{4} \displaystyle= \displaystyle(A_{3}-A_{5}+A_{6}-A_{8})B_{6} \displaystyle M_{5} \displaystyle= \displaystyle\hphantom{(}A_{2}B_{7} \displaystyle M_{6} \displaystyle= \displaystyle\hphantom{(}A_{0}B_{0} \displaystyle M_{7} \displaystyle= \displaystyle(A_{1}-A_{7})(B_{2}+B_{5}) \displaystyle M_{8} \displaystyle= \displaystyle\phantom{(}A_{5}(B_{4}+B_{5}-B_{6}-B_{7}-B_{8}) \displaystyle M_{9} \displaystyle= \displaystyle\phantom{(}A_{4}B_{3} \displaystyle M_{10} \displaystyle= \displaystyle(A_{0}-A_{1}-A_{6}+A_{7})B_{2} \displaystyle M_{11} \displaystyle= \displaystyle(A_{3}+A_{6}-A_{8})(B_{1}+B_{2}+B_{4}+B_{5}-B_{6}) \displaystyle M_{12} \displaystyle= \displaystyle(A_{1}+A_{6}-A_{7})(B_{2}+B_{4}+B_{5}) \displaystyle M_{13} \displaystyle= \displaystyle\phantom{(}A_{1}B_{3} \displaystyle M_{14} \displaystyle= \displaystyle(A_{1}+A_{3}+A_{6}-A_{7})(B_{2}-B_{3}+B_{5}) \displaystyle M_{15} \displaystyle= \displaystyle(A_{3}-A_{4}+A_{6}-A_{7})(B_{3}-B_{5}+B_{8}) \displaystyle M_{16} \displaystyle= \displaystyle(A_{3}-A_{4}-A_{5}+A_{6}-A_{7})(B_{4}+B_{5}-B_{8}) \displaystyle M_{17} \displaystyle= \displaystyle\phantom{(}A_{3}(B_{0}+B_{1}+B_{2}+B_{4}+B_{5}) \displaystyle M_{18} \displaystyle= \displaystyle(A_{3}-A_{4}-A_{5})(B_{4}+B_{5}) \displaystyle M_{19} \displaystyle= \displaystyle\phantom{(}A_{8}(B_{1}+B_{2}+B_{4}+B_{5}+B_{7}) \displaystyle M_{20} \displaystyle= \displaystyle\phantom{(}A_{2}B_{6} \displaystyle M_{21} \displaystyle= \displaystyle(A_{6}-A_{8})(B_{1}+B_{2}+B_{4}+B_{5}) \displaystyle M_{22} \displaystyle= \displaystyle(A_{3}+A_{6})(B_{0}-B_{2}+B_{3}-B_{5}+B_{6}) \displaystyle C_{0} \displaystyle= \displaystyle\phantom{-}M_{6}+M_{13}+M_{20} \displaystyle C_{1} \displaystyle= \displaystyle\phantom{-}M_{0}+M_{1}+M_{5} \displaystyle C_{2} \displaystyle= \displaystyle-M_{0}-M_{2}+M_{3}+M_{10}+M_{12}-M_{16}+M_{18} \displaystyle C_{3} \displaystyle= \displaystyle-M_{4}+M_{9}-M_{11}+M_{17}+M_{21} \displaystyle C_{4} \displaystyle= \displaystyle-M_{0}+M_{4}-M_{8}-M_{9}+M_{11}+M_{12}-M_{13}-M_{14}-M_{15}-M_{16}-M_{21} \displaystyle C_{5} \displaystyle= \displaystyle\phantom{-}M_{0}+M_{9}-M_{12}+M_{13}+M_{14}+M_{15}+M_{16}-M_{18} \displaystyle C_{6} \displaystyle= \displaystyle-M_{7}+M_{11}+M_{13}+M_{14}-M_{17}-M_{21}+M_{22} \displaystyle C_{7} \displaystyle= \displaystyle\phantom{-}M_{0}+M_{7}-M_{12}+M_{19}+M_{21} \displaystyle C_{8} \displaystyle= \displaystyle-M_{0}-M_{2}-M_{7}+M_{12}-M_{16}+M_{18} Table 1: Fast matrix multiplication algorithm with 110 additions (before reduction). Here we use compact indexing notation. The algorithm is specified in implementation order. Note that negation (negative leading term) is entirely avoided in implementations by rearranging terms. \displaystyle t_{0} \displaystyle= \displaystyle A_{3}+A_{6} \displaystyle t_{1} \displaystyle= \displaystyle A_{1}-A_{7} \displaystyle t_{2} \displaystyle= \displaystyle A_{4}+A_{5} \displaystyle t_{3} \displaystyle= \displaystyle A_{7}-t_{0} \displaystyle t_{4} \displaystyle= \displaystyle A_{6}+t_{1} \displaystyle t_{5} \displaystyle= \displaystyle A_{8}-t_{0} \displaystyle t_{6} \displaystyle= \displaystyle t_{2}+t_{3} \displaystyle u_{0} \displaystyle= \displaystyle B_{2}+B_{5} \displaystyle u_{1} \displaystyle= \displaystyle B_{4}+u_{0} \displaystyle u_{2} \displaystyle= \displaystyle B_{1}+u_{1} \displaystyle u_{3} \displaystyle= \displaystyle B_{4}+B_{5} \displaystyle u_{4} \displaystyle= \displaystyle B_{3}-u_{0} \displaystyle u_{5} \displaystyle= \displaystyle B_{8}-u_{3} \displaystyle M_{0} \displaystyle= \displaystyle\phantom{(}A_{1}B_{4} \displaystyle M_{1} \displaystyle= \displaystyle\phantom{(}A_{0}B_{1} \displaystyle M_{2} \displaystyle= \displaystyle(A_{8}+t_{6})B_{8} \displaystyle M_{3} \displaystyle= \displaystyle(A_{2}-A_{8})B_{8} \displaystyle M_{4} \displaystyle= \displaystyle(A_{5}+t_{5})B_{6} \displaystyle M_{5} \displaystyle= \displaystyle\phantom{(}A_{2}B_{7} \displaystyle M_{6} \displaystyle= \displaystyle\phantom{(}A_{0}B_{0} \displaystyle M_{7} \displaystyle= \displaystyle\phantom{(}t_{1}u_{0} \displaystyle M_{8} \displaystyle= \displaystyle\phantom{(}A_{5}(B_{6}+B_{7}+u_{5}) \displaystyle M_{9} \displaystyle= \displaystyle\phantom{(}A_{4}B_{3} \displaystyle M_{10} \displaystyle= \displaystyle(A_{0}-t_{4})B_{2} \displaystyle M_{11} \displaystyle= \displaystyle\phantom{(}t_{5}(B_{6}-u_{2}) \displaystyle M_{12} \displaystyle= \displaystyle\phantom{(}t_{4}u_{1} \displaystyle M_{13} \displaystyle= \displaystyle A_{1}B_{3} \displaystyle M_{14} \displaystyle= \displaystyle(t_{0}+t_{1})u_{4} \displaystyle M_{15} \displaystyle= \displaystyle(A_{4}+t_{3})(B_{3}-B_{5}+B_{8}) \displaystyle M_{16} \displaystyle= \displaystyle\phantom{(}t_{6}u_{5} \displaystyle M_{17} \displaystyle= \displaystyle\phantom{(}A_{3}(B_{0}+u_{2}) \displaystyle M_{18} \displaystyle= \displaystyle(A_{3}-t_{2})u_{3} \displaystyle M_{19} \displaystyle= \displaystyle\phantom{(}A_{8}(B_{7}+u_{2}) \displaystyle M_{20} \displaystyle= \displaystyle\phantom{(}A_{2}B_{6} \displaystyle M_{21} \displaystyle= \displaystyle(A_{6}-A_{8})u_{2} \displaystyle M_{22} \displaystyle= \displaystyle\phantom{(}t_{0}(B_{0}+B_{6}+u_{4}) \displaystyle v_{0} \displaystyle= \displaystyle\phantom{-}M_{0}-M_{12} \displaystyle v_{1} \displaystyle= \displaystyle\phantom{-}M_{16}+v_{0} \displaystyle v_{2} \displaystyle= \displaystyle\phantom{-}M_{11}-M_{21} \displaystyle v_{3} \displaystyle= \displaystyle\phantom{-}M_{14}-M_{13} \displaystyle v_{4} \displaystyle= \displaystyle\phantom{-}M_{18}-v_{1} \displaystyle v_{5} \displaystyle= \displaystyle\phantom{-}M_{2}+v_{4} \displaystyle v_{6} \displaystyle= \displaystyle\phantom{-}M_{4}+M_{9} \displaystyle v_{7} \displaystyle= \displaystyle\phantom{-}M_{15}+v_{3} \displaystyle v_{8} \displaystyle= \displaystyle\phantom{-}M_{17}-v_{2} \displaystyle C_{0} \displaystyle= \displaystyle\phantom{-}M_{6}+M_{13}+M_{20} \displaystyle C_{1} \displaystyle= \displaystyle\phantom{-}M_{0}+M_{1}+M_{5} \displaystyle C_{2} \displaystyle= \displaystyle\phantom{-}M_{3}+M_{10}+v_{5} \displaystyle C_{3} \displaystyle= \displaystyle\phantom{-}v_{6}+v_{8} \displaystyle C_{4} \displaystyle= \displaystyle\phantom{-}M_{8}-v_{1}+v_{2}-v_{6}+v_{7} \displaystyle C_{5} \displaystyle= \displaystyle\phantom{-}M_{9}-v_{4}-v_{7} \displaystyle C_{6} \displaystyle= \displaystyle-M_{7}+M_{22}-v_{3}-v_{8}

Read the complete text