pith. sign in

arxiv: 2604.27645 · v1 · submitted 2026-04-30 · 💻 cs.DS · cs.CC

An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication

Yinqi Sun This is my paper

Pith reviewed 2026-05-07 04:59 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords matrix multiplicationbilinear algorithmstensor rank3x3 matricesaddition minimizationBrent equationsstraight-line programs
0
0 comments X

The pith

A rank-23 algorithm computes any 3x3 matrix product with 56 additions and 23 multiplications.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an explicit bilinear straight-line program for multiplying two general 3 by 3 matrices over any associative ring. The program performs 23 multiplications of linear forms in the input entries followed by 56 additions and subtractions to obtain all nine output entries. All coefficients are restricted to the set {-1, 0, 1}. This yields a total of 79 scalar operations and improves on earlier rank-23 schemes that required 58 or more additions. A sympathetic reader cares because matrix multiplication is a basic building block whose operation count directly affects the cost of many linear-algebra computations when the same scheme is applied recursively.

Core claim

The paper gives a concrete straight-line program consisting of 23 multiplications of linear combinations of the input matrix entries, followed by 56 additions and subtractions to produce the nine entries of the output matrix. The coefficients are all in {-1,0,1}, and the program is verified to be correct by checking that it satisfies the 729 Brent equations over the integers along with additional tests in finite fields and noncommutative settings.

What carries the argument

The bilinear algorithm defined by 23 specific linear forms whose products are then combined by 56 additions and subtractions to recover each entry of the 3x3 product matrix.

If this is right

  • This scheme uses fewer additions than any previously published rank-23 algorithm for 3x3 matrix multiplication.
  • The algorithm remains valid when the coefficient ring is non-commutative.
  • Because every coefficient lies in {-1,0,1}, the linear forms can be evaluated using only additions, subtractions, and sign changes.
  • The total operation count of 79 scalar operations is the new record for exact rank-23 schemes in the bilinear model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Recursive use of this scheme on larger block matrices could lower the leading-term exponent for matrix multiplication below what is currently obtained from known decompositions.
  • The ternary-coefficient property may permit especially efficient implementations in exact-arithmetic libraries or on hardware that treats multiplication as more expensive than addition.
  • The same search method that produced the 56-addition scheme might be applied to look for rank-22 or lower algorithms for 3x3 multiplication.

Load-bearing premise

The chosen coefficients for the 23 multiplications and 56 additions satisfy all 729 Brent equations exactly over the integers.

What would settle it

Symbolic expansion of the straight-line program over the integers and direct comparison of the resulting nine output expressions against the standard formulas for the entries of the matrix product; any coefficient mismatch disproves the claim.

read the original abstract

We present a rank-$23$ algorithm for general $3\times3$ matrix multiplication that uses $56$ additions/subtractions and $23$ multiplications, for a total of $79$ scalar operations in the standard bilinear straight-line model. This improves the recent sequence of $60$-, $59$-, and $58$-addition rank-$23$ schemes. The algorithm works over arbitrary associative, possibly noncommutative, coefficient rings. Its tensor coefficients are ternary, meaning that every coefficient lies in $\{-1,0,1\}$. Correctness is certified by the $729$ Brent equations over $\mathbb{Z}$, and the verifier also expands the straight-line program and performs additional finite-field and noncommutative implementation tests.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents an explicit bilinear straight-line scheme for multiplying two general 3×3 matrices over an arbitrary associative ring. The scheme uses exactly 23 multiplications whose input linear forms have coefficients in {-1,0,1} together with 56 additions/subtractions, for a total of 79 scalar operations. Correctness is certified by a computer-assisted check that the 729 Brent equations hold with equality over ℤ, supplemented by finite-field and non-commutative implementation tests. The result improves the additive complexity of the best previously known rank-23 schemes (58 additions).

Significance. If the verification is sound, the construction supplies a concrete, parameter-free improvement in the additive cost of exact 3×3 matrix multiplication while preserving the optimal multiplication count of 23 and the ternary coefficient restriction. The machine-checked symbolic verification over ℤ together with the supplementary finite-field and non-commutative tests constitutes a reproducible, falsifiable certificate; this is a methodological strength that raises the evidential bar for future work in the area.

major comments (2)
  1. [§4] §4 (Verification): the central correctness claim rests on the custom verifier establishing that all 729 Brent equations hold exactly over ℤ. Because no hand-derived algebraic identity is supplied, the manuscript must make the verifier source code (or a fully detailed pseudocode description together with the explicit coefficient lists) available as supplementary material so that independent reproduction is possible and the risk of an undetected implementation error is minimized.
  2. [§3] §3 (The Scheme): the straight-line program realizing the 56 additions must be presented with an explicit accounting of common subexpressions so that the addition count can be verified by direct inspection rather than by trusting the final tally alone.
minor comments (2)
  1. [Abstract] The abstract and title use inconsistent notation ('3*3' versus '3×3'); adopt a single mathematical symbol throughout.
  2. [Introduction] The introduction refers to the 'recent sequence of 60-, 59-, and 58-addition rank-23 schemes' but does not supply bibliographic citations for those works; add the missing references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for the constructive comments aimed at improving reproducibility. We address each major comment below and will incorporate the suggested changes into the revised manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (Verification): the central correctness claim rests on the custom verifier establishing that all 729 Brent equations hold exactly over ℤ. Because no hand-derived algebraic identity is supplied, the manuscript must make the verifier source code (or a fully detailed pseudocode description together with the explicit coefficient lists) available as supplementary material so that independent reproduction is possible and the risk of an undetected implementation error is minimized.

    Authors: We agree that independent reproduction requires access to the verification tools. In the revised version we will release the complete source code of the custom verifier as supplementary material. We will also augment §4 with a self-contained pseudocode description of the verification procedure together with the explicit coefficient lists for all linear forms, so that the 729 Brent equations can be checked without relying on the original implementation. revision: yes

  2. Referee: [§3] §3 (The Scheme): the straight-line program realizing the 56 additions must be presented with an explicit accounting of common subexpressions so that the addition count can be verified by direct inspection rather than by trusting the final tally alone.

    Authors: We accept the point that an explicit accounting is needed for independent verification of the addition count. We will expand §3 to display the full straight-line program, explicitly identifying every common subexpression and providing a line-by-line tally that confirms the total of 56 additions/subtractions. This presentation will allow direct inspection while preserving the readability of the algorithm description. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit scheme verified against independent Brent equations

full rationale

The paper constructs an explicit bilinear scheme consisting of 23 multiplications with ternary coefficients and 56 linear combinations, then certifies correctness by direct symbolic verification that the scheme satisfies the 729 Brent equations over Z (plus finite-field and non-commutative checks). The Brent equations are the external, standard definition of what it means for such a scheme to compute the 3x3 matrix product; they are not derived from or fitted to the paper's own construction. No parameter is tuned to the target result, no self-citation supplies a load-bearing uniqueness theorem or ansatz, and the verification is machine-checkable against an independent benchmark. The derivation is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The construction relies on the standard definition of bilinear algorithms and the Brent equations that encode correctness for matrix multiplication. No free parameters are introduced; the coefficients are discrete values in {-1,0,1} found by search and then verified. No new entities are postulated.

axioms (2)
  • domain assumption The underlying ring is associative (but not necessarily commutative).
    The abstract states that the algorithm works over arbitrary associative, possibly noncommutative, coefficient rings.
  • standard math The 729 Brent equations are necessary and sufficient for a bilinear algorithm to compute 3x3 matrix multiplication exactly.
    These polynomial identities are the standard algebraic condition used to certify matrix-multiplication algorithms.

pith-pipeline@v0.9.0 · 5419 in / 1599 out tokens · 63308 ms · 2026-05-07T04:59:36.874545+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 4 canonical work pages

  1. [1]

    Sparsifying the operators of fast matrix multiplication algorithms.arXiv preprint arXiv:2008.03759, 2020

    Gal Beniamini, Nathan Cheng, Olga Holtz, Elaye Karstadt, and Oded Schwartz. Sparsifying the operators of fast matrix multiplication algorithms.arXiv preprint arXiv:2008.03759, 2020. 5

    work page arXiv 2008

  2. [2]

    Richard P. Brent. Algorithms for matrix multiplication. Stanford Computer Science Report STAN-CS-70-157, 1970

    1970

  3. [3]

    Matrix multiplication, a little faster.Journal of the ACM, 67(1):1–31, 2020

    Elaye Karstadt and Oded Schwartz. Matrix multiplication, a little faster.Journal of the ACM, 67(1):1–31, 2020

    2020

  4. [4]

    Laderman

    Julian D. Laderman. A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications.Bulletin of the American Mathematical Society, 82(1):126–128, 1976

    1976

  5. [5]

    The number of the beast: reducing additions in fast matrix multiplication algorithms for dimensions up to 666

    Erik M˚ artensson and Paul Stankovski Wagner. The number of the beast: reducing additions in fast matrix multiplication algorithms for dimensions up to 666. InProceedings of the Conference on Applied and Computational Discrete Algorithms, pages 47–60. SIAM, 2025

    2025

  6. [6]

    A rank 23 algorithm for mul- tiplying 3×3 matrices with an arithmetic complexity of 59.arXiv preprint arXiv:2601.05272, 2025

    Erik M˚ artensson, Paul Stankovski Wagner, and Joshua Stapleton. A rank 23 algorithm for mul- tiplying 3×3 matrices with an arithmetic complexity of 59.arXiv preprint arXiv:2601.05272, 2025

    work page arXiv 2025

  7. [7]

    Perminov

    Andrew I. Perminov. A 58-addition, rank-23 scheme for general 3×3 matrix multiplication. arXiv preprint arXiv:2512.21980, 2025

    work page arXiv 2025

  8. [8]

    Alexey V. Smirnov. The bilinear complexity and practical algorithms for matrix multiplication. Computational Mathematics and Mathematical Physics, 53:1781–1795, 2013

    2013

  9. [9]

    A 60-addition, rank-23 scheme for exact 3×3 matrix multiplication.arXiv preprint arXiv:2508.03857, 2025

    Joshua Stapleton. A 60-addition, rank-23 scheme for exact 3×3 matrix multiplication.arXiv preprint arXiv:2508.03857, 2025

    work page arXiv 2025

  10. [10]

    Gaussian elimination is not optimal.Numerische Mathematik, 13:354–356, 1969

    Volker Strassen. Gaussian elimination is not optimal.Numerische Mathematik, 13:354–356, 1969

    1969

  11. [11]

    On multiplication of 2×2 matrices.Linear Algebra and its Applications, 4(4):381–388, 1971

    Shmuel Winograd. On multiplication of 2×2 matrices.Linear Algebra and its Applications, 4(4):381–388, 1971. 6

    1971