O'Reilly logo

Algorithms and Parallel Computing by Fayez Gebali

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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:

(20.10) c20e010

Consider the 5 × 5 lower triangular linear system:

(20.11) c20e011

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

(20.12) c20e012

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.

Figure 20.1 The dependence graph of the forward substitution algorithm.

Input ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required