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.