Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Wilkinson's matrix — where it appears

The matrix attaining partial pivoting's 2ⁿ⁻¹ growth bound exactly, which it does by giving the pivot rule no interchange to make. It attains the bound by giving the pivot rule nothing to interchange, which is the useful lesson: the failure is not a bad choice but an absence of choices.

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

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.

elimination · Growth 0357010514017521024528010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration|subdiagonal entry|no shiftRayleighWilkinsontwo routes to one raterate, from the spectrum0.9rate, measured0.9iterations, none / Wilkinson45symmetric 4×4, spectrum 8, 4, 2, 1.8the dashed line is the prediction

The algorithm the libraries actually run

Factorise, multiply the factors back in the other order, repeat. That description is complete and correct and produces something nobody would use — on a matrix with eigenvalues +1 and −1 it does not converge at all, and the subdiagonal entry does not move by so much as a rounding error.

spectra · The QR algorithm forward error, relative to a solution of exactly (1, 1)no pivoting · as given1 0 interchangesno pivoting · rows scaled1 0 interchangespartial · as given0 1 interchangepartial · rows scaled1 0 interchangesscaled partial · as given0 1 interchangescaled partial · rows scaled0 1 interchangecomplete · as given0 1 interchangecomplete · rows scaled0 1 interchangethe same problem twicepartial, as given10⁻¹⁸partial, rows scaled1its relative residual10⁻¹⁷complete, rows scaled10⁻¹⁸the two systems have the same solutionand one pivot rule cannot see it

The pivot that reads the units

Partial pivoting compares the entries of a column and takes the largest. Those entries carry units, so the comparison depends on them — and there is a row scaling, on the standard two-by-two that pivoting exists to fix, which makes partial pivoting perform the identical catastrophic elimination it was introduced to prevent, with no interchange at all.

elimination · Pivoting 0510152025303540012345matrix size ngrowth factorpartial pivotingrook pivotingcomplete pivotingsolid: median of 30 · dashed: worst of themat n = 40partial pivoting, median3.3rook pivoting, median2complete pivoting, median1.6rook, worst of the draw2.8the same matrices under every rulerook 3.3× partial's search

A pivot that searches one row and one column

Rook pivoting looks down a column for its largest entry, along that entry's row for a larger one, and back down that entry's column, until it finds an entry largest in both. On Gaussian matrices of size 64 it keeps the median growth factor at 2.53 against partial pivoting's 4.06 and complete pivoting's 1.88, and it compares 6,987 entries against 2,080 and 89,440. On Wilkinson's matrix it holds the growth at exactly 2 where partial pivoting reaches 9.2·10¹⁸. And on a matrix built to make it walk it compares 113,376 entries — more than complete pivoting.

elimination · Pivoting 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.

elimination · Growth 468101214160246810nlog₂ of the growth factorW ⊗ I₁W ⊗ I₂W ⊗ I₃look 1 step aheadlook 2 steps aheadlook 3 steps aheadlook 4 steps aheaddashed: 2^(n/d − 1); each family defeats every depth up to its owna fixed depth stretches the exponential

A doubling that arrives two steps late

A pivot rule that looks one elimination ahead chooses Wilkinson's growth row for row, because the doubling it sets up arrives one step later; looking two ahead escapes it. The argument said a matrix whose damage arrives two steps late would defeat the two-step rule the same way. It exists, and it is two Wilkinson matrices interleaved: W ⊗ I₂. Every look-ahead of depth one or two reproduces the greedy rule's growth on it exactly, 4 to 64 from n = 6 to 14, and depth three gives 2. Three copies defeat depth three and yield to four. The growth each depth is held to is 2^(n/d − 1): a fixed depth stretches the exponential and never removes it, at a cost that rises by a factor of about n for every step it looks.

elimination · Elimination 10¹10²10³10⁴size n = m·dentries compared by the pivot search4102040complete pivotingrook pivotinghalf rookpartial pivotingone dot per matrix and rulethe rook's price does not see the deferral

The doubling is in the row already

Interleave d copies of Wilkinson's matrix and every pivot rule that looks up to d eliminations ahead walks into growth 2^(n/d − 1); escaping costs a look one step deeper, and a deeper look multiplies its trial eliminations. Rook pivoting looks no further than the present step and escapes every one of them — growth exactly 2 at every deferral and every size — for 3.2 times partial pivoting's comparisons whatever the deferral. The doubling a look-ahead hunts for in the future is already visible in the row in front of it. And the leak that was supposed to let the two-step rule escape was placed where no pivot is ever chosen: at every size up to one, it changes nothing.

elimination · Elimination

Named alongside it

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

Gaussian eliminationGrowth factorPartial pivotingComplete pivotingBackward errorAverage-case behaviourCombinatorial searchKronecker productRook pivotingRow scalingWorst-case analysisBackward stability

All concepts