Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Admissible estimate — where it appears

An estimate of the work still to be done that never exceeds the true amount. Ranking partial solutions on cost so far plus such an estimate cannot make a promising one look worse than it is, though it can make a poor one look as good.

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

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

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

Named alongside it

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

Beam searchContraction orderFlop countHeuristicTensor network

All concepts