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 5 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 0316032613261326234633464356435650.25316131663468347138733975417641770.52660286832763380418843914595469812162237429863310343117461244913251136214621775259033116461504916753178551863136214762294321264517048198522135422157631178181013114945207482405227054280846498418113321694623849275533125333800.250.512358τ for partial orders, ranked by cost so farτ forpairingscell: networks solved exactly · beneath: pairings pricedthe order cut needs the room

The prefix sits further down

A beam over contraction orders cuts twice at every level — once among the pairings out of each partial order, ranked by the size of their result, and once among the partial orders that survive, ranked by their cost so far — and one tolerance had been widening both. Measured separately, the exhaustive order's pairing is the size ranking's first choice on 34 of 60 seven-tensor networks; its prefix sits a median factor of 2.3 above the cheapest prefix on offer, and needs more room than its pairing on 49. So the width belongs at the order cut, as predicted. What was not predicted is the other half: widening the pairing cut alone is worse than not widening at all, because it hands the cost-so-far ranking more chances to choose a cheap-first prefix.

cost · Contraction 110¹110¹the order cut's needfirst-level readingthe kept pairings' ratiodearest kept overcheapest of alldashed: equaldotted: a factor 1.5seven tensors, sixty networksthe offer does not show the need

The need is set further on

A beam over contraction orders needs a wide tolerance at its partial-order cut, a median factor of 2.33 at seven tensors, and the beam was predicted to see that need in its own first level — the ratio of the dearest prefix it is offered to the cheapest, within a factor of 1.5 on four networks in five. The best such ratio is within 1.5 on 32 of 60, and none ranks the networks better than chance. A beam that sets its tolerance from its first level lands on the line the fixed tolerances draw. The ratio is exact where the need is set at the first level, and 35 of 60 networks set it later.

cost · Contraction

Named alongside it

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

Contraction orderTensor networkFlop countHeuristicAdmissible estimateGreedy algorithmExact ground truth

All concepts