Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Rook pivoting — where it appears

A pivoting rule for Gaussian elimination that searches along a column, then along the row of the entry found, and so on, until an entry is the largest in both. It usually needs a few scans a step and keeps growth far smaller than partial pivoting's worst case.

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

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 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.

elimination · Growth

Named alongside it

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

Complete pivotingGaussian eliminationGrowth factorPartial pivotingBackward errorBackward stabilityCondition numberFlop countRow scalingWilkinson's matrixWorst-case analysis

All concepts