The order the products are taken in

The sparsity field opens with a sentence: the elimination order decides the memory. A symmetric permutation changes no answer and changes the fill by a factor of eight, so the order is a decision rather than a detail.

This is that sentence about a different resource. A contraction of several tensors over shared indices is an expression with one value and many evaluation orders, and the orders differ by orders of magnitude in arithmetic — with no approximation anywhere and no answer changing at all.

What is counted #

Two tensors contracted over their shared indices cost one multiply-add per entry of the union of their open indices, and the result carries whatever indices are still needed elsewhere. So both quantities this page reports fall out of the label sets alone and neither needs a number to be multiplied:

• cost, the total multiply-adds over a whole evaluation;
• peak, the largest intermediate ever held.

An index is closed once every tensor carrying it is inside the group being contracted, and open otherwise. That single rule is the whole cost model, and it is why the exhaustive answer is computable: a dynamic program over the 2^t subsets of the network’s tensors, which is affordable to about twelve of them.

The three networks #

A matrix chain. Six matrices with the dimensions 30, 35, 15, 5, 10, 20, 25 — the example every algorithms course uses. Cheapest 15,125; dearest 512,793,750; a factor of 33,900.

The inner product of two trains. Ten cores, five per train, contracted to a scalar. Cheapest 3,344; dearest 6,580,895,744; a factor of 1,968,000. The dearest order contracts all five cores of one train first, which forms the whole tensor the train was representing — the exact object the format exists to avoid — and then does the same to the other.

One alternating-least-squares step. A four-index tensor against three factor matrices. Cheapest 105,120; dearest 113,040; a factor of 1.075.

The third is the counterweight, and it is the finding worth having beside the other two. On that network the search is not worth running, every order is within eight per cent, and nothing about the shape of the network says so in advance. A code that ran an exhaustive search on every contraction would spend more on the search than the search saves, on some networks and not others, and knowing which is itself the problem.

Why this belongs in this field #

The field’s premise is that a count of arithmetic stopped deciding which of two implementations is faster about thirty years ago, and every other essay in it measures something else — words moved, messages sent, a block size that is a property of the machine.

This one measures arithmetic, which looks like a step backwards and is not. The point is not that 15,125 multiply-adds take less time than 512,793,750; that is not in doubt and needs no measurement. The point is that both counts describe the same expression, so the arithmetic a computation performs is not a property of what it computes.

That is the same kind of statement as the rest of the field makes, one level up. Blocking says the same multiplications at a different price; this says a different number of multiplications for the same answer. Together they say that neither the count nor the price is fixed by the problem, and a cost model that quotes either as though it were is quoting a decision as a fact.

The order also interacts with everything else the field measures. The cheapest order in arithmetic may hold a larger intermediate, which changes what fits in a fast memory; and on a parallel machine the order decides what can be done at once. Those are not measured here and they are why a real library’s heuristic is not the one this page prices.

Two rules that sound like the same idea #

An exhaustive search is exponential in the number of tensors, so no library runs it. What they run is greedy: pair two operands, repeat.

There are two obvious ways to choose the pair and both are one line.

Pair the two that are cheapest to multiply. Minimise the immediate cost of the contraction.

Pair the two that leave the smallest result. Minimise the size of the intermediate produced.

Both are plausible, both are greedy, and the argument for either is a sentence. Priced against the exhaustive answer over sixty random networks of seven tensors:

The second is the rule the libraries ship, and the measurement is what says it is the better one. Nothing about the two descriptions would have separated them; the median excess differs by a factor of a hundred and forty in the deficit.

The spread being searched over is on the same figure: the median network’s best and worst orders differ by a factor of 607, and the worst by 10,590. So a heuristic with a median excess of 1.003 is capturing essentially all of a very large saving.

A median is not a worst case #

The two columns of that table are different kinds of number and the difference is this field’s own.

The median is knowable from twenty networks. It settles almost immediately, it is what a benchmark reports, and it is what makes a heuristic shippable.

The worst case is not knowable from any finite sample. The cheapest-product rule’s worst of sixty is 25.4, and there is no reason to think a hundred and twenty would not find worse — the figure at 120 networks shows exactly that.

A heuristic that is optimal on 1.7 per cent of networks and within a factor of one and a half on half of them is a good heuristic. A coverage number that reported only the first would say the opposite, and one that reported only the median would hide the tail. Both are quoted here for that reason, which is the same discipline the refutations index applies to this site’s own claims.

The other resource #

The cheapest order is not always the leanest one, and the two objectives are two dynamic programs over the same subsets.

Over 120 random networks they disagree on three. Where they disagree the difference is worth having: the cheapest-cost order on the worst of them peaks at 1,188 numbers and the leanest peaks at 396 — a factor of three in memory — for nine per cent more arithmetic.

So the best order is not a well-formed phrase until the resource has been named. That is the same finding the sparsity field’s threshold-pivoting essay reaches about fill against growth, and the same one this field’s blocking essay reaches about operations against words moved: two resources, one decision, and no exchange rate between them that is not a property of the machine.

Three networks in 120 is also worth reporting as a small number. On most networks the two objectives agree, so a code that optimises arithmetic gets the memory for free — which is a convenient fact and not a theorem, and would not have been visible without running both.

Where the orders come from #

It is worth saying what makes the train’s inner product span two million, because the number sounds like an artefact and is not.

Two trains of five cores each, with ranks four and mode sizes eight. Contracting them left to right sweeps a small matrix along the chain: at every step the intermediate carries one rank index from each train, so it is 4 × 4 = 16 numbers, and the whole thing is 3,344 multiply-adds.

Contracting one train’s cores together first builds the tensor it represents: 8⁵ = 32,768 entries, and then the same for the other, and then an inner product of two dense arrays. That is the entire content of the format thrown away by an ordering decision, and the resulting count is 6.6·10⁹.

So the format’s advantage is not a property of the representation alone. It is a property of the representation and the order operations are performed in, and a code that stores trains and contracts them carelessly has a data structure and no algorithm.

Why an exhaustive search is affordable at all #

The dynamic program is over subsets, so it is 2^t states and 3^t transitions — 2,187 for seven tensors and about 60,000 for ten. That is nothing, and it is nothing because t is the number of tensors rather than the number of indices.

The contrast with the sparsity field’s version is worth drawing. Choosing an elimination order optimally is NP-hard in the size of the matrix, which is why that field measures heuristics — minimum degree, nested dissection — against each other rather than against an optimum. Here the optimum is computable for the network sizes that occur, so the heuristics can be priced against the answer rather than against one another.

That is a rare position on this site and it is why this page can say 1.003 rather than the two rules are comparable.

What a code should actually do #

The measurements support a short rule and it is worth stating, because “search the orders” is not implementable and “use the greedy rule” throws away the tail.

Use the smallest-result rule by default. Median excess 1.003 over sixty networks, optimal on half of them, worst case 2.76. It costs t² comparisons per contraction and is essentially free.

Search exhaustively when t is small and the contraction is repeated. A dynamic program over ten tensors is 60,000 transitions, which is nothing compared with one evaluation of the network it is ordering — and inside an iterative method the same network is contracted thousands of times, so the search is amortised to nothing.

Report the spread. The one number that says whether either of the above mattered is the ratio of the worst order to the best, and it is a by-product of the exhaustive search. On the alternating step it is 1.075 and the whole exercise was unnecessary; on the train’s inner product it is two million.

That last is the same recommendation this collection makes about every heuristic it prices: the useful output is not the answer but the answer together with the size of what was being chosen between.

The refusal #

The claim under test is the one every expression invites: that a formula with one value has one cost.

The assertion that the cheapest and dearest orders of the matrix chain are within one per cent of each other is fed the pair. It fails by a factor of 33,900.

The refusal is the whole page in one line, and it is worth having in the file rather than in the prose because the claim is not usually stated — it is assumed, by every piece of code that writes a contraction in whatever order the indices came out in.

The file’s other refusals cover the two directions this page could be over-read in. One is fed the sixty random networks and required to refuse the claim that the greedy rule is nearly always optimal, which is the flattering reading and is false at 1.7 per cent. The other is fed the train’s inner product and required to refuse the claim that its cheapest cost is zero — a network whose labels all appear twice has arithmetic to do, and a search that reported none would mean the model had not run.

The generalisation nobody can take #

One boundary is worth naming, because it is the reason contraction ordering is a research subject rather than a solved one.

The dynamic program above is exponential in the number of tensors, and it is affordable because the networks that occur in this field have five or ten of them. The networks that occur in quantum many-body simulation and in the analysis of contraction as a model of computation have hundreds, and finding the optimal order for those is NP-hard — by a reduction from treewidth, which is the same quantity the sparsity field’s elimination-order problem turns on.

So the two orderings this page compares are the same hard problem seen twice. A contraction network’s optimal order is a tree decomposition of its index graph, an elimination order for a sparse matrix is a tree decomposition of the matrix’s graph, and the heuristics on both sides are the same family: greedy by degree, nested dissection, simulated annealing.

That is worth the paragraph because it means the sparsity field’s measurements transfer. Its finding that nested dissection loses to minimum degree at every size drawn — 1,413 against 1,026 on a 12 × 12 grid, despite the better asymptotics — is a finding about tree decompositions of small graphs, and the networks here are small graphs.

At other settings #