next up previous
Next: Introduction

A Parallel Gauss-Seidel Algorithm for Sparse Power Systems 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

A Condensed Version of this Paper was presented at SuperComputing '94

NPAC Technical Report --- SCCS 630

4 April 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.





David P. Koester
Sun Oct 22 15:29:26 EDT 1995