Efficient Parallelization of Relaxation Iterative Methods for
Solving Banded Linear Systems on Multiprocessors
Pedro Diniz and Tao Yang
Department of Computer Science,
University of California at Santa Barbara
Santa Barbara, CA 93106-5110
Abstract
Iterative methods can be used to solve large banded linear systems on
concurrent processors. The choice of the most suitable method depends
upon matrix properties. We concentrate on the implementation of the
Successive-Over-Relaxation (SOR) method on distributed-memory machines.
We present an efficient method for partitioning and scheduling SOR
computation. Our work uses the idea of overlapping computation among
several iterations, but also carefully designs the execution ordering
of the SOR computation and synchronization points for data communication.
Load is evenly balanced among processors and computation can be overlapped
with communication. The effectiveness of this approach is validated by
experimental results on the Intel Paragon and nCUBE distributed-memory
multiprocessors.