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 uii ≠ 0, then we can determine the unknowns according to the equations
(20.25)
where x5 must be calculated before x4 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.
Get Algorithms and Parallel Computing now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
