5.3 Outer Product Formulation

In Section 5.1 and Section 5.2 triangular systems are solved by techniques which use inner product accumulation on each row of A. It is possible to formulate these algorithms in a manner that arrives at the solution through partial sum accumulations (also known as an outer product). Algorithm 6 solves lower triangular systems using an outer product formulation of forward substitution. You should observe that if bi is zero, the ith stage can be skipped. In this situation, yi will also be zero and the term yilki will not change any of the partial sums bk.

Algorithm 6: Forward Substitution - Outer Product
for 1=1,,n1=1,\cdots,n
   yi=biliiy_{i}=\displaystyle\frac{b_{i}}{l_{ii}}
   for k=i+1,,nk=i+1,\cdots,n
      bk=bk-yilkib_{k}=b_{k}-y_{i}l_{ki}

Algorithm 7 solves upper triangular systems are using an outer product formulation of the backward substitution algorithm. Also observe that when yi is zero, the ith stage can be skipped. In this situation, xi will also be zero and the term xiuki will not change any of the partial sums yk.

Algorithm 7: Back Substitution - Outer Product
for i=1,,ni=1,\cdots,n
   xi=yiuiix_{i}=\displaystyle\frac{y_{i}}{u_{ii}}
   for k=i-1,,1k=i-1,\cdots,1
      yk=yk-xiukiy_{k}=y_{k}-x_{i}u_{ki}

George and Liu [6] examine outer product solutions of triangular systems as do Tinney et al. [16].