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 35 as long as the permutations are logged and taken into account during the substitution process. The choice of pivot elements $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 $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 Loan[2].
For an implementation of Doolittle’s method with scaled
partial pivoting, see algorithm 3.5 of
Conte and de Boor[5].
Crout’s method with scaled partial pivoting is implemented in
section 2.3 of
Press
The following sections present a brief introduction to the topic of pivoting to reduce numerical instability.