Next: Introduction
Parallel Choleski Factorization of Block-Diagonal-Bordered Sparse Matrices
D. P. Koester, S. Ranka, and G. C. Fox
School of Computer and Information Science and
The Northeast Parallel Architectures Center (NPAC)
Syracuse University
Syracuse, NY 13244-4100
dpk@npac.syr.edu, ranka@top.cis.syr.edu, gcf@npac.syr.edu
NPAC Technocal Report --- SCCS 604
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.
David P. Koester
Sun Oct 22 15:40:25 EDT 1995