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.