The sequential algorithm we propose for LU factorization of
block-diagonal-bordered sparse matrices follows the version of Crout's
algorithm presented during the background discussion in
section 2. The fan-in form of Crout's algorithm is followed
for each independent block and the corresponding portion of the
border. The last block is also factored in a fan-in manner, however,
data in the borders must be used in the update of values in
the last block. None of the independent blocks need be concerned with
data from other blocks or corresponding border sections, so the
algorithm to factor the last block differs from the algorithm for the
independent blocks. In this implementation, the last block is also
factored using sparse techniques. This factorization algorithm is
presented in figure 13. Other implementations of this
algorithm may consider the last block to be dense, or a combination of
sparse and dense. Such a consideration would be dependent on the
nature of the sparse matrix.
Our research into ordering power systems distribution network matrices into block-diagonal-bordered form has illustrated that there are substantial reductions in the number of fillin for this ordering technique when compared to conventional ordering techniques such as minimum degree ordering [14]. Consequently, the ordering techniques required for efficient parallel algorithms also benefit sequential algorithms.
Figure 13: Sequential Sparse LU Factorization
The remaining steps in the sequential algorithm are forward reduction
and backward substitution. The sequential version of these algorithms
are straight forward implementations of the row reduction/substitution
technique discussed in section 2.6. Pseudo-code versions of
the algorithms for sequential forward reduction and sequential
backward substitution are presented in figures 14
and 15 respectively. The backward substitution step does not
require a final division operation, because the all values
are equal to 1. Detailed versions of the factorization, forward
reduction, and backward substitution algorithms are presented in
appendix B.
Figure 14: Sequential Sparse Forward Reduction
Figure 15: Sequential Sparse Backward Substitution