SOR as a Preconditioner

Preconditioning is usually necessary for CG-type iterative algorithms for the solution of large sparse nonsymmetric linear systems. However, many good preconditioners have only marginal intrinsic parallelism -- ILU and SSOR in the natural ordering are essentially sequential algorithms. Reordering can yield very good parallelism, but can cause (severe) degradation in the rate of convergence.
We consider multi-step SOR in the red-black ordering as a preconditioner. It can have very good parallel properties, but it does not cause degradation in the overall rate of convergence, as does ILU or SSOR. We present one-processor results using multi-step SOR to precondition GMRES which substantiate this claim.
There has been some confusion in the literature as to whether this approach should be effective. We deal with these objections, and discuss the relationship between the spectral properties of the preconditioned system and the convergence of GMRES.
We also present results from the Intel Paragon and the IBM SP2 showing that as a preconditioner, multistep red-black SOR can give good scaled speedup.