New Parallel SOR Method by Domain Partitioning Dexuan Xie Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012, xie@monod.biomath.nyu.edu ABSTRACT In this paper, we propose and analyze a new parallel SOR method, the PSOR method, formulated by using domain partitioning together with an interprocessor data-communication technique. We prove that the PSOR method can have the same asymptotic rate of convergence as the corresponding sequential SOR method for a wide class of linear systems in which the sub-matrix on each sub-grid mesh is ``consistently ordered''. We also demonstrate the parallel performance of the PSOR method on four different message passing multiprocessors (a KSR1, the Intel Delta, an Intel Paragon and an IBM SP2), along with a comparison with the point Red-Black and four-color SOR methods.