Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Combinatorial search — where it appears

Examining every member of a finite set of choices, such as every row ordering of an elimination, to find the best one exactly rather than by a rule. It is only affordable at small sizes, and what it buys there is a ground truth that a heuristic can be scored against.

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

an ordering that is theregreedy at n = 764best ordering at n = 72its largest multiplier1456710¹10²matrix size ngrowth factorgreedy, ties forwardsgreedy, ties backwards, ε = 10⁻¹²greedy, ties backwards, ε = 0the best orderingthe best order is 2 3 4 5 6 1 at n = 6one cyclic shift of the rows

The order the greedy rule cannot choose

Wilkinson's matrix is the standard demonstration that partial pivoting's growth bound of 2^(n−1) is attained. It is attained by the row order the greedy rule picks, and not by the matrix: a single cyclic shift of the rows gives growth 2 at every size, with no multiplier above one. At n = 7 that is 64 against 2. And perturbing one entry by 10⁻¹² leaves the good order exactly where it was while putting every tie-break of the greedy rule back on 64.

elimination · Elimination ties broken by 10⁻¹²one step ahead, n = 248.4·10⁶two steps ahead, n = 2424812162024110¹10²10³10⁴10⁵10⁶10⁷matrix size ngrowth factorgreedyone step aheadtwo steps aheadone step ahead lies exactly on greedythe damage is done a step before it shows

One step ahead is one step short

Partial pivoting takes the largest entry in the column and, on Wilkinson's matrix, walks into growth of 2^(n−1) that a cyclic shift of the rows avoids entirely. A rule that chose instead the pivot whose elimination leaves the smallest trailing submatrix was expected to see the good order at the first step. It sees nothing there: every first pivot leaves a largest entry of exactly 2, and with the ties broken by 10⁻¹² it prefers the greedy row by 10⁻¹². It attains 2^(n−1) at every size. Looking two eliminations ahead, the greedy row scores 4 and every other row 2, and the growth is 2 at every size up to 24. On random matrices one step of look-ahead helps below n = 16 and is worse than greedy on more than half of them by n = 32.

elimination · Elimination

Named alongside it

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

Exact ground truthGaussian eliminationGrowth factorLU factorisationPartial pivotingPermutationPivotingBackward errorMultipliers

All concepts