The Rook's pivoting strategy (Q1591193)

A theoretical proof is given that the pivoting strategy, called Rook's pivoting, produces computed solutions that have consistently greater accuracy than partial pivoting. Rook's pivoting searches for pivots that are maximal in absolute value in both the row and column they reside. It is shown that, as with complete pivoting, Rook's pivoting usually produces an upper-triangular system whose hyperplanes are very well-oriented with respect to their corresponding coordinate axes. Furthermore, Rook's pivoting usually produces back-substitution phase error multipliers whose magnitudes are much smaller than those produced by partial pivoting. If the forward course of Gaussian elimination is performed in double precision using Rook's pivoting strategy, then the round-off error is usually well controlled and the back substitution phase is almost always numerically stable.