Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Beam search — where it appears

A search that keeps a fixed number of the best partial solutions at each step instead of one, extending each and keeping the best of what results. Its width runs from a greedy rule to an exhaustive search, and which partial solutions count as best is a choice of ranking.

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

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

Named alongside it

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

Contraction orderHeuristicTensor networkAdmissible estimateFlop countExact ground truth

All concepts