next up previous
Next: About this document Up: Parallel LU Factorization of Previous: The Hierarchical Data

Block Bordered Diagonal Form Sparse Matrix Algorithms

This appendix contains detailed descriptions of both the sequential and parallel algorithms implemented for the Thinking Machines CM-5. Figures 23 and 24 describe the sequential block-diagonal-bordered sparse LU factorization algorithm that was implemented using the hierarchical data structure described in section 5. Figure 23 describes the sequential algorithm to factor the independent blocks, and figure 24 describes the sequential algorithm to factor the last block. Figures 25 and 26 respectively describe the sequential forward reduction and backward substitution steps. Figures 28 and 27 describe the parallel block-diagonal-bordered sparse LU factorization that was implemented for the CM-5 using the CMMD message passing libraries for the node and host programs respectively. The parallel forward reduction algorithm is presented in figures 30 and 29, also for the node and host programs respectively. The parallel backward substitution algorithm is presented in figure 31. Additional implementation details are discussed in section 5.

 
Figure 23: Sequential Sparse LU Factorization --- Independent Blocks 

 
Figure 24: Sequential Sparse LU Factorization --- Last Block 

 
Figure 25: Sequential Sparse Forward Substitution 

 
Figure 26: Sequential Sparse Backward Substitution 

 
Figure 27: Parallel Sparse LU Factorization - Node Program 

 
Figure 28: Parallel Sparse LU Factorization - Host Program 

 
Figure 29: Parallel Sparse Forward Reduction - Node Program 

 
Figure 30: Parallel Sparse Forward Reduction - Host Program 

 
Figure 31: Parallel Sparse Backward Substitution 



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