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

Four directions on the one question: fewer multiplications, fewer additions, the rank asked as a question a SAT solver can answer, and, where no search can reach, a bound read off an algebraic curve. 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 8.96 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 narrowed from both sides and not closed. 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 the rank is thirteen or more. The descent exhibits fourteen, so what is proved here is 13 ≤ rank ≤ 14. Finding a thirteen is what would close it and has not been run. Barbulescu, Detrey, Estibals and Zimmermann report 13, [bdez2012], so the descent’s 14 is not the last word.

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 costs 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, against 67 minutes for the same leaf on one core, with the survivor sets compared map for map on thirteen questions.

It is a proof of concept and it is wired to nothing. The kernels build only where nvcc is present, a machine without one compiles and passes the same 59 tests, and decide-rank prints device: cpu (no gpu backend compiled in) rather than pretending the choice does not exist. 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: 27.8× on a refutation, 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 779× 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 takes 0.263 s against 0.0102 s: 53× fewer nodes for 25.8× the wall clock. Two floors give the cost model behind that pair, 0.196 s to build the presentation and then 0.795 ms a node against a plain node's 2.66 µs, so break-even needs 299× fewer nodes and the quotient supplies 53×. 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.

Its deficit grew from 15× to 25.8× while the route itself got 10.5× faster, because the packed GF(2) leaf made a plain node cheaper faster still. That is the durable lesson, and it 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.

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 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.

Read it