20.3 FORWARD SUBSTITUTION (DIRECT TECHNIQUE)
The general form for a system of linear equations was given in Eq. 20.1. Forward substitution technique converts the square matrix A into a lower triangular form:
Consider the 5 × 5 lower triangular linear system:
If all lii ≠ 0, then we can determine the unknowns according to the equations
where x1 must be calculated before x2 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.
20.3.1 Forward Substitution Dependence Graph
The iterations in Eq. 20.12 use two indices i and j and we can use the results of Chapters 10 or 11 to study the parallelization of the forward substitution algorithm. Figure 20.1 is the dependence graph of the iterations in Eq. 20.12. Note that the variable x is an input/output variable and this explains why we have two sets of x, one set for the output instances of x and the other set is for the input instances of x.