# 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.