After a matrix A is factored into the two matrices L and U in
the solution of the vector x for a given b vector follows a two step process. First, there is the forward reduction step where
is solved for a temporary working vector y, and then the solution for x is obtained by the backward substitution step
LU factored matrices can be reused many times when solving for
multiple right-hand side vectors in the linear equation
. It is common practice in iterative
solutions of non-linear equations using Newton's method to evaluate
the linear system in the Jacobian only every k
iterations, because of the computational complexity to solve the
linear system. Consequently, efficient parallel implementations of
forward reduction and backward substitution are required even though
the complexity of these steps are significantly less than the workload
to factor the matrix.
The sequential version of forward reduction and backward
substitution are traditionally viewed as straight forward
implementations of loops to directly solve for and
in
the equations
and
In these equations, the values and
are the lower
and upper triangular matrices respectively, that are generated by the
LU factorization step. For L and U matrices generated by Crout's
factorization algorithm, equation 9 does not require a
final division operation because the all values
are equal to
1. However, like factorization, there are multiple distinct ways to
manipulate the data in the nested for loops. Instead of
performing reduction and substitution by rows using
equation 8 and equation 9, the values
and
can be calculated using
and
respectively
in the formulas
and
Then the entire column in forward reduction or backward
substitution respectively can be updated using the formulas
and
After the entire column has been updated, the values of
and
can be calculated and this procedure
iteratively repeated for all columns.
Figure 5 presents a comparison of row and sub-matrix
reduction/substitution. This figure illustrates the loop order for
the two algorithm types by the large arrows, while smaller arrows
depict the calculation order. For row reduction/substitution, the
calculations are constrained to within rows, after which a value of
or
is calculated. However, for sub-matrix
reduction/substitution, the value of
or
is calculated
first, then all values remaining in the sub-matrix are used to update
and
values.
Figure 5: Alternative Forward Reduction/Backward Substitution Schemes