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 *u _{ii}* 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$ |