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
| $$\mathbf{Ax=b}$$ |
and premultiplying both sides by P
| $$\mathbf{PAx=Pb}$$ |
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}$$ $$\displaystyle\mathbf{Lc}\displaystyle=\mathbf{y}$$ $$\displaystyle\mathbf{Ux}\displaystyle=\mathbf{c}$$ | (56) |
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.