📝 Paper on arXiv: https://arxiv.org/abs/2606.13408
🌐 Live catalog browser: https://www.solven.eu/matmulcatalog/
📄 Download latest paper PDF: https://raw.githubusercontent.com/solven-eu/matmulcatalog/paper-pdf/paper.pdf — rebuilt on every push to master by the paper workflow.
A research-grade catalog and exploration toolchain for fast matrix
multiplication algorithms — bilinear tensor decompositions for ⟨n,m,p⟩
matmul. Combines a verified-on-disk algorithm corpus (~2,400 schemes spanning
Strassen 1969 → AlphaEvolve 2025), composition tools that drive ⟨32,32,32⟩
from small base algorithms, and a SAT pipeline for over-rank certification.
The primary objective of this work is multiplication rank for small
matrices — the number of multiplications r in a bilinear scheme for
⟨n,m,p⟩, currently max(n,m,p) < 32. That is the number the catalog is
organised around and the axis on which we track the state of the art.
Additions are a secondary objective. We do look into the additive complexity of a scheme — and we track improvements on it (fewer additions for the same rank is a real, citable result) — but it is not the main axis of this catalog. Concretely:
- For schemes where we compute one, we publish a straight-line program (SLP) with a small addition count.
- These addition counts are almost always upper bounds, not proven
minima: our SLP minimiser is a greedy, cancellation-free heuristic
(see the Optimality discipline note in
CLAUDE.md—min_additionsis abound, not an optimum). Treat a published addition count as "≤ this many additions", never as "the minimum".
Tooling for evaluating / reducing an SLP. If you want to verify or improve the addition count of a scheme, several external projects help (and go well beyond our greedy heuristic):
- github.com/werekorren/fmm_add_reduction — additive-complexity reduction for known fast-matmul schemes.
- github.com/dronperminov/ternary_addition_reducer
— addition reduction for ternary
{-1, 0, +1}schemes (Perminov; see arXiv:2512.13365 in REFERENCES.md [78]). - github.com/jgdumas/plinopt — Dumas et al.'s linear/bilinear-program optimiser. Not limited to ZT/ternary — it handles general (e.g. rational) coefficients, so it is the broadest of the three.
- Catalog browser (GitHub Pages) — interactive UI: filter the 2,300+ scheme catalog by field, max-dimension, source, shape; links straight to each scheme's JSON. Source under docs/.
- INTRODUCTION.md — gentle introduction for readers with no prior background. Covers what a matrix is, what matmul is, why anyone cares about saving multiplications, Strassen's 1969 discovery, divide-and-conquer recursion, fields vs rings, commutativity, and how the two interact with recursive matmul.
- SMALL_MATMUL_CATALOG.md — narrative per-format synthesis: who/when/source, recursive composition framework, AlphaEvolve / AlphaTensor / Perminov sources.
- COVERAGE.md — auto-generated coverage matrix
(format × field → ✓ verified scheme / 📄 literature only / —). Sections
organized by
max(n,m,p); regenerated byCoverageMatrixGenerator. - OMEGA_HISTORY.md — per-field timelines of ω improvements and small-format rank evolution.
- RANK_KNOWLEDGE.md — theoretical rank/border-rank bounds; cross-field transfer rules (§1.2bis).
- REFERENCES.md — central bibliography (numbered
[1]..[N], BibTeX blocks, per-entry annotations and back-links). - NEW_BOUNDS.md — strict improvements over DIS09 Tables 3 (NC) & 4 (commutative) that this repository establishes via its multi-base + Pan TA + paired-subproducts pipeline. 4 NC + 14 commutative wins as of 2026-05-28.
- SEARCH_STRATEGY.md — methodology for the multi-layer (multi-base × S₃ symmetry × Pan TA × paired sub-products × balanced/unbalanced enumeration) bound-search pipeline. Includes how to re-run, how to materialise a bound into a verified scheme, and the prioritised list of extensions to find more.
- references/fmm-lille-discrepancies.md
— comparison of our
schemes/ranks against fmm-lille's best-rank table (5,426 formats): where we're sub-optimal, where we're better (mostly F₂-specific via AlphaTensor), where we're missing entries. - references/case_studies/makarov_1986_recovery.md
— concrete worked example of the why of this catalog: how a
cited, useful, never-superseded-for-33-years algorithm
(Makarov 1986
⟨3,3,3⟩=22commutative) became practically inaccessible through a chain of paywall + language + thesis archival + transcription-typo barriers, and what it took to put it back into circulation as a verifiable JSON file.
- SOLVING_STRATEGIES.md — strategy menu for rank-search work: systematic (symmetry-quotiented, pruned) enumeration, ALS, SAT, gradient, RL. Phased plan for the SAT pipeline.
- TRILINEAR_AGGREGATION.md — how fast
matmul algorithms for one format are derived from another: pure
Kronecker vs naïve block split vs padded Kronecker (Sedoglavic 2017 /
AlphaTensor); worked
⟨7,7,7⟩example; when padding can be worse; the "must-have" trivial-base schemes. - STRASSEN_AS_EQUATIONS.md —
⟨2,2,2⟩as a system of polynomial constraints. - RANK_3X3_SEARCH.md — search-space mechanics
for
⟨3,3,3⟩. - RANK_5_SEARCH.md —
⟨5,5,5⟩notes. - SYMMETRIES.md — the symmetry group of the matmul tensor + quotient strategies.
- REVIEW.md — review notes / TODOs.
- ROADMAP.md — prioritized open work items (catalog expansion, stabilizer integration, fmm-lille biblio import, Phase 1.6/2 SAT runs, ω-history backfill).
KnownAlgorithm/KnownAlgorithmCatalog— curated literature claims.SchemeIO— read/write Perminov-style (dronperminov GH repo) JSON for verified factor matrices. Auto-detects dense / sparse / reduced / complex formats; auto- selects sparse output formax(n,m,p) ≥ 9(~5× smaller).MatrixJsonFormatter— Jackson-3-backed JSON pretty-printer with matrix-friendly rules (arrays-of-primitives inline; compound vertical).Compose/Compositions— Kronecker composition of catalog schemes (Strassen³ → ⟨8,8,8⟩=343,AlphaTensor² ⊗ Strassen → ⟨32,32,32⟩=15,463, ...).Recombination— Java port of DeepMind AlphaTensor's allocation-search recombination, both rank-only (recombine) and constructive (construct).CoverageMatrixGenerator— auto-generates COVERAGE.md.
io.cormoran.strassen.v3— core types (BilinearAlgorithm,NonCubicBilinearAlgorithm,ComplexNonCubicBilinearAlgorithm,Verifier) and hand-built reference algorithms (Strassen7,Laderman23).io.cormoran.strassen.v3.sat— SAT/SMT encoding pipeline for matmul rank search (Z2CnfEncoder,SatMatmulPipeline, bridges to SAT4J / kissat / cryptominisat / BreakID).io.cormoran.strassen.v3.benchmark— performance harness for solver strategies (per-run artifact directories, CSV+MD roll-ups, per-strategy timeouts).
import_alphaevolve.py— pullsmathematical_results.ipynbfrom google-deepmind/alphaevolve_results, verifies upstream, writes Perminov-style JSON.import_alphatensor.py— convertsfactorizations_f2.npz/factorizations_r.npzfrom google-deepmind/alphatensor.ImportPerminovSchemes.java(docs.migrate) — bulk-download scheme factor matrices from github.com/dronperminov/FastMatrixMultiplication, filtered by max-dim. Replaces the formerimport_dronperminov.py. The methods/results behind that repo are published in Perminov's papers — see REFERENCES.md entries [75] (arXiv:2603.02398), [77] (arXiv:2511.20317), [78] (arXiv:2512.13365), [79] (arXiv:2512.21980).
~7,300 algorithm scheme files organized into section{N} by max(n,m,p),
e.g.:
section2/strassen-2x2x2_m7_a18.json— Strassen (hand-coded)section3/laderman_1976-3x3x3_m23_a98.json— Ladermansection4/alphatensor_F2-4x4x4_m47_a340.json— AlphaTensor F₂section4/alphaevolve-4x4x4_m48_a1264.json— AlphaEvolve complexsection8/derived_recursive-8x8x8_m336.json— derived
Filename convention (task #173): {source}-{n}x{m}x{p}_m{rank}[_a{additions}].json
— _ separates tokens within the source (fmm_lille, perminov_ZT,
rosowski_2019_thm2), - separates source from shape; _m{N} is the
rank (multiplications), _a{N} the addition count. Field markers live in
the JSON fields[], not the filename.
All parsing/serialisation lives in one class:
SchemeIO
(matrix-friendly pretty-printing in
MatrixJsonFormatter).
Common keys:
| Key | Meaning |
|---|---|
n |
[n, m, p] — the shape ⟨n,m,p⟩ (A is n×m, B is m×p, C is n×p). |
m |
the rank = number of bilinear products. |
fields |
the fields the scheme is verified valid over, a subset of [F2, F3, Z, Q, R, C] in containment order (task #174/#175). Integer ±1 ⇒ all six; ½-coefficient ⇒ [Q,R,C]; AlphaTensor ⇒ [F2]. |
fields_not |
fields explicitly excluded (provenance for narrowing). |
commutative |
true for commutative-only schemes (Waksman, Rosowski Thm 2/3, Makarov) — these do not lift to recursive matmul over a non-commutative ring. |
u / v / w |
dense factor matrices (used for small schemes, max(n,m,p) < 16). Perminov/dronperminov convention: u,v are rank-major (rank rows × dim cols); w uses column-major C-flatten (j·n + i). Read by SchemeIO.fromJson. |
u_sparse / v_sparse / w_sparse |
sparse factor matrices (used for large schemes, max(n,m,p) ≥ 16, where they save real space). Row-oriented map keyed by product index: {"0": {"i": [pos…], "c": [coef…]}, …}. Same m/n and same col-major-W positions as the dense form; read by SchemeIO.fromJsonSparse. |
additions |
flat addition count from (U,V,W) (also recomputed by Verifier.additionCount). |
scheduled_additions |
the cheaper count when common sub-expressions are shared (e.g. Strassen-Winograd ⟨2,2,2⟩ = 15 scheduled vs 24 flat). The canonical schedule representation is a straight-line-program array (schedule[], planned — see tasks #189/#190). |
multiplications / elements |
human-friendly Perminov-style rendering: multiplications = ["m1 = (a11 + a22)*(b11 + b22)", …], elements = ["c11 = m1 + m4 - m5 + m7", …]. Generated by HumanScheme (flat / unshared form). Emitted into docs/catalog.json for small schemes. |
lineage / lineage_str / lineage_compact |
how a composed scheme is built from atoms (Kronecker ⊗, recombination R[…], concat, axis-flip, permutation). lineage is the replayable tree; lineage_compact is the one-line display. |
source / attribution_for_rank / discovery / year |
provenance: who published the scheme vs who first established the rank bound (discovery = N new / R rediscovery, Smith 2002 convention). |
Schemes are end-to-end Java-verified (Verifier residual check; small shapes
fully residual-checked, larger load-checked and sampled).
# Run the full test suite (Verifier, SAT pipeline, catalog round-trips, ...).
mvn test
# Regenerate the auto-generated docs after adding/changing schemes.
mvn -q test-compile
CP=$(mvn dependency:build-classpath -q -Dmdep.outputFile=/dev/stdout 2>/dev/null)
java -cp target/classes:target/test-classes:$CP \
io.cormoran.strassen.v3.catalog.CoverageMatrixGenerator
# Canonicalize JSON formatting after editing schemes (matrix-friendly,
# primitives inline / compound vertical).
java -cp target/classes:target/test-classes:$CP \
io.cormoran.strassen.v3.catalog.ReformatSchemes
# Spotless for Java / Markdown hygiene.
mvn spotless:check
mvn spotless:apply
# Bulk-import scheme corpora (optional).
python3 tools/import_alphaevolve.py
python3 tools/import_alphatensor.py
mvn -q exec:java -Dexec.mainClass=eu.solven.matmul.docs.migrate.ImportPerminovSchemes -Dexec.args="--max-dim=16"- 2,353 verified scheme files spanning sections 2 → 16.
- 78/78 unit tests pass (verifier round-trips for real, F₂, and complex schemes; composition correctness; SAT pipeline; recombination).
⟨32,32,32⟩over F₂ at rank 15,463 — constructed end-to-end from AlphaTensor⟨4,4,4⟩=47+ Strassen⟨2,2,2⟩=7, sampled-verified.
For the longer-term direction (publishable / R&D-demonstration catalog
up to ⟨32,32,32⟩), see
SMALL_MATMUL_CATALOG.md §7.1 and
OMEGA_HISTORY.md.