pith. sign in

arxiv: 2606.02480 · v2 · pith:RGSWVN6Bnew · submitted 2026-06-01 · 💻 cs.SC

Meta Flip Graph meets Serendipitous Product: new Fast Matrix Multiplication results

A. I. Perminov This is my paper

Pith reviewed 2026-06-28 11:13 UTC · model grok-4.3

classification 💻 cs.SC
keywords matrix multiplicationfast algorithmsrectangular formatsasymptotic exponentternary schemesmeta flip graphserendipitous product
0
0 comments X

The pith

The meta flip graph extended to 680 formats and paired with the serendipitous product improves multiplication ranks for 207 small rectangular cases.

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

The paper extends an existing enumeration method to every rectangular matrix multiplication format whose dimensions are at most 16 by 16 by 16. It then applies a known product construction to generate new multiplication schemes and measures their ranks. The result is lower ranks in 207 formats, the appearance of ternary-coefficient schemes in 84 formats that previously used only integer or rational coefficients, and 23 additional schemes whose asymptotic exponent falls below log base 2 of 7. These changes also shift the overall catalog to 375 ternary schemes, 18 integer schemes, and 287 rational schemes.

Core claim

Extending the meta flip graph to all 680 rectangular formats up to size 16 by 16 by 16 and combining it with the serendipitous product construction produces multiplication schemes whose ranks are strictly smaller than all previously published schemes for 207 formats, supplies the first ternary schemes for 84 formats, and adds 23 new schemes satisfying ω less than log base 2 of 7.

What carries the argument

The meta flip graph enumeration extended across all 680 rectangular formats, used in tandem with the serendipitous product construction to generate and rank multiplication schemes.

If this is right

  • 207 formats now possess multiplication schemes of lower rank than any previously published scheme.
  • 84 formats gain their first known ternary-coefficient schemes.
  • The total number of known schemes with asymptotic exponent below log base 2 of 7 rises from 29 to 52.
  • Across all 680 formats the coefficient-type counts stand at 375 ternary, 18 integer, and 287 rational.

Where Pith is reading between the lines

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

  • The new schemes could be substituted directly into existing matrix-multiplication libraries to reduce the number of scalar multiplications required for those dimensions.
  • Because the schemes and code are released openly, independent groups can test them on concrete hardware or attempt to combine them with other algebraic identities.
  • The same enumeration-plus-product approach might be applied to formats slightly larger than 16 cubed or to related problems such as tensor decomposition.

Load-bearing premise

The enumeration and construction steps produce only correct multiplication schemes whose reported ranks are not caused by search gaps or validation mistakes.

What would settle it

An independent recomputation that either shows one of the 23 new schemes fails to multiply the input matrices or finds a scheme of strictly lower rank for any of the 207 formats claimed to be improved.

Figures

Figures reproduced from arXiv: 2606.02480 by A. I. Perminov.

Figure 1
Figure 1. Figure 1: illustrates this product: a 2 × 2 row multiplied by a 2 × 3 row produces a 4 × 6 row. The figure shows the general case with dimensions n1, m1, n2, m2. 𝑢2 (𝑗) ∈ 𝔽 𝑛2×𝑚2 𝑢1 (𝑖) ∈ 𝔽 𝑛1×𝑚1 𝑢1 (𝑖) ⊗ 𝑢2 (𝑗) ∈ 𝔽 𝑛1𝑛2 × 𝑚1𝑚2 = = ⊗ [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Kronecker product of a single u (i) 1 from the first scheme with all r2 rows u (1) 2 , . . . , u (r2) 2 from the second scheme. The result is r2 rows for the U tensor of the resulting scheme, each of size (n1n2) × (m1m2). For the U tensor, the construction is identical to the trivial block using the common u (i1) 1 -vector: u (j) = u (i1) 1 ⊗ u (j) 3 . For the V tensor, each entry is formed by summing cont… view at source ↗
Figure 3
Figure 3. Figure 3: Serendipitous product for a ⟨1, 1, 2⟩ block multiplied by one row of the third scheme (n2, m2, 2p2 : r ′ 2 ). The common u-vector yields one row of U; V and W sum contributions from both indices across the two blocks. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
read the original abstract

This paper presents new results for fast matrix multiplication in small formats obtained by combining the meta flip graph framework with the serendipitous product construction. The framework has been extended to support all 680 rectangular formats with dimensions up to $16 \times 16 \times 16$. Compared to the previous state of the art, ranks are improved for 207 formats. For 84 formats, ternary schemes are found where previously only integer or rational coefficients were known. Additionally, 23 new schemes with asymptotic exponent $\omega < \log_2 7$ are discovered, bringing the total number of such schemes to 52. The overall distribution of coefficient types across all investigated formats is 375 ternary, 18 integer, and 287 rational. All code and discovered schemes are available as open source.

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

0 major / 2 minor

Summary. The paper extends the meta flip graph framework to enumerate multiplication schemes over all 680 rectangular formats with dimensions ≤16×16×16, then applies the serendipitous product construction. It reports rank improvements for 207 formats, discovery of ternary schemes for 84 formats previously known only with integer or rational coefficients, and 23 new schemes satisfying ω < log₂ 7 (raising the total to 52). Coefficient-type distribution across all formats is stated as 375 ternary, 18 integer, and 287 rational. All code and discovered schemes are released as open source.

Significance. If the enumerated schemes are valid, the work materially enlarges the catalog of low-rank matrix-multiplication algorithms for small formats and supplies the first systematic ternary-coefficient results for many of them. The open-source release of both code and explicit schemes constitutes a verifiable, reusable artifact that directly supports further research in algebraic complexity.

minor comments (2)
  1. [Results] A compact table (or supplementary file) listing the 207 improved formats together with previous and new ranks would make the magnitude of the improvements immediately assessable rather than leaving readers to consult the open-source repository.
  2. [Method] The description of the extended meta-flip-graph search parameters (depth limits, coefficient-field handling, pruning heuristics) should be expanded by one paragraph so that the enumeration can be understood without immediate recourse to the source code.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and the recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No circularity: explicit computational enumeration with released code

full rationale

The paper reports rank improvements and new multiplication schemes obtained by extending an existing enumeration framework (meta flip graph) and applying a construction (serendipitous product) across 680 formats. No equations, fitted parameters, or predictions appear; the central claims are direct outputs of a search whose validity is externally checkable because all code and discovered schemes are released as open source. No self-definitional steps, fitted-input predictions, or load-bearing self-citations that reduce the result to its inputs are present. The derivation chain is therefore self-contained as a reproducible computation rather than a closed-form derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, background axioms, or new entities introduced by the frameworks.

pith-pipeline@v0.9.1-grok · 5658 in / 1074 out tokens · 24321 ms · 2026-06-28T11:13:28.834424+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

25 extracted references · 10 canonical work pages · 2 internal anchors

  1. [1]

    Gaussian elimination is not optimal.Numerische mathematik, 13(4):354–356, 1969

    V olker Strassen. Gaussian elimination is not optimal.Numerische mathematik, 13(4):354–356, 1969

    1969

  2. [2]

    Yet another catalogue of fast matrix multiplication algorithms, 2019.URL: http://fmm

    Alexandre Sedoglavic. Yet another catalogue of fast matrix multiplication algorithms, 2019.URL: http://fmm. univ-lille. fr, accessed: march, 2025

    2019

  3. [3]

    Local search for fast matrix multiplication

    Marijn JH Heule, Manuel Kauers, and Martina Seidl. Local search for fast matrix multiplication. InInternational Conference on Theory and Applications of Satisfiability Testing, pages 155–163. Springer, 2019

    2019

  4. [4]

    New ways to multiply 3× 3-matrices.Journal of Symbolic Computation, 104:899–916, 2021

    Marijn JH Heule, Manuel Kauers, and Martina Seidl. New ways to multiply 3× 3-matrices.Journal of Symbolic Computation, 104:899–916, 2021

    2021

  5. [5]

    Ruling out low-rank matrix multiplication tensor decompositions with symmetries via sat.arXiv preprint arXiv:2402.01011, 2024

    Jason Yang. Ruling out low-rank matrix multiplication tensor decompositions with symmetries via sat.arXiv preprint arXiv:2402.01011, 2024

    work page arXiv 2024

  6. [6]

    Fast matrix multiplication without tears: A constraint programming approach.arXiv preprint arXiv:2306.01097, 2023

    Arnaud Deza, Chang Liu, Pashootan Vaezipoor, and Elias B Khalil. Fast matrix multiplication without tears: A constraint programming approach.arXiv preprint arXiv:2306.01097, 2023

    work page arXiv 2023

  7. [7]

    The bilinear complexity and practical algorithms for matrix multiplication.Computational Mathematics and Mathematical Physics, 53(12):1781–1795, 2013

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

    2013

  8. [8]

    Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al

    Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al. Discovering faster matrix multiplication algorithms with reinforcement learning.Nature, 610(7930):47–53, 2022

    2022

  9. [9]

    AlphaEvolve: A coding agent for scientific and algorithmic discovery

    Alexander Novikov, Ngân V˜u, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco JR Ruiz, Abbas Mehrabian, et al. Alphaevolve: A coding agent for scientific and algorithmic discovery.arXiv preprint arXiv:2506.13131, 2025. 14 Meta Flip Graph meets Serendipitous Product: new Fast Matrix Mult...

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  10. [10]

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

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

    work page arXiv 2025

  11. [11]

    A network that learns strassen multiplication.Journal of Machine Learning Research, 17(116):1–13, 2016

    Veit Elser. A network that learns strassen multiplication.Journal of Machine Learning Research, 17(116):1–13, 2016

    2016

  12. [12]

    Flip graphs for matrix multiplication

    Manuel Kauers and Jakob Moosbauer. Flip graphs for matrix multiplication. InProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, pages 381–388, 2023

    2023

  13. [13]

    Adaptive flip graph algorithm for matrix multiplication

    Yamato Arai, Yuma Ichikawa, and Koji Hukushima. Adaptive flip graph algorithm for matrix multiplication. In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, pages 292–298, 2024

    2024

  14. [14]

    Flip graphs with symmetry and new matrix multiplication schemes

    Jakob Moosbauer and Michael Poole. Flip graphs with symmetry and new matrix multiplication schemes. In Proceedings of the 2025 International Symposium on Symbolic and Algebraic Computation, pages 233–239, 2025

    2025

  15. [15]

    Exploring the meta flip graph for matrix multiplication.arXiv preprint arXiv:2510.19787, 2025

    Manuel Kauers and Isaac Wood. Exploring the meta flip graph for matrix multiplication.arXiv preprint arXiv:2510.19787, 2025

    work page arXiv 2025

  16. [16]

    Fast matrix multiplication via ternary meta flip graphs.arXiv preprint arXiv:2511.20317, 2025

    Andrew I Perminov. Fast matrix multiplication via ternary meta flip graphs.arXiv preprint arXiv:2511.20317, 2025

    work page arXiv 2025

  17. [17]

    Fast matrix multiplication in small formats: Discovering new schemes with an open-source flip graph framework.arXiv preprint arXiv:2603.02398, 2026

    Andrew I Perminov. Fast matrix multiplication in small formats: Discovering new schemes with an open-source flip graph framework.arXiv preprint arXiv:2603.02398, 2026

    work page arXiv 2026

  18. [18]

    Fast matrix multiplication formulae

    Warren Douglas Smith. Fast matrix multiplication formulae. Technical report, 2002

    2002

  19. [19]

    Algorithms for matrix multiplication

    Richard P Brent. Algorithms for matrix multiplication. Technical report, Stanford University Stanford, 1970

    1970

  20. [20]

    Exploiting the Structure in Tensor Decompositions for Matrix Multiplication

    Manuel Kauers, Jakob Moosbauer, and Isaac Wood. Exploiting the structure in tensor decompositions for matrix multiplication.arXiv preprint arXiv:2602.11041, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  21. [21]

    Complex to rational fast matrix multiplication.arXiv preprint arXiv:2602.13171, 2026

    Yoav Moran, Oded Schwartz, and Shuncheng Yuan. Complex to rational fast matrix multiplication.arXiv preprint arXiv:2602.13171, 2026

    work page arXiv 2026

  22. [22]

    On why and how to minimize the arithmetic complexity of fast matrix multiplication algorithms.Cryptology ePrint Archive, 2026

    Erik Mårtensson and Paul Stankovski Wagner. On why and how to minimize the arithmetic complexity of fast matrix multiplication algorithms.Cryptology ePrint Archive, 2026

    2026

  23. [23]

    Plinopt: optimization of linear, bilinear & trilinear programs

    Jean-Guillaume Dumas, Bruno Grenet, Clément Pernet, and Alexandre Sedoglavic. Plinopt: optimization of linear, bilinear & trilinear programs. 2024

    2024

  24. [24]

    Towards automated generation of fast and accurate algorithms for recursive matrix multiplication.Journal of Symbolic Computation, page 102524, 2025

    Jean-Guillaume Dumas, Clément Pernet, and Alexandre Sedoglavic. Towards automated generation of fast and accurate algorithms for recursive matrix multiplication.Journal of Symbolic Computation, page 102524, 2025

    2025

  25. [25]

    Parallel heuristic exploration for additive complexity reduction in fast matrix multiplication

    Andrew I Perminov. Parallel heuristic exploration for additive complexity reduction in fast matrix multiplication. arXiv preprint arXiv:2512.13365, 2025. URLhttps://arxiv.org/abs/2512.13365. 15

    work page arXiv 2025