New faster method multiplies 3 by 3 matrices using fewer additions

A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization

Mathematical SoftwareComputational ComplexityData Structures and AlgorithmsSymbolic Computation

Summary

Multiplying two 3×3 matrices usually takes many steps. The authors found a way to do it with one less addition operation than the previous best method, making the process slightly more efficient. Their approach uses exact math techniques and even verified the method using a computer proof checker. This means computers can multiply matrices a bit faster without changing how the data is arranged.

What this means in practice

Authors

Greg Sidebottom

Abstract

We give a scheme that multiplies two $3\times3$ matrices with 23 multiplications and 55 additions over any ring, one addition below the previous record of 56 (Sun, 2026) and the first below 56 for exact non-commutative $3\times3$ multiplication without a change of basis. The scheme forms 13 signed combinations of the entries of A and 14 of B, takes 23 products, and recombines them with 28 further additions; its correctness is machine-checked in Lean 4. The previous records, from 60 down to 56, were obtained by greedy common-subexpression elimination, which only bounds each side of a scheme from above. We minimize both input sides exactly by chain covering, and the output side exactly through the transposition principle: the 9-by-23 output map costs its transpose plus 14, and the transpose is a 9-input map that the input-side minimizer solves exactly. Applied to Perminov's cn122 scheme (class i19w225c4efh, published at 58 additions) this gives 55 = 13 + 14 + 28, where greedy elimination reaches only 29 on the output side. The same method shows that Sun's representative is output-optimal at 56, and an exact orbit-wide computation over the Heule-Kauers-Seidl database shows that the record class is the only database class attaining 55.