4.6 Pivoting Strategies for Numerical Stability

A solution to the numerical instability of LU decomposition algorithms is obtained by interchanging the rows and columns of A to avoid zero (and other numerically unstable) pivot elements. These interchanges do not effect the solution to Equation 19 as long as the permutations are logged and taken into account during the substitution process. The choice of pivot elements akk(k)a_{kk}^{(k)} is referred to as a pivot strategy. In the general case, there is no optimal pivot strategy. Two common heuristics are:

  • At the kth stage of the computation, choose the largest remaining element in A as the pivot. If pivoting has proceeded along the diagonal in stages 1 through k – 1, this implies the next pivot should be the largest element aij(k-1)a_{ij}^{(k-1)} where k \leq i \leq n and k \leq j \leq n. This strategy is referred to as complete pivoting.

  • At the kth stage of the computation, select the largest element in column k as the pivot. This strategy is referred to as partial pivoting.

Both procedures have good computational properties. Gaussian elimination with complete pivoting is numerically stable. In most practical applications, Gaussian elimination with partial pivoting has the same stability characteristics as complete pivoting. However, there are theoretical situations where partial pivoting strategies can become unstable.

Applications of current interest are diagonally dominant; therefore, algorithms which incorporate pivoting strategies for numerical stability are not examined in this document. For implementations of Gaussian elimination with complete and partial pivoting, see algorithms 4.4–1 and 4.4–2 of Golub and van Van Loan [8]. For an implementation of Doolittle’s method with scaled partial pivoting, see algorithm 3.5 of Conte and de Boor [3]. Crout’s method with scaled partial pivoting is implemented in section 2.3 of Press et al. [14]. Pivoting strategies which control element growth in sparse matrices are examined in Section 8.3 of this document.

The following sections present a brief introduction to the topic of pivoting to reduce numerical instability.