How few multiplications does a product need?

tensor-rank-toolkit, a library for exact tensor and bilinear rank
C++20 on Givaro, MIT licensed

What it computes

Two strands, because a fast algorithm pays for both. Multiplications are the rank of the map. Additions are how many nonzero entries its operators carry. Each is settled exactly here on one map, and settled means proved rather than found: the rank below is closed from both sides, by a refutation and an exhibit, and the nonzero count further down is the least any change of basis can leave. Everything else on this page is a route to one of those two questions: a descent, an exhaustion, a solver, a quotient by symmetry, a canonical form. Nothing here is ever a float, so a reported rank is a fact about the map rather than an artefact of rounding.

Every count on this page is asserted by the test suite and reproduces anywhere. The timings are not: none of them is asserted, no test fails on one, and they are quoted as evidence of an order of magnitude rather than of a digit. The protocol they were taken under is MEASURING.md.

The cheap direction is rank by descent. Three steps: an exact matroid greedy for the starting basis, then two relaxations that trade the guarantee for reach.

What the timings are, and are not

Every figure in the Time column was measured by hand on one core of an i5-12450H at 2.2 GHz, on an otherwise quiet machine, under the protocol in MEASURING.md. Two timings close enough together to be the fan rather than the code are never reported here as a ratio, and no timing is checked by CI, because a shared runner would turn a real regression and a noisy afternoon into the same red tick.

The finding worth stating on its own

The expensive step buys almost nothing. Step 3 of the descent enumerates the full pool of rank-one maps, and across the four polynomial fixtures it improved the answer in two of four cases, by one product each time, while accounting for essentially all of the cost: on F2 4×7 almost the whole of the 0.397 seconds went to returning the rank the previous step already had.

So the step that costs essentially everything buys essentially nothing. Any continuation that only makes step 3 faster is optimising the part that mostly does not pay, and the fixtures exist to hold that finding still.

And now a bound from below

The descent is a heuristic: it says a map needs no more than so many multiplications. The complete search asks the other question, not “can this be improved” but “is there one with exactly k products”, and a no from it, run to exhaustion, is a fact about the map rather than about the searcher.

The last line is closed, and it took both directions to close it. Nine, ten and eleven products are refused by rank_lower_bound before the search opens a node, and twelve is ruled out by exhaustion in 146 402 553 nodes, so no fewer than thirteen will do; tighten-rank-bound then exhibits a thirteen in 80 nodes, so the rank is exactly 13, settled on 2026-08-21 by this repository’s own two searches. Neither half is the answer on its own: the refutation is the floor and the exhibit is the ceiling, and the descent reaches only fourteen. Barbulescu, Detrey, Estibals and Zimmermann report the same 13, [bdez2012], and the line above no longer rests on their reporting it.

What made that refutation affordable

Ruling out twelve was recorded here as never run and priced at about seven hours, and the price was an extrapolation from a leaf that rebuilt every candidate as a general finite-field matrix: 256 field multiplications and a heap allocation for an object that is 256 bits. Forming it in words instead cost 129.1 ns against 940.2, and the seven hours became 535.59 seconds. The estimate was not wrong about the tree, which is still 146 402 553 nodes; it was wrong about the leaf, and a bound nobody re-derives is a bound that keeps its first mistake.

That leaf is also the one part of this shaped for a graphics card, which is worth saying precisely because the rest is not. The tree diverges per branch and GPU CDCL is a published negative result, so neither the search nor the solver route is a candidate. The leaf is 4.29 billion independent iterations of an outer product, a bit-pack and an exclusive-or against a basis that fits in constant memory, with nothing to transfer, since a thread derives its own candidate from its index. One whole ⟨4,4,4⟩ leaf on an RTX 4060 Laptop is 1.019 s, timed end to end and reproduced to three digits, with the survivor sets compared map for map on thirteen questions. What that is worth against one core is suspended rather than settled: the host leaf has been rewritten twice since the comparison was taken, from 129.1 ns an element to 3.3 ns, and the rule here is that a card is priced against the path it would replace as that path ships today.

It is a proof of concept, and where it is wired is exact rather than vague. The kernels are compiled only where CMake finds the CUDA toolkit; where it does, five commands link one registration object, and --device auto then sends any leaf past the measured 8 192-element floor to the card. Where it does not, nothing links it, the seam is null, a machine without nvcc compiles and passes the same 97 tests, and decide-rank prints device: cpu (no gpu backend compiled in) rather than pretending the choice does not exist. The shipped build is the second kind. The point of the measurement was to find out whether a card changes what is decidable, not to ship a dependency: at 4.2 billion elements a second the answer is that one leaf stops being the obstacle and the number of leaves starts being it.

Cheaper routes to the same question

Two rank-sum bounds return a floor from the tensor alone in milliseconds, and they are tight often enough to remove the dearest question in a sweep entirely: they raise GF(16) from 4 to 8 and cyclic convolution from 5 to 9, each of which previously cost a minute of exhaustion.

Håstad proved deciding tensor rank NP-complete over every finite field, and that cuts both ways. One tool turns 3SAT into a tensor, and three encoders turn the rank question into one a solver answers. A refutation can be written as DRAT and checked by drat-trim, so a lower bound from a solver is verifiable rather than trusted.

Symmetry removes work before any of them runs. A change of coordinates fixing the target subspace maps solutions to solutions, so one member of each orbit suffices: 39.2× fewer nodes on a refutation, about 30× on the clock, and the ⟨3,3,3⟩ candidate pool collapses from 261 121 to 13 orbits. Canonical augmentation goes further, deduplicating with no memory at all, and returns ⟨2,2,2⟩'s 36 solution subspaces as the 1 orbit they are while visiting 22 778× fewer nodes and running 11.8× faster. It did neither until the canonical code stopped being found by walking all 216 group elements and started coming from a base and strong generating set, which is the difference between naming an orbit and searching for it.

The same method put to deciding rather than counting is the sharpest measured trade here. Wired into the factorisation search it visits 72 nodes against the plain tree's 3815 and loses anyway: 0.0381 s against 0.00748 s over the same sweep, 53× fewer nodes for 5.1× the wall clock. There is no entry fee in that account and there never was one: the presentation this page used to charge it for was a line fitted through two points at different targets, where a node costs far more at one than at the other, and building that presentation is 98 µs. It ships behind a flag with a test that keeps it honest, never as a default, because a wired route known to lose is worth more than an unwired one somebody will propose again.

That deficit widened before it narrowed, and the widening is the durable lesson. It stood at 25.8× on the day the route itself got 10.5× faster, because the packed GF(2) leaf had made a plain node 18× cheaper meanwhile; two further rewrites of the route have since brought it to 5.1×. So the lesson is not the one first written down: an optimisation to the common path raises the bar for every quotient competing with it. A quotient is only ever worth what the work it skips is worth.

Where no search is needed, and a theorem that stops holding

A tensor with two slices is a matrix pencil, and Kronecker's theory settles it by exact linear algebra in polynomial time, with no candidate pool at all, in about fifty microseconds on a 4×4. What it will not settle is the rank, and that is the finding. Ja'Ja's 1979 formula reads the rank off that canonical form, and it is a theorem over an algebraically closed field: on (I4, C) over GF(2) with C the companion of x4+x+1 it gives 5, and the exhaustive search proves no five-product algorithm exists, walking 1 897 576 nodes to the end of the tree, then exhibits one with six.

The construction that attains the classical bound interpolates through more points than the projective line over GF(2) contains, which is Winograd's condition. So the module reports the closure value as a proved lower bound, a sharper count beside it marked provisional, and exact only where the pencil is diagonalisable over the field. Twelve pencils settled by exhaustion are tabulated, three of which the classical formula gets wrong. The per-block cost that would close it is stated as a conjecture, and the wrong fixture is kept with its node count in its header, because the artefact that caught an error is worth more than a clean repository.

The other half of the cost

A fast algorithm costs multiplications and additions both, and the additions are set by how many nonzero entries its operators carry. Fewer nonzeros means fewer additions, the cost the multiplication count does not capture.

Strassen's two encoding operators go from 12 nonzeros to 10, and an alternative-basis operator from 21 to 10, in milliseconds. Ten is not merely the best found: it is the least any change of basis can leave, because choosing the sparsest basis of a subspace is a matroid problem and the greedy returns a minimum-weight basis of any matroid.

On the operators of a published rank-23 ⟨3,3,3⟩ scheme, that is 221 nonzeros to 128, and the 128 is the proved minimum there too, over every invertible change of basis. Where the trade used to be speed it no longer is: the run costs about a third of a second, against roughly five hundred before the methods that could not say their answer was minimal were retired to a branch.

Searching column supports stops finishing somewhere, and on a ⟨4,4,4⟩ operator it stops well before the answer: fourteen million subsets at weight six, four hundred and fifty-one million at weight eight. That one is answered by not searching: one linear programme per coordinate, in exact rationals, reaching a verified basis at 100 nonzeros in a third of a second. It is an upper bound rather than a proof, and it reaches the proved minimum anyway on every operator where a proof exists, four to fifteen times faster than the search that proves it. Why it should is an open question: the theorem that suggested it turns out not to apply to any operator measured.

And fewer nonzeros is not the same as fewer additions. Hand this exact stage's output to a common-subexpression pass and a raw scheme improves by 23%, two already-polished ones by 2% and 7%, and one operator gets worse. That is measured rather than expected, and it is the reason the two counts are reported separately.

One pipeline, not two halves

A decomposition is not the deliverable; the algorithm is, and an algorithm is three operators: L and R encoding the two operands, P combining the products. The rank search recovers them from the decomposition it finds and writes them out; the sparsification is what they are for.

minimise-rank evidence/fixtures/f2_5x5.tensor --emit-operators out   # 25 -> 14 multiplications
sparsify-operator out_L.sms                                 # 31 -> 27 nonzeros

Fewer multiplications, then fewer additions, from one map, in two commands. The same two run in that order from a browser, as the console's decompose-then-sparsify flow: one press, four runs, each an ordinary run with its own command, its own card and its own exit code. It is local, on the loopback address, and needs Python 3's standard library and nothing else.

Read it