2026-10-07
Matrix multiplication sits underneath a huge amount of modern computing, from statistics and genomics to graphics and machine learning. Faster algorithms reduce the number of scalar multiplications by reorganising the calculation.
Recent work in OpenAI’s mathematics repository motivated us to build fast_mm_search, which searches for exact fast matrix-multiplication rules without being given a known construction. In An Upper Bound of 9/4 for the Matrix Multiplication Exponent, OpenAI proves \(\omega \leq 9/4\) over \(\mathbb{C}\).
The first validation succeeded. Starting from random coefficients and without being given Strassen’s formula, fast_mm_search independently recovered and exactly verified a seven-product \(2\times2\) matrix-multiplication algorithm. Its equations differ from the familiar textbook form of Strassen’s algorithm while achieving the same exact rank-7 result.
The code and reproducible results are available in the
fast_mm_search repo.
Why do seven products matter?
For two \(2\times2\) matrices, ordinary multiplication uses 8 scalar multiplications. In 1969, Volker Strassen showed that the same result could be computed exactly using 7. Recursion compounds this one-product saving:
\[2\times2:\quad 8 \rightarrow 7\] \[4\times4:\quad 64 \rightarrow 49\] \[8\times8:\quad 512 \rightarrow 343\] \[16\times16:\quad 4096 \rightarrow 2401\]The recursive rule reduces the asymptotic exponent of matrix multiplication from \(3\) to
\[\log_2 7 \approx 2.807.\]A larger matrix can be divided into blocks, with the same small multiplication rule applied to those blocks recursively. A single improvement at the finite level can therefore change the asymptotic arithmetic cost.
Find a better small multiplication rule, then reuse it recursively on larger matrices.
What changed with the new result?
Research since Strassen has continued to reduce the upper bound on the matrix-multiplication exponent. OpenAI’s recent result gives
\[\omega \leq \frac{9}{4}=2.25\]over \(\mathbb{C}\), corresponding to square matrix multiplication complexity
\[O_\varepsilon\left(n^{9/4+\varepsilon}\right).\]Very roughly,
\[\text{ordinary multiplication} \sim n^3\] \[\text{Strassen} \sim n^{2.807}\] \[\text{new upper bound} \sim n^{2.25+\varepsilon}.\]Strassen’s result gives an explicit finite recipe: the seven products can be written down and implemented directly. The \(9/4\) theorem is asymptotic and does not specify a small competitive finite rule with explicit coefficients.
This suggests a constructive search problem:
Can we search for explicit finite multiplication rules, prove them exactly, and then reuse them recursively?
What did the search find?
fast_mm_search starts with random coefficients and optimises them against the matrix-multiplication tensor. Promising numerical candidates are reconstructed as exact rational coefficients and passed to a separate exact verifier.
\(\text{random search} \rightarrow \text{numerical candidate} \rightarrow \text{exact formula} \rightarrow \text{independent verification}.\)
The validation campaign tested independent random starting points until an exact rule was found. Seed 581 reached a relative numerical residual of \(3.09\times10^{-8}.\)
Rational reconstruction then produced exact coefficients that passed independent verification.
For
\[A= \begin{pmatrix} a & b\\ c & d \end{pmatrix}, \qquad B= \begin{pmatrix} e & f\\ g & h \end{pmatrix},\]the search found
\[\begin{aligned} P_1 &= (b-d)h\\ P_2 &= a(e+f+g+h)\\ P_3 &= (a-b)(g+h)\\ P_4 &= (a-c)f\\ P_5 &= (c-d)e\\ P_6 &= d(e+g)\\ P_7 &= (a-d)(e+g+h). \end{aligned}\]The output is reconstructed as
\(AB= \begin{pmatrix} -P_1-P_3+P_6+P_7 & P_1+P_2-P_6-P_7\\ P_5+P_6 & P_2-P_4-P_6-P_7 \end{pmatrix}.\)
Expanding these expressions gives exactly
\(AB= \begin{pmatrix} ae+bg & af+bh\\ ce+dg & cf+dh \end{pmatrix}.\)
The residual \(3.09\times10^{-8}\) describes the numerical search stage. Exact reconstruction converts the candidate into an integer-coefficient identity, and the independent verifier then checks the complete matrix-multiplication tensor. The verified result has zero mismatches and zero exact residual.
A concrete example
For
\[A= \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}, \qquad B= \begin{pmatrix} 5 & 6\\ 7 & 8 \end{pmatrix},\]both ordinary multiplication and the recovered seven-product algorithm give
\[AB= \begin{pmatrix} 19 & 22\\ 43 & 50 \end{pmatrix}.\]The following Python implements the two calculations independently:
def standard_mm(A, B):
return [
[
sum(A[i][k] * B[k][j] for k in range(2))
for j in range(2)
]
for i in range(2)
]
def discovered_mm(A, B):
a, b = A[0]
c, d = A[1]
e, f = B[0]
g, h = B[1]
P1 = (b - d) * h
P2 = a * (e + f + g + h)
P3 = (a - b) * (g + h)
P4 = (a - c) * f
P5 = (c - d) * e
P6 = d * (e + g)
P7 = (a - d) * (e + g + h)
return [
[
-P1 - P3 + P6 + P7,
P1 + P2 - P6 - P7,
],
[
P5 + P6,
P2 - P4 - P6 - P7,
],
]
A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
standard = standard_mm(A, B)
discovered = discovered_mm(A, B)
print("Standard: ", standard)
print("Discovered:", discovered)
print("Match: ", standard == discovered)
assert standard == discovered
which prints
Standard: [[19, 22], [43, 50]]
Discovered: [[19, 22], [43, 50]]
Match: True
The complete verification checks the symbolic identity across all tensor coefficients; this numerical example provides a direct implementation check.
What does this establish?
The classical \(2\times2\), rank-7 result serves here as a validation target. fast_mm_search recovered an exact seven-product algorithm from random initial coefficients without access to Strassen’s formula, and the resulting coefficient representation differs from the familiar textbook construction.
This validates the numerical search, exact reconstruction and independent verification pipeline. The same machinery can now be applied to finite \((u,r)\) problems whose solutions are unknown.
Technical details
Before the longer campaign, we ran an eight-restart validation benchmark. Each restart began from different random coefficients and searched for a \(2\times2\), rank-7 decomposition. Seven of the eight restarts reached the numerical-candidate threshold, with a best relative residual of \(3.67\times10^{-8}.\) Our benchmark produced numerical candidates without an exact verified identity.
Residual during numerical optimisation for the eight independent validation restarts. Lower is better.
Final residual for each restart. Exact verification is the acceptance criterion.
The subsequent campaign continued with independent starting points. Seed 581 converged after 140 optimisation iterations to \(3.09\times10^{-8}.\) Exact reconstruction succeeded for this candidate, and the independent verifier reported zero mismatches and zero exact residual.
The successful numerical search. Exact reconstruction and independent verification followed numerical convergence.
The plots show the numerical optimisation stage. Acceptance requires the reconstructed coefficients to satisfy the complete matrix-multiplication identity exactly.
Original Strassen paper
The original 1969 paper is three pages long.
References
-
V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik 13 (1969), 354–356.
-
OpenAI. An Upper Bound of 9/4 for the Matrix Multiplication Exponent. October 2, 2026. OpenAI mathematics repository.
