Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Contraction order — where it appears

The sequence in which the tensors of a network are paired off and contracted, which changes no answer and changes the arithmetic by orders of magnitude. It is chosen from the index labels alone, before any number is multiplied, and the cheapest order and the one holding the smallest intermediate are usually not the same order.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

Also named here as tensor network — the same set of essays touches all of them, so they are one junction rather than several.

chain · cheapest1.51·10⁴chain · greedy5.06·10⁴chain · dearest5.13·10⁸train-inner · cheapest3344train-inner · greedy1.51·10⁴train-inner · dearest6.58·10⁹als-step · cheapest1.05·10⁵als-step · greedy1.13·10⁵als-step · dearest1.13·10⁵multiply-adds, on a logarithmic scaleone value, many priceschain, best ⁄ worst3.4·10⁴train, best ⁄ worst2·10⁶als step, best ⁄ worst1.1worst greedy excess4.5no answer changesand the price does

The order the products are taken in

The sparsity field's first essay says the elimination order decides the memory. This is the same sentence about arithmetic: a contraction of several tensors over shared indices has one value and many evaluation orders, and on the inner product of two trains they differ by a factor of two million.

cost · Contraction 10⁴1ceiling on the largest intermediate, numbers heldarithmetic ÷ the unconstrained cheapest orderno evaluation order fits below thisminimising the peak insteadthe unconstrained cheapest ordera ceiling, not a targetfree order, peak9504leanest possible2106cheapest that fits1leanest order costs1.6the difference1.6largest input2106the same memoryat two prices

A ceiling is not a target

Asked to hold the smallest possible intermediate, an evaluation order costs a median of 1.55 times the cheapest order's arithmetic. Asked to hold no more than that same amount, it costs 1.15. The two answers hold exactly the same number of numbers, and on one network they are 5.17 times apart in work.

cost · Contraction 10¹10²110¹rank of the trains at the moment of evaluationcost ÷ the cost of this rank's own best ordereach rank's own best orderthe order compiled at rank 4, carriedthe smallest-result rule, recomputedthe cheapest-product rule, recomputedone plan, eight rankscompiled at rank4worst carried8carried at rank 2568fresh rule at 2562.9carried at rank 21fresh rule at 21.1the search was exhaustiveand the dimensions moved

The plan that was right at rank four

An evaluation order is chosen once and paid for thousands of times, and the dimensions it was chosen at are not the dimensions it runs at. Compiled at rank four and run at rank 256 it costs 8.01 times the order that rank deserves; compiled at 256 and run at 2 it costs 301 times. A one-line rule recomputed on arrival costs 2.92 and 1.11.

cost · Contraction 12345678110¹partial orders kept at each pairingexcess over the exhaustive orderthe exhaustive orderdashes above: each rule's worst casepair by cheapest productpair by smallest resultone knob, two rulesby cost, width 11.5by cost, width 21.1by size, width 11both, width 81by size, worse wider24by cost, worse wider3the width repairs the bad ruleand does not improve the good one

The search that got worse as it widened

Keeping two candidate orders instead of one removes a third of the cheapest-product rule's excess, and by eight it has removed all of it — the two greedy rules this field separated become the same rule. On twenty-four of sixty networks a wider search returns a dearer order than a narrower one, and it is the better rule that it more often makes worse.

cost · Contraction

Named alongside it

The objects these essays reach for when they reach for this one.

Flop countTensor networkArithmetic costHeuristicSymbolic phaseElimination orderMemory hierarchyTensor trainAlternating least-squaresBlock methodsFill-reducing orderingKhatri–Rao product

All concepts