How few multiplications does a product need?
The rank of a bilinear map is the number of multiplications required to compute it. Strassen doing 2×2 matrix multiplication in seven instead of eight is where fast matrix multiplication comes from, and finding such decompositions in general is open. This began as a heuristic that proposed decompositions; it now proves them, on the maps small enough to settle.
Where it started
Eight weeks at LJK, in Julia. The method is a greedy descent: it takes a bilinear map over a finite field and repeatedly rewrites it in a different basis, looking for a spanning set with fewer rank-1 components than the one it started from. The rewrite is allowed to use more components than it started with, since it only has to generate the original map: that is what Karatsuba’s five products for a four-coefficient product is.
It was redone in C++ on Givaro, the exact-arithmetic library from the same laboratory. Nothing is ever a float, so a reported rank is a fact about the map and not an artefact of rounding, and every decomposition is rebuilt and multiplied back out against the map before it is printed.
The descent’s expensive step is priced badly, and that is the finding the internship left behind. Step 3 scans the full pool of rank-one maps. Across the four polynomial fixtures it improved the answer in two of four cases, by one product each, and cost between 58 and 184 times what the first two steps cost together. Any continuation that only makes step 3 faster optimises the part that mostly does not pay. Source: fixtures/README.md.
fixtures/README.md and descent_search/results.json, produced by minimise-rank.What it is now
That descent is one strand of ten. tensor-rank-toolkit attacks the same question from ten directions with thirteen command-line tools, each answering one question no other answers: the cheap descent, an exhaustive search that returns a proof, lower bounds with no search at all, a SAT encoding whose refutations are written as DRAT and rechecked by drat-trim, a quotient by the symmetry group, isomorph-free enumeration, and a canonical form for two-slice tensors that answers a 4×4 pencil in about 50 microseconds in polynomial time. The thirteenth reads somebody else’s published ⟨L, R, P⟩ back into a tensor, because nobody distributes tensors — PLinOpt ships 153 SMS operator triples and no tensor at all. Sources: README.md, OPTIONS/one-question-per-command.md, OPTIONS/reading-the-answer-off.md.
The internship’s second strand is a strand here too. Sparsifying the operators is the cost the multiplication count misses: fewer nonzero entries means fewer additions. Strassen’s two encoding operators go from 12 nonzeros to 10 and an alternative-basis operator from 21 to 10, in milliseconds, which takes Strassen’s 18 additions to 12. The source article reported no measured result for this operator, only that its program took too long for a simple problem. Source: matrix_sparsification/README.md.
Decided, not proposed
A heuristic proposes and never proves: a decomposition is a witness, and only a refutation settles a rank. The exhaustive search refutes. Four maps are now settled outright, in exact arithmetic, each answer rebuilt and multiplied back out against the map it claims to compute.
| Map | Both halves, from the tensor | Naive | Rank |
|---|---|---|---|
| 2×2 matrix multiplication | 6 refuted in 25 399 nodes, 7 found in 7 436 | 8 | 7 |
| GF(16) over GF(2) | 8 refuted in 105 600 301 nodes, 9 reached | 16 | 9 |
| F2 5×5 polynomial | 12 refuted in 146 402 553 nodes, 13 exhibited in 80 | 25 | 13 |
| F3 3×6 polynomial | 9 refuted in 4 729 nodes, 10 reached | 18 | 10 |
Strassen’s seven products and Winograd’s proof that six are impossible, neither assumed and both recomputed from the tensor, in 0.55 s in all. GF(16) is the expensive one, 38.8 minutes for the refutation alone; F3 3×6’s refutation of nine takes 7.65 s. The 13 and the 10 are the values Barbulescu, Detrey, Estibals and Zimmermann published in 2012, so nothing here beats them; what changed is that both halves are now proved inside the repository instead of half of each being cited. Sources: famous_tensors/decided-exactly.md, what-it-computes.md, incumbent_search/what-it-reaches.md, state-of-the-art/what-is-missing.md.
One case shows what the extra levels are for. Length-7 cyclic convolution over F2 sits at 15 after the descent, and its step-3 shortlist is 0 of 16 129: not one rank-one map strictly improves it, so a first-improvement greedy has nowhere to step. Cutting the same tree at the incumbent instead of at a target reaches 13 in 22 nodes, which is the published rank. Source: incumbent_search/what-it-reaches.md.
Against the published state of the art
“State of the art” is only earned against somebody else’s code on the same question, so the baseline is yang2025’s own public implementation, cloned outside the tree and run on this machine. Same question, one core, 2×2 matrix multiplication over GF(2): refuting six products costs their Java 0.954 s and their Python 30.45 s, against 0.0362 s here, and 0.0013 s with the orbit quotient. The whole sweep is 1.385 s against 0.0554 s. Source: state-of-the-art/comparing-against-the-baseline.md.
That wall clock is an implementation result and must not be read as an algorithmic one. It is C++ against Java, and a bit-packed leaf against a general one. The two searches visit 25 426 nodes and 25 399, and two independently written programs agreeing that closely on a tree size is evidence they are the same algorithm, which is what both papers say. The algorithmic difference is the orbit quotient: 648 nodes, 39.2 times fewer, and that one survives any language.
state-of-the-art/comparing-against-the-baseline.md.A second strand hands the same question to a SAT solver, and on the one instance both were run to the end it wins by an order of magnitude: ruling out eight products for GF(16) multiplication costs the tree 2 328 s and kissat 108.0 s, 21 times less. The advantage grows with the instance, which is the interesting part: level on 2×2 matrix multiplication, twenty-one times on GF(16). Source: satisfiability/measurements.md.
Where it is behind
Two published values are matched and two are not. gf32_multiplication reaches 14 against a published mu_2(5) = 13, and gf64_multiplication reaches 20 against mu_2(6) = 15. On 3×3×3 matrix multiplication the plateau walk reaches 24 where Laderman published 23 in 1976, and the exhaustive search does not reach that shape at all: its refutation is projected at about ten hours and has not been run. Sources: fixtures/published-targets.md, famous_tensors/README.md.
The one genuinely open map here is F2 4×7, bracketed at 15 ≤ rank ≤ 16: the lower bound is the literature’s, the upper one is this repository’s, and neither side has closed it. Source: state-of-the-art/where-we-stand.md.
What is open, and what would come next
yang2025 prunes by rank sums and by rref; covanov2019’s quotient removes whole orbits. They are different mechanisms, and nothing shows they cannot be combined. No paper found publishes that combination, and neither does this repository: it is an open direction rather than a result, and it is the one this work would take next. Source: state-of-the-art/comparing-against-the-baseline.md.
What is proved, and what is not
Each proof above is an exhaustion over one map at one size; the bilinear rank problem itself is still open, and every upper bound on this page proves nothing on its own. Every timing is one core of an i5-12450H, fastest of three runs on a quiet machine, and is evidence of an order of magnitude rather than of a digit: no test asserts a timing and CI does not check one. The counts are the opposite kind of number. They are exact, asserted by the test suite, and rerun on every push. Protocol: MEASURING.md.