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.