next up previous
Next: The Parallel Algorithm Up: Sparse Matrix Solver Previous: The Hierarchical Data

The Sequential Algorithm

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 



next up previous
Next: The Parallel Algorithm Up: Sparse Matrix Solver Previous: The Hierarchical Data



David P. Koester
Sun Oct 22 16:27:33 EDT 1995