4.8 Partial Pivoting

If a partial pivoting strategy is observed (pivoting is restricted to row interchanges), factorization produces matrices L and U which satisfy the following equation.

𝐋𝐔=𝐏𝐀\mathbf{LU=PA} (54)

P is a permutation matrix that is derived as follows:

  • P is initialized to I.

  • Each row interchange that occurs during the decomposition of A causes a corresponding row swap in P.

Recalling the definition of a linear system of equations


and premultiplying both sides by P


Using Equation 54 to substitute for PA yields

𝐋𝐔𝐱=𝐏𝐛\mathbf{LUx=Pb} (55)

Following the same train of logic used to derive equations Equation 40 and Equation 41 implies that a solution for A can be achieved by the sequential solution of two triangular systems.

𝐲\displaystyle\mathbf{y} =𝐏𝐛\displaystyle=\mathbf{Pb} (56)
𝐋𝐜\displaystyle\mathbf{Lc} =𝐲\displaystyle=\mathbf{y}
𝐔𝐱\displaystyle\mathbf{Ux} =𝐜\displaystyle=\mathbf{c}

Observe that the product Pb is computed before forward substitution begins. Computationally, this implies that P can be implemented as a mapping that is applied to b before substitution.