A pivot that searches one row and one column

Three essays here have now said three things about the rule every library uses. The swap that is not optional found that elimination without interchanges fails silently on a matrix that needs one. The bound that is never attained found that partial pivoting’s guarantee permits the entries to double at every step, 5.5·10¹¹ at n = 40, and that random matrices of that size grow by about three. And the pivot that reads the units found a row scaling that makes partial pivoting perform the very elimination it was introduced to prevent, with no interchange at all.

Each of those essays mentions a fourth rule and moves on. Complete pivoting searches the whole remaining matrix for its largest entry, which fixes the scaling failure and the worst-case growth, and costs a search of n³/3 entries — as much as the elimination itself. Rook pivoting is the rule named as the compromise: look down the current column for its largest entry; look along that entry’s row for a larger one; if there is one, look down its column; stop when an entry is the largest in both its row and its column. A rook on a chessboard, moving along a row and a column until it finds a square that dominates both.

Nothing in the collection measures it, and the claims attached to it — that it buys most of complete pivoting’s protection at a small multiple of partial pivoting’s search — are claims about constants, which is the kind of claim this collection distrusts until it has counted.

Three rules, one factorisation, three searches #

All three rules produce a factorisation PAQ = LU with every multiplier at most one in magnitude, and all three are backward stable in the same sense: the backward error is bounded by a modest multiple of the unit roundoff times the growth factor — the largest entry the elimination ever produces, divided by the largest entry it started with. The rules differ in what they guarantee about growth and in what they pay to find each pivot, and those are the only two columns this essay needs.

Partial pivoting compares the entries of one column at each step: n + (n − 1) + … + 1 = n(n + 1)/2 comparisons over the whole elimination, 2,080 at n = 64. It swaps rows only. Its growth bound is 2ⁿ⁻¹ and it is attained.

Complete pivoting compares every entry of the remaining submatrix: the sum of the squares, 89,440 at n = 64. It swaps rows and columns. Its growth bound grows like a power of n whose exponent itself grows with log n, and the largest growth anyone has found for it is of order n.

Rook pivoting compares a column, then a row, then a column, as many times as it takes. Its cost is not fixed; it depends on how many moves the rook makes before it stops, and that depends on the matrix. The known bound on its growth is of the same super-polynomial but far-from-exponential kind as complete pivoting’s, with a larger exponent. The bound is stated here, not measured.

The routine behind every number below counts each comparison as it is made, so the search costs are exact integers rather than estimates, and it counts the rook’s moves separately so the reason for its cost is visible.

Growth on random matrices #

Thirty Gaussian matrices at each size, the median and the worst growth for each rule:

The rook’s median sits between the other two at every size, and nearer complete pivoting than partial. A useful way to read that: at n = 64 partial pivoting’s median exceeds complete pivoting’s by 2.18 and the rook’s exceeds it by 0.65, so the rook has recovered 70% of the gap in the median. At n = 16 it has recovered 65%, at n = 32 66%, at n = 80 73%. On the worst of thirty the picture is similar: at n = 64 the rook’s worst is 3.80, half of partial pivoting’s 7.47 and well above complete pivoting’s 2.31.

The numbers are small on every row, which is the bound that is never attained restated for three rules: on random matrices no rule’s growth is anywhere near its bound, and all three would give a backward error within a small factor of the rounding. The comparison matters where growth is large, and random matrices do not produce that.

Wilkinson’s matrix, where partial pivoting reaches its bound #

The matrix that makes partial pivoting’s bound exact has ones on the diagonal, minus ones below it and a column of ones at the right. Partial pivoting makes no interchange on it, because every column’s largest entry in magnitude is already the diagonal one, and the last column doubles at every step.

Rook and complete pivoting both hold the growth at exactly 2 at every size drawn, and they do it the same way: each makes a column interchange at every step and no row interchange, which brings the last column forward before it can be doubled. On a matrix whose entries start with magnitude one everywhere, which of several tied entries a rule takes is decided by how its search breaks ties, and the pivot sequence behind the 2 has been counted rather than traced; a rule breaking ties differently could make different interchanges, and that has not been measured.

The rook’s search on this matrix is a column and a row per step, which is the whole of its advantage made concrete: complete pivoting found the same pivots by searching every remaining entry. At n = 64 partial pivoting’s growth is 9.2·10¹⁸, which puts the backward error bound at about a thousand in a problem whose entries are of size one. The rook’s is 2.

What the rook’s search actually costs #

Entries compared over the whole elimination, medians over thirty Gaussian matrices:

The complete-to-partial ratio grows in proportion to n, as it must: n³/3 against n²/2. The rook-to-partial ratio is 3.2 at n = 8 and 3.4 at n = 80, a tenfold change in size moving it by a sixteenth. That is the rook’s selling point and it survives measurement, with one amendment: it is not quite a constant, and it drifts upward slowly.

The reason is in the move counts. The rook made 17 moves beyond its first column search at n = 8, 34 at 16, 72 at 32, 148 at 64 and 188 at 80 — about two per elimination step at every size. Each move costs a line of the remaining submatrix, so the search at a step costs roughly three lines where partial pivoting’s costs one: the column, one row, and a little more. On a Gaussian matrix the entry that is largest in its column is very likely to be largest in its row too, or close to it, so the rook rarely walks far.

The search against the elimination it serves #

A comparison count and a multiply-add are not the same unit, and a pivot search is only worth pricing against the work it protects. Gaussian elimination on an n-by-n matrix does about n³/3 multiply-adds, a count the same arithmetic at a different price takes as an exact integer for every ordering of it. At n = 64 that is about 87,000.

Against it, partial pivoting’s 2,080 comparisons are 2.4% of the arithmetic, the rook’s 6,987 are 8.0%, and complete pivoting’s 89,440 are 103% — the search costs more than the elimination it chooses pivots for. At n = 16 the same shares are 10%, 32% and 110%, because n²/2 against n³/3 shrinks like 3/(2n) and complete pivoting’s n³/3 against n³/3 does not shrink at all. A comparison reads two numbers and a multiply-add reads two and writes one, so a comparison is the cheaper operation and the percentages overstate every search; they overstate all three by the same factor, which leaves the ranking intact.

So on the matrices a rook usually meets, it turns a search that is a rounding error in the total into one that is a small fraction of it, and it does so at every size, because its share falls like partial pivoting’s rather than holding like complete pivoting’s. At n = 1,000, if the ratio of 3.4 held, the rook’s search would be about half a per cent of the elimination. That is the arithmetic behind the rule’s reputation, and it is an extrapolation of the measured ratio rather than a measurement at that size.

The comparison also says what the rook is not. A factorisation with nothing to pivot for is the case where no search is needed at all, because Cholesky’s growth is exactly one on every positive definite matrix; a code that knows its matrix is definite pays none of these percentages. Pivot search is a price paid for not knowing, and the rook is a way of paying less of it.

An average is not a bound #

“Rarely walks far” is a statement about Gaussian matrices, and the rook’s cost is a property of the matrix. So the next measurement is a matrix built to make it walk as far as it can.

The construction puts small entries everywhere and a staircase of increasing magnitudes down the diagonal and the subdiagonal. The largest entry of the first column is the subdiagonal one; the largest entry of that row is the next diagonal one; the largest of that column is the next subdiagonal one; and so on to the corner. Every move the rook makes finds something strictly larger, so the first step alone walks the whole staircase and scans about 2n lines. It is not a random matrix and is not offered as a typical one. It is the answer to whether the average search is a bound.

It is not. The rook compares 1,976 entries at n = 16, 14,704 at 32, 113,376 at 64 and about 219,800 at 80, against complete pivoting’s 1,496, 11,440, 89,440 and 173,880. It makes 144, 544 and 2,112 moves at the first three sizes where on a Gaussian matrix it made 34, 72 and 148. On this matrix the rook’s search is 1.27 times complete pivoting’s at n = 64, and it buys nothing for it: the growth under all three rules is 1, because the staircase needs no protection.

That is the refusal on this essay, and it is the kind of result the tail a sample never reaches is about. Thirty Gaussian matrices, or three hundred, would never have produced the staircase; the rook’s expected cost is what its description has been quietly carrying, and the word “expected” does real work. The worst case of the rook’s search is of the same order as complete pivoting’s, a constant times n³, and it is attained by a matrix anyone could write down.

Whether that matters in practice depends on whether matrices resembling the staircase arise. On the sparse side of the subject the same tension between a guaranteed search and a typical one decides which pivots a code will even consider — structure and stability stop being separable is where that tension is met in sparse factorisations — and a rook that can be walked the length of a band is one more reason the sparse codes restrict their searches. A matrix with strongly graded magnitudes along a band — which a discretisation with rapidly varying coefficients can produce — is closer to it than a Gaussian matrix is, and on such a matrix the rook’s cost would sit somewhere between the two tables. That has not been measured on any matrix from an application.

The two-by-two that disarms partial pivoting #

The pivot that reads the units took the two-by-two that pivoting exists to fix, multiplied its first row by 1/ε, and watched partial pivoting make no interchange and lose the answer completely — a forward error of 1 at ε = 10⁻¹⁶ with a residual at rounding.

The rook does not read the units on it. Before and after the scaling, at ε from 10⁻¹² down to 10⁻¹⁸, the rook makes a column interchange at every setting and its forward error is between 0 and 2.2·10⁻¹⁶ on both the given and the scaled system — which is complete pivoting’s behaviour, reached by searching one column and one row. The reason is short. After the scaling the first column no longer gives partial pivoting any reason to swap, which is the whole of the previous essay’s finding. The rook does not stop at the column: it searches the first row, where the scaling has made the off-diagonal entry 1/ε times larger than it was, finds that entry far the largest, and moves to it — the interchange the scaling was hiding, made across a column instead of down one.

That is not a proof that the rook is scale-invariant, and it is not. A row scaling can still change which entry is largest in its row and column, and a column scaling can mislead the row search the way a row scaling misleads the column search. What the two-by-two shows is that a rule which checks a candidate against its own row cannot be disarmed by scaling that row, and that is the specific failure the previous essay found.

What the rook buys, and what it does not #

Put the three measurements together and the rook’s position is clear enough to state as a trade.

It buys most of complete pivoting’s growth. Seventy per cent of the median gap on random matrices, and all of it on Wilkinson’s matrix, where the difference is between 2 and 9.2·10¹⁸.

It buys most of complete pivoting’s resistance to row scaling, on the case that matters most — the one where a scaled row hides the pivot.

It costs about three times partial pivoting’s search on typical matrices, and that ratio is nearly flat in n where complete pivoting’s grows like n.

And its cost is an average rather than a bound. A constructed matrix makes it dearer than complete pivoting, and nothing in the rule warns that it is being walked. A code that wanted a guarantee on search cost would cap the number of moves, and a capped rook is a different rule with a weaker growth guarantee — which is the trade over again, one level down.

Partial pivoting remains the default for the reason elimination is a sequence of choices gives: its growth is harmless on nearly everything, its search is the cheapest possible, and its failures are rare enough to handle when they occur. The rook is what a code reaches for when it has evidence that a matrix is of the rare kind — large growth observed, or a matrix known to be badly scaled — and wants protection without paying complete pivoting’s n³.

The same search appears where pivoting meets symmetry. When symmetry is not enough found that a symmetric indefinite factorisation must sometimes take two variables at once, and the rule that decides when — in its bounded form — is a rook search restricted to symmetric interchanges. The growth protection there is the same protection measured here, bought the same way.

Where this goes from here #

The rook in a sparse factorisation. A sparse code chooses pivots for fill as well as for size, with a threshold that accepts any entry within a factor of the largest; a threshold between fill and growth measures that trade for partial pivoting. A threshold rook — accept an entry within a factor of the largest in both its row and its column — changes which entries are admissible, and what that does to fill and to growth together is the next measurement.

The rook’s worst growth. Every growth factor above is on random, Wilkinson or staircase matrices, and the rook’s growth is modest on all of them. The worst growth actually attainable under rook pivoting is not known in closed form; constructions that push it beyond complete pivoting’s are in the literature and a search for large growth under the rook, the kind the growth essays did for partial pivoting, would say how much of the stated bound is real.

And the symmetric rook. The bounded symmetric indefinite factorisation mentioned above uses the same walk under a restriction to diagonal interchanges and two-by-two blocks. Its search cost on typical and constructed matrices, and whether a staircase exists for it too, would put the two stories about pivoting — the general one and the symmetric one — on one axis.