Threshold pivoting

While we want to control the size of the multiplier, we may find adherence to (4.4.1) overly restrictive when other factors need to be taken into account, for example, sparsity or moving data in and out of cache. The compromise strategy is termed threshold pivoting and requires the satisfaction of the inequalities

where u, the threshold parameter, is a value in the range 0 < u < 1.

If u has the value 1, we have the partial pivoting condition while if u is very small, we have essentially no pivoting except to avoid zeros. Any value between these allows some pivoting accompanied by some growth for the multipliers. The bound (4.4.4) is replaced by

For the case where A is dense and can be held in memory, there is no advantage to introducing this flexibility, since the same number of compares and the same amount of computation will be done independently of the value of u. We will return to this strategy in Section 5.2.1 when we consider the sparse case.

Rook pivoting

Growth in the course of the computation may occur for reasons other than having a multiplier larger than 1. Growth can take place steadily with multipliers bounded by 1, as is shown by a carefully constructed case, which achieves the bound of equation (4.4.4). Relative growth also takes place in the example

The larger number may be the result of accumulated growth in the (1,2) position where all entries in the original, much larger, matrix were in the range (0.5,5). Note that when working with three significant decimals, the value 1.58 is destroyed by the calculation (-2420 + 1.58), but not as a result of a large multiplier. This kind of problem could also be the result of a poorly scaled problem, which we discuss in Section 4.14.

A way to address this kind of growth is to use a larger number not in the first column as the pivot. One way to do this is to use rook pivoting (Neal and Poole 1992), where the pivot is chosen if it is larger than or equal to any


entry in both its row and its column. That is to say, the new pivot a(kk satisfies the inequalities

It is intuitively clear that this strategy should produce less growth in the factorization than partial pivoting. The partial pivoting strategy only sought to limit the size of the multiplier. However, a multiplier that is less than one can produce a relatively large addition to an entry in the lower submatrix if an entry in the row is much larger than the pivot. Foster (1997) has shown that, for rook pivoting, the growth is bounded by:

Experience has shown that often the number of compares to find the pivot satisfying the rook criteria is only modestly more than partial pivoting. However, it is possible to create a case where every entry in the matrix must be examined (see Exercise 4.6).

While it would appear that rook pivoting does a better job of controlling growth than partial pivoting, it has not been used much in computer codes for dense matrices. We do not know if this is because partial pivoting is usually stable or because of a lack of stability monitoring in existing codes. We will, however, return to rook pivoting in Section 5.2 because it is much more attractive for sparse matrices.

< Prev   CONTENTS   Source   Next >