New parallel SOR method by domain partitioning

In this paper we propose and analyze a new parallel SOR method, the PSOR me thod, formulated by using domain partitioning and interprocessor data commu nication techniques. We prove that the PSOR method has the same asymptotic rate of convergence as the Red/Black (R/B) SOR method for the five-point st encil on both strip and block partitions, and as the four-color (R/B/G/O) S OR method for the nine-point stencil on strip partitions. We also demonstra te the parallel performance of the PSOR method on four different MIMD multi processors (a KSR1, an 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. Numeri cal results on the Paragon indicate that PSOR is more efficient than R/B SO R and R/B/G/O SOR in both computation and interprocessor data communication .