NPAC Technical Report SCCS-550

Parallel LU Factorization of Block-Diagonal-Bordered Sparse Matrices

David Koester, Sanjay Ranka, Geoffrey Fox

Submitted October 01 1993


Abstract

Research is being performed to examine the applicability of parallel direct block-diagonal-bordered sparse matrix solvers for irregular sparse matrix problems derived from the electrical power systems community. Moreover, we believe that this research also has utility for irregular sparse matrix factorization for applications where the data is hierarchical. Direct block-diagonal-bordered sparse matrix algorithms exhibit distinct advantages when compared to current general parallel direct sparse matrix solvers. Task assignments for numerical factorization on distributed-memory multi-processors depend only on the assignment of independent blocks to processors and the processor assignments of data in the last diagonal block. In addition, data communications are significantly reduced and those remaining communications are generally uniform and structured. Parallel block-diagonal-bordered sparse matrix algorithms require modifications to the traditional sparse matrix preprocessing phase that include an explicit {\em load balancing} step coupled to a specialized {\em ordering} step to uniformly distribute the workload throughout a distributed-memory multi-processor. In this paper, we propose a new preprocessing phase that includes specialized {\em ordering} and {\em load balancing} techniques, we describe in detail the mathematics of block-diagonal-bordered sparse matrix solvers, and we present implementation details and empirical parallel performance data for a prototype direct block-diagonal-bordered sparse matrix solver running on a Thinking Machines CM-5 using message passing.


PostScript version of the paper

Hypertext version of the paper