New Parallel SOR Method by Domain Partitioning

Dexuan Xie
Courant Institute of Mathematical Sciences
New York University
251 Mercer Street
New York, NY 10012

Loyce Adams
Department of Applied Mathematics
University of Washington
Seattle, Washington 98195


In this paper, we propose and analyze a new parallel SOR method, the PSOR method, formulated by using domain partitioning and interprocessor data communication techniques. We prove that the PSOR method has the same asymptotic rate of convergence as the Red/Black (R/B) SOR method for the 5-point stencil on both strip and block partitions, and as the four-color (R/B/G/O) SOR method for the 9-point stencil on strip partitions. We also demonstrate the parallel performance of the PSOR method on four different MIMD multiprocessors (a KSR1, the Intel Delta, a Paragon and an IBM SP2). Finally, we compare the parallel performance of PSOR, R/B SOR and R/B/G/O SOR. Numerical results on the Paragon indicate that PSOR is more efficient than R/B SOR and R/B/G/O SOR in both computation and interprocessor data communication.

Contributed June 4, 1997.