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} (38)

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

𝐀𝐱=𝐛\mathbf{Ax=b}

and premultiplying both sides by P

𝐏𝐀𝐱=𝐏𝐛\mathbf{PAx=Pb}

Using Equation 38 to substitute for PA yields

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

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

𝐲\displaystyle\mathbf{y} =𝐏𝐛\displaystyle=\mathbf{Pb} (40)
𝐋𝐜\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.