20.4 BACK SUBSTITUTION

The general form for a system of linear equations was given in Eq. 20.1. Back substitution technique converts the square matrix A into an upper triangular form:

(20.23)

Consider the 5 × 5 upper triangular linear system:

(20.24)

If all u_ii ≠ 0, then we can determine the unknowns according to the equations

(20.25)

where x₅ must be calculated before x₄ could be evaluated and so on. Thus, it appears that the calculations are sequential, with small opportunity for parallelization. However, the techniques we discussed earlier will help us derive parallel multithreaded and systolic architectures. The procedure we used to derive scheduling and projection functions for forward substitution can be used here.