In this paper we present an efficient parallel implementation of relaxation iterative methods,
such as the Gauss-Seidel (GS) and Successive-Over-Relaxation (SOR), for solving banded
linear systems on distributed memory machines. We introduce a novel partitioning and
scheduling scheme in our implementation which allows perfect overlapping of computation
with communication, hence minimizing latency effects. We provide analytic and experimental
results to verify the effectiveness of our approach and discuss its incorporation in other iterative
solvers. Experiments on nCUBE and Intel Paragon machines for several sample banded
matrices show that the proposed approach yields good performance on these machines.