Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Growth — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 0816243240110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴matrix size ngrowth factor max|u| / max|a|the 2ⁿ⁻¹ boundworst of 30 randommedian randomWilkinson's matrix sits on the bound30 Gaussian matrices per sizeat n = 40: bound 5.5·10¹¹, worst 4.8

    The bound that is never attained

    Partial pivoting's stability guarantee permits the entries to double at every step — a factor of 5.5·10¹¹ at n = 40. The measured growth on random matrices of that size is about three. The gap is eleven orders of magnitude, and the guarantee is still worth having.

    part 3 · elimination
  2. 0246810121416110¹10²10³10⁴10⁵10⁶length of the interval Tgrowth factorpartialrookcompleteh = 0.3, 102 unknownspartial, T = 15.01.3·10⁵e^(5T/6)/21.3·10⁵complete2largest κ8.3a boundary-value problem, not a constructionκ single-digit throughout

    The growth a boundary-value problem supplies

    Large growth under partial pivoting is usually said to need a matrix built for it. A two-point boundary-value problem solved by multiple shooting supplies one without being asked: its growth factor is e^(5T/6)/2 to four figures — 1.1·10⁴ at an interval of 12, 1.3·10⁵ at 15 — on a matrix whose condition number never exceeds 8.3, while rook and complete pivoting keep it below 2. And it is the finer shooting grid that grows: below a step of 0.3397 the choice partial pivoting makes turns on one entry against one, and above it there is no growth at all.

    part 4 · elimination
  3. 10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹110²10⁴standard deviation of the noise σmedian growth factormargin 0.00564shootingWilkinsonwhat the growth rests onWilkinson, no noise5.5·10¹¹Wilkinson, σ = 10⁻¹⁴2shooting, σ = 10⁻⁸1.1·10⁴pivot margin0.0056thirty draws at every pointa tie breaks at any noise; a margin needs its own size

    A worst case is as fragile as its margin

    Wilkinson's matrix grows by 5.5·10¹¹ under partial pivoting, and adding Gaussian noise of 10⁻¹⁴ to every entry takes its median growth to exactly 2. The shooting matrix from a boundary-value problem grows by 1.1·10⁴, and noise ten million times larger leaves it untouched. The difference is what each worst case rests on. Wilkinson's rests on exact ties between candidate pivots, which any noise breaks. The shooting matrix's rests on a choice made by a margin of 5.6·10⁻³, and between 10⁻⁶ and 10⁻³ its median growth is that margin divided by the noise, times a constant between one half and four thirds.

    part 5 · elimination
  4. 10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²110¹10²10³10⁴standard deviation of the noise σmedian growth factorthe marginevery entrynonzeros onlyrelative, per entryone error in Estep 0.3, margin 0.00564, thirty drawsno noise1.1·10⁴every entry, σ = 10⁻⁵536nonzeros only, σ = 10⁻³1.1·10⁴one error in E, σ = 10⁻², draws kept21every curve is the same matrixonly what the noise touches changes

    Noise the growth amplifies

    The shooting matrix's growth of 1.1·10⁴ fell under noise as its pivot margin divided by the noise, and the explanation offered was noise reversing partial pivoting's choices. But noise of 10⁻⁵ is five hundred times smaller than that margin. Add the same noise only to the entries that are not zero and every draw keeps the whole growth up to 10⁻³. The dense noise was not reversing the comparisons by itself: it sat in the zeros, the elimination multiplied it by the growth already made, and a comparison flips when that product reaches about four tenths of the margin — at every noise level from 10⁻⁶ to 10⁻³.

    part 6 · elimination
  5. 10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³r½ recorded during one factorisationnoise that halves the growthT 6, h 0.3: 75T 9, h 0.3: 910T 12, h 0.3: 11000T 15, h 0.3: 1.3·10⁵T 12, h 0.25: 11000T 12, h 0.2: 11000T 9, h 0.15: 910measured ÷ predicted, shooting matricessmallest ratio0.92largest ratio2.4Wilkinson: recorded r½0Wilkinson: noise that halves it10⁻¹⁶one factorisation, one extra comparison a stepdashed: a factor of three either way

    A margin the factorisation records

    Partial pivoting finds the second-largest candidate in every column it scans, and throws it away. Keep it, divide the gap by the growth reached at that step, and take the smallest over the steps before half the final growth has arrived. That one number, recorded by the factorisation that is already running, predicts the dense noise that halves the growth to within a factor of 0.92 to 2.4 on shooting matrices whose growth runs from 75 to 1.3·10⁵ and whose fragility spans three and a half decades — and on Wilkinson's matrix it is exactly zero.

    part 7 · elimination
  6. noise that halves the growthshooting, partial pivoting0.0018shooting, τ = 0.10.56Wilkinson, τ = 0.10.1800.10.20.30.40.50.60.70.80.9110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1one minus the thresholdstored noise that halves the growthshooting, T = 12, h = 0.3Wilkinson, n = 24the same growth at every thresholdheld by a choice noise must push further to reverse

    A threshold that holds the growth still

    Partial pivoting's large growth on the shooting matrix rests on a margin of 5.6·10⁻³, and Wilkinson's rests on exact ties, which a perturbation at rounding breaks. A sparse code pivots with a threshold instead, taking the sparsest row among candidates within a factor τ of the largest. At every threshold from 1 to 0.1 both matrices grow by exactly as much as under partial pivoting. But the growth is now held by row counts, which no perturbation of the values can reverse: at τ = 0.1 it survives noise on the stored entries up to 0.56 on the shooting matrix, three hundred times more, and 0.18 on Wilkinson's, where partial pivoting's goes at 10⁻¹⁶. The margin that predicts it is the chosen candidate's height above the threshold line, and it needs no division by the growth.

    part 8 · elimination
  7. step 0.3rate per interval1.3largest r that catches it1.3110¹10²10³10⁴trigger sensitivity rgrowth factor1.021.324dashed: e to the five-sixths of the stepthe trigger must be finer than the growth

    A trigger finer than the growth

    Threshold pivoting cannot remove the shooting matrix's growth of 1.1·10⁴, because at τ = 1 it is partial pivoting. The proposal was a factorisation that notices growth on a step and searches as rook pivoting does after it, paying for the stricter search only where growth is made. But no step makes much: the largest one-step rise is exactly the growing mode's rate over one shooting interval, 1.284 at a step of 0.3, and 1.133 at 0.15. A trigger finer than that rate holds the growth at 2.00 for about two thirds of rook's extra search; one coarser never fires. And a trigger fine enough searches as rook on a quarter of an ordinary random matrix's steps.

    part 9 · elimination

All series