NPAC Technical Report SCCS-630
A Parallel Gauss-Seidel Algorithm for Sparse Power Systems Matrices
David Koester, Sanjay Ranka, Geoffrey Fox
Submitted July 27 1994
Abstract
We describe the implementation and performance of an efficient
parallel Gauss-Seidel algorithm that has been developed for irregular,
sparse matrices from electrical power systems applications. Although,
Gauss-Seidel algorithms are inherently sequential, by performing
specialized orderings on sparse matrices, it is possible to eliminate
much of the data dependencies caused by precedence in the
calculations. A two-part matrix ordering technique has been developed
--- first to partition the matrix into block-diagonal-bordered form
using diakoptic techniques and then to multi-color the data in the
last diagonal block using graph coloring techniques. The ordered
matrices often have extensive parallelism, while maintaining the
strict precedence relationships in the Gauss-Seidel algorithm. We
present timing results for a parallel Gauss-Seidel solver implemented
on the Thinking Machines CM-5 distributed memory multi-processor. The
algorithm presented here requires active message remote procedure
calls in order to minimize communications overhead and obtain good
relative speedup. The paradigm used with active messages greatly
simplified the implementation of this sparse matrix algorithm.