Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Contraction — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · cost
  2. 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.

    part 2 · cost
  3. 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.

    part 3 · cost
  4. 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.

    part 4 · cost
  5. 11.21.41.6partial orders kept at each pairingcost over the exhaustive order's cost123468cost so far+ largest group+ closing pairings7 tensors, 60 networkscost so far: networks worse wider24+ largest group: networks worse wider12+ closing pairings: networks worse wider23solid: median · dashed: ninetieth percentilethe width axis is the same knob in every curve

    A beam ranked on what remains

    A beam over contraction orders ranked on cost so far returns a dearer order when it is widened on 24 of 60 networks. Rank it on cost so far plus the largest group still to be paired — a lower bound on what remains, and free — and that falls to 12, eleven of them from the original 24. Rank it on a stronger estimate that is not a bound and the count stays at 23, but only 10 are the same networks: the anomaly has moved, not gone. At nine tensors, where the unranked beam's median at width 8 was worse than at width 1, both rankings make widening pay again.

    part 5 · cost
  6. 00.10.20.30.40.50.6pairings priced, on a logarithmic axisshare of networks whose optimum was missed10²316wide earlywide lateconstant 1constant 16constant widthswide earlywide late7 tensors, 60 networks: optimum foundconstant 1 [1 1 1 1 1 1]30constant 4 [4 4 4 4 4 4]30constant 16 [16 16 16 16 16 16]53wide early [16 8 4 2 1 1]27wide late [1 1 2 4 8 16]37lower and further left is bettera schedule is a width for each level

    Widen the beam where the ranking is right

    A beam that is wide at its first pairings and narrow at its last looks like the right shape, since the early commitments are the damaging ones. Measured, it is worse than no beam: at nine tensors a width of 16, 8, 4, 2 and then 1 prices 742 pairings and has a median of 1.263 against width 1's 1.062 for 120. The reverse shape — width 1 early, doubling to 16 at the end — prices 78 pairings on seven tensors and finds the exhaustive order on 37 of 60 networks, against 30 for a constant width of 4 at 161. A beam should be wide where cost so far is nearly the whole cost.

    part 6 · cost
  7. 7 tensors, 60 networksτ = 2, networks exact46constant 8, networks exact4210²0102030405060pairings pricednetworks exacttie-widened, τ 0 to 8constant width 1 to 8wide late, two ratesup and to the left is betterwidth spent where the ranking is uncertain

    A near-tie is a factor of four

    A beam over contraction orders spends its width by level — wide late was the best schedule, finding the exhaustive order on 37 of 60 seven-tensor networks for 78 pairings priced. The alternative was to widen only where the ranking is a near-tie. Measured, near-ties buy nothing: keeping every candidate within a quarter of the best changes nothing at all, because the pairing the exhaustive order wants is almost never tied with the ranking's first choice. It sits a factor of two to four further down. Widen to keep everything within a factor of three and the beam finds the exhaustive order on 46 networks for 150 pairings, and at nine tensors has a median of 1.007 where every schedule tried before had 1.056 or worse below 1,380 pairings.

    part 7 · cost

All series