4.9 Complete Pivoting

If a complete pivoting strategy is observed (pivoting involves both row and column interchanges), factorization produces matrices L and U which satisfy the following equation.

𝐋𝐔=𝐏𝐀𝐐\mathbf{LU=PAQ} (41)

where P is a row permutation matrix and Q is a column permutation matrix. Q is derived from column interchanges in the same way P is derived from row interchanges.

If A and its factors are related according to Equation 41, then Equation 19 can still be solved for A by the sequential solution of two triangular systems.

𝐲\displaystyle\mathbf{y} =𝐏𝐛\displaystyle=\mathbf{Pb} (42)
𝐋𝐜\displaystyle\mathbf{Lc} =𝐲\displaystyle=\mathbf{y} (43)
𝐔𝐳\displaystyle\mathbf{Uz} =𝐜\displaystyle=\mathbf{c} (44)
𝐱\displaystyle\mathbf{x} =𝐐𝐳\displaystyle=\mathbf{Qz} (45)

Since Equation 40 and Equation 42 are identical, P can still be implemented as a mapping that is applied to b before substitution begins. Since Equation 45 computes the product Qz after back substitution is finished, Q can be implemented as a mapping that is applied to A following the substitution process.

If A is symmetric, pivoting for numerical stability may destroy the symmetry of the LU decomposition of A. For a symmetric factorization of A, matching row and column interchanges are required. In other words, pivoting must be complete and the permutation matrices must be related as follows: