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 70 or Equation 71 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 63 with u${}_{ii}$ being one. Substituting Equation 63 into Equation 47 yields:

$x_{i}=y_{i}-\displaystyle\sum_{j=i+1}^{n}\frac{l_{ji}x_{j}}{l_{jj}},% \operatorname{where}i=n,n-1,\cdots,1$ | (74) |

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}\text{[i]}$ |

for $j=i+1,\cdots,n-1$ |

$\alpha=\alpha-\displaystyle\frac{\mathbf{l}\text{[jn-j(j+1)/2+i]}}{\mathbf{l}% \text{[jn-j(j+1)/2+j])}}\cdot\mathbf{x}\text{[j]}$ |

$\mathbf{x}\text{[i]}=\alpha$ |