NPAC Technical Report SCCS-604
Parallel Choleski Factorization of Block-Diagonal Bordered Sparse Matrices
David Koester, Sanjay Ranka, Geoffrey Fox
Submitted 01 22.94
Abstract
This paper presents research into parallel block-diagonal-bordered
sparse Choleski factorization algorithms developed with special
consideration to irregular sparse matrices originating in the
electrical power systems community. Direct block-diagonal-bordered
sparse Choleski algorithms exhibit distinct advantages when compared
to general direct parallel sparse Choleski algorithms. Task
assignments for numerical factorization on distributed-memory
multi-processors depend only on the assignment of data to blocks, and
data communications are significantly reduced with uniform and
structured communications. Choleski factorization algorithms for
block-diagonal-bordered form matrices require a specialized ordering
step coupled to an explicit load balancing step in order to generate
this matrix form and to uniformly distribute the computational
workload for an irregular matrix throughout a distributed-memory
multi-processor. Matrix orderings are performed using a diakoptic
technique based on node-tearing-nodal analysis, which permits load
balancing on either the number of calculations in the factorization
step or the number of calculations in the forward reduction and
backward substitution phase. Empirical performance measurements for
real power system load-flow matrices are presented for an
implementation of a parallel block-diagonal-bordered Choleski
algorithm run on a distributed memory Thinking Machines CM-5
multi-processor.