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.

What the shape does say in advance #

“Nothing about the shape of the network says so in advance” is the essay’s own claim about when the search is worth running, and it is nearly right. The part that is wrong is the part a code could use.

Sixty random seven-tensor networks, dearest order over cheapest, bucketed by how many distinct index labels the network carries:

at six labels the spread runs from 54 to 190, median 100. At seven, from 90 to 11,000, median 450. At eight, from 170 to 5,900, median 1,100.

The minimum rises monotonically — 54, 90, 175 — and the maximum does not even rise. The log-log correlation between the label count and the spread is 0.617, which explains under forty per cent of the variance and is the wrong number to quote, because at a fixed label count the spread still ranges over more than an order of magnitude.

So the shape predicts a bound, not a value: a seven-tensor network over eight labels is worth at least 175× to order well, and how much more is unpredictable. That is the useful direction. A code deciding whether to run a search does not need to know the payoff — it needs a guaranteed minimum, and the label count is one, computable from the expression before a single dimension is looked at.

And the counterweight is structural #

The third network is the one the essay leans on, and it deserves a stronger statement than it gets.

The minimum spread over all sixty random networks is 53.6. The alternating-least-squares step’s is 1.075. Not one random network of the same size comes within a factor of fifty of it.

So a network on which ordering does not matter is not an unlucky draw from the space of networks — it is a different kind of object, and the space of seven-tensor networks contains essentially none of them. That strengthens the counterweight rather than weakening it: the essay’s warning is not that a code might occasionally waste a search, it is that the two regimes are disjoint, and the boundary between them is not on any axis the sixty random networks vary along.

Which says where a real predictor would have to look. The random ensemble varies the labels, the dimensions and which tensor carries what; none of that separates the ALS step from the rest. What does separate it is topology — the ALS network is a star, one four-index tensor with three matrices hanging off it, so there are few groupings to choose between and they all pay about the same. A matrix chain is a path, and a train inner product is a ladder, and both admit orders that differ by building or not building an enormous intermediate.

That is the shape of the answer a library needs and it is not the shape of a size heuristic. The question is not how big is this network but how many essentially different ways are there to cut it, which is a question about the contraction graph and has nothing to do with the dimensions at all — the same distinction the sparsity field draws between a symbolic phase that reads the pattern and a numeric one that reads the values.

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.

That is the essay’s result and it is a statistic over a sample, so the sample size is a knob worth turning before the number is quoted.

A smaller sample is a milder verdict on the cost rule and a much milder one on the worst case, which is the first sign that two of these columns are about the search rather than about the rules:

Two of those three columns have barely moved and one of them has more than tripled.

The size rule is optimal to within 1.4% at every sample size and exactly optimal at the largest. 1.0034, 1.0140, 1.0026, 1.0026, 1.0000 — the cheaper heuristic, the one that never looks at a flop count, sits within a per cent and a half of the best order on the median network throughout.

The cost rule’s median excess rises with the sample: 1.296, 1.337, 1.446, 1.443, 1.471. Twenty networks put it 30% over optimal and a hundred and twenty put it 47% over. So “the cost rule is about a third worse” is a number about a sample of twenty, and the honest form of the claim needs the sample size attached to it.

And the worst column is not a measurement of the worst case. 7.53 at twenty networks, then 25.4 at forty, ninety and a hundred and twenty — found once and never beaten. A worst case that stops moving as the search widens has not been bounded; it has been found and then not improved on, which is a statement about the search rather than about the heuristic. The right reading of 25.4 is at least 25.4.

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.