We can push the search for a pivot one step further, by choosing as pivot the largest entry in the remaining submatrix at any step. That is, row and column interchanges are performed at each stage to ensure that the inequalities

all hold, then the stronger bound

has been obtained by Wilkinson (1961).

This strategy is known as full or complete pivoting. Note that f (n) is much smaller than 2^{n-1} for large n (for example f (100) — 3570). It was speculated that f (n) may be replaced by n, but this was disproved by Gould (1991), who found a 13x13 matrix for which the growth is 13.0205.

The choice of pivoting strategy

The bound (4.4.4) for partial pivoting is achieved for a carefully contrived matrix, as shown by Wilkinson (1965, p. 212), but years of experience in solving such problems in the dense case have established partial pivoting as the algorithm of choice. To this date, we have seen no documented advantage of working harder to control stability through rook pivoting or full pivoting in the dense case. Furthermore, there is no advantage to threshold pivoting in the dense case, since each pivot choice involves the same amount of computation and each has to be examined whether using threshold or partial pivoting. When we examine local pivoting strategies for the sparse case in Chapter 5, and in more detail in Chapter 7, we will bring both threshold and rook pivoting together.