
SOR as a Preconditioner
M. A. DeLong and J. M. Ortega
November 7, 1994
1 Introduction
It is wellknown (see, e.g. [2] and [4]) 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[9]); 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 conjugategradient type methods such as GMRES ([6]). In fact, Saad[5] showed promising results using several steps of GaussSeidel iteration as a preconditioner in conjunction with the GMRES iteration, and the present paper complements his results. Shadid and Tuminaro[7] have also reported experiments using GaussSeidel as a preconditioner. However, they used only one GaussSeidel 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 twodimensional convectiondiffusion equation (see, e.g., [3])
? (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 fivepoint 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)