Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Heuristic — where it appears

A rule that chooses quickly without proving its choice is best, used where the exhaustive answer is unaffordable. On the small networks here the exhaustive answer exists, so a heuristic can be priced against it rather than against another heuristic.

Named by 10 essays across 3 fields — each of them below, with the objects they name alongside it.

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

cost · Contraction 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.

cost · Contraction 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.

cost · Contraction 1.01.21.41.61.82.0median member's cost over the least any row order reachesindependent entriesa shared zero patternshared row scalesone matrix, two entries redrawnnatural order1.60the median order1.72another member's best1.54best over the other eleven1.46rows by their norms1.49smallest pivot entry1.24natural order1.65the median order1.72another member's best1.59best over the other eleven1.36rows by their norms1.35smallest pivot entry1.08natural order1.88the median order1.86another member's best1.13best over the other eleven1.16rows by their norms1.05smallest pivot entry1.01natural order1.28the median order1.51another member's best1.16best over the other eleven1.07rows by their norms1.42smallest pivot entry1.14dashed: the least cost of all 40,320 ordersthe rule wins wherever the rows show why

An order found once knows what the rows know

Searching for a fraction-free elimination's least-cost row order costs forty to two hundred and sixty times the elimination, so it can only pay if one order serves a whole family. The prediction was that it cannot: the best order depends on which rows happen to have short entries, so a reused order should do no better than the natural one. On independent entries and on a shared zero pattern that holds — another member's best order is an ordinary order, at the middle of the 40,320. On a family that shares its row scales it fails completely: another member's order costs a median 1.13 of the least where the natural order costs 1.88. But on every family, including that one, the rule that just takes the smallest pivot entry is cheaper than any reused or trained order — 1.24, 1.08 and 1.01. What an order carries from one matrix to the next is what the family shares — and only when that is a particular matrix, not a visible structure, does an order trained on the family beat the rule.

exact · Fraction-free 00.511.52ranks added by one triplingκ from 13⅓ to 400.28κ from 40 to 1200.95κ from 120 to 3601.39κ from 360 to 10800.38dot: mean over tolerances · bar: rangeno fixed step

An offset that bends twice

A hierarchical matrix's cheapest leaf can be named by one build at a leaf of 8, and a rank guessed from the tolerance alone names it on smooth kernels and misses on oscillatory ones. The repair proposed was a term in the frequency: the oscillatory kernels sat two thirds of a rank and one and a half ranks above 1/r at frequencies 40 and 120, and the prediction was a fixed step each time the frequency triples. On five frequencies from 13⅓ to 1,080 the step is a third of a rank, then one, then one and a half, then a third again — a curve that bends twice. The last bend is the smallest blocks filling up: at the tightest tolerance every 8-wide block is at full rank from 360 on. No fixed term reproduces it, and the one build that reads it directly still names the cheapest leaf on thirteen cells of fifteen, never storing two per cent too much, where the uncorrected guess misses seven by up to nine.

hierarchy · Storage growth of 5 cellscheapest 32, 16-wide ≥ 85cheapest 32, 8-wide ≥ 82234567891011121323456789mean rank of the 16-wide blocksmean rank of the 8-wide blockshalving 32 → 16 does not paythe most an 8-wide block holdscheapest leaf 32cheapest 8 or 16the decision is a column, not a rowthe 16-wide blocks carry it

Each halving reads its own width

A hierarchical matrix's cheapest leaf is found by halving it while the blocks the halving creates have rank below a quarter of the leaf. The proposal was to probe only the near blocks of one compression at a leaf of 8, predicted to do at least as well as the whole compression. It does worse: twelve cells of fifteen against thirteen, every miss naming 16 where 32 is cheapest, because the decision between 32 and 16 turns on whether a block reaches rank 8 and an 8-wide block cannot exceed it. Read each halving off the blocks of its own width instead and the probe names the cheapest leaf on all fifteen oscillatory cells and all thirty cells of six kernels, beating even the rule with every leaf compressed, from eighteen small blocks at under one per cent of the work of the compression it replaces.

hierarchy · Storage growth draw 140/3401203601080ε = 10⁻⁴8881616ε = 10⁻⁸1616163232ε = 10⁻¹²1616323232draw 240/3401203601080888161616161632321616323232frequency κ across, tolerance down; each cell prints the cheapest leafshaded: all three probes name itscattering moved no decision

A class is no longer one matrix

On a uniform grid every off-diagonal block of one width and one offset is the same matrix, so a probe that compresses one block of each class reads the whole partition's ranks and names a hierarchical matrix's cheapest leaf. On scattered points that stops being true, and the prediction was that the ranks inside a class would spread by at most one, that three blocks a class would still name the leaf everywhere, and that the probe would fail first at the highest frequency. The ranks spread by up to four. Three blocks a class still name the cheapest leaf on all thirty cells of two draws — so does one — and nothing fails at the highest frequency. The decision survives because no mean the rule compares sits close to its threshold, and scattering moved no cheapest leaf at all.

hierarchy · Storage growth

Named alongside it

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

Contraction orderTensor networkFlop countArithmetic costAdmissibilityBeam searchHierarchical matrixKernel matrixNumerical rankOff-diagonal rankStorageSymbolic phase

All concepts