SOR as a Preconditioner
M. A. DeLong and J. M. Ortega
November 7, 1994
It is well-known (see, e.g.  and ) that the use of red/black or multicolor orderings to parallelize SSOR or ILU preconditioning may seriously degrade the rate of convergence of the conjugate gradient method, as compared with the natural ordering.
The SOR iteration itself, however, does not suffer this degradation. Indeed, if the coefficient matrix is consistently ordered with property A, the asymptotic rates of convergence of the natural and red/black orderings are identical (Young); moreover, in practice one quite often sees faster convergence in the red/black ordering than in the natural ordering. This suggests the possible use of SOR as a parallel preconditioner. It cannot be a preconditioner for the conjugate gradient method on symmetric positive definite systems since the corresponding preconditioned matrix is not symmetric. But this restriction does not apply to nonsymmetric systems and conjugate-gradient type methods such as GMRES (). In fact, Saad showed promising results using several steps of Gauss-Seidel iteration as a preconditioner in conjunction with the GMRES iteration, and the present paper complements his results. Shadid and Tuminaro have also reported experiments using Gauss-Seidel as a preconditioner. However, they used only one Gauss-Seidel iteration and, as our experiments show, this is usually not competitive.
2 Experimental Results on a Model Problem
We first present some experimental results on a two-dimensional convectiondiffusion equation (see, e.g., )
? (uxx + uyy) + oe(ux + uy) = f(x; y) (2.1)
on the unit square with Dirichlet boundary conditions. For simplicity we take oe to be constant. The equation (2.1) is discretized by standard five-point finite differences using centered differences for the first derivative terms. The right hand side f of (2.1) is chosen so that the exact solution of the discrete system is known. If there are n = N2 interior points, this results in an n ? n linear system
Au = b (2.2)