As stated previously, symmetry reduces the amount of work required to decompose symmetric systems into triangular factors. It does not reduce the work required to actually solve the system from an existing triangular factorization. Implementing backward substitution for a symmetric decomposition reduces to making sure that implicit data (i.e. the portion of the symmetric factorization that is not not physically stored) is correctly derived from the explicitly stored data. See Section 7.2 for a discussion of implicit data in symmetric LU decompositions.
Backward substitution solves upper triangular systems. When U is available, the symmetric and asymmetric solution algorithms are identical. See Section 5.2 for the general implementation of backward substitution. If U is stored in a linear array, use Equation 86 or Equation 87 for indexing.
The case in which L is the explicit factorization merits further attention. If L is an n × n matrix containing the upper triangular factors of a symmetric matrix, then U is unit lower triangular and obtained from L via Equation 79 with uii being one. Substituting Equation 79 into Equation 63 yields:
| $$x_{i}=y_{i}-\displaystyle\sum_{j=i+1}^{n}\frac{l_{ji}x_{j}}{l_{jj}},\mbox{ where }i=n,n-1,\cdots,1$$ | (90) |
Algorithm 18 implements this inner product formulation of backward substitution for symmetric systems whose lower triangular factors are available.
| for $i=1,\cdots,n$ |
| $\alpha=y_{i}$ |
| for $j=1,\cdots,i-1$ |
| $\alpha=\alpha-\displaystyle\frac{l_{ji}}{l_{jj}}x_{j}$ |
| $x_{i}=\alpha$ |
If L is stored in a linear array with zero based indexing, the inner product formulation of back substitution is stated in Algorithm 19.
| for $i=n-1,\cdots,0$ |
| $\alpha=\mathbf{y}{[i]}$ |
| for $j=i+1,\cdots,n-1$ |
| $\alpha=\alpha-\displaystyle\frac{\mathbf{l}{[jn-j(j+1)/2+i]}}{\mathbf{l}% {[jn-j(j+1)/2+j]}}\cdot\mathbf{x}{[j]}$ |
| $\mathbf{x}[i]=\alpha$ |