Acceleration of Five-point Red-Black Gauss-Seidel
in Multigrid for Poisson Equation

Jun Zhang
Department of Mathematics
The George Washington University
Washington, DC 20052, USA


A new relaxation analysis and two acceleration schemes are proposed for the five-point Red-Black Gauss-Seidel smoothing in multigrid for solving two dimensional Poisson equation. For a multigrid V cycle, we discovered that under-relaxation is applicable to restriction half cycle and over-relaxation is applicable to interpolation half cycle. Numerical experiments using modified multigrid V cycle algorithms show that our simple acceleration schemes accelerate the convergence rate by as much as 34% with negligible cost. This result is contrary to the existing belief that SOR is not suitable for using as a smoother in multigrid for Poisson equation, because the gain in computational savings would not pay for the cost of implementing it. More important is the idea of employing different parameters to accelerate the reduction of low and high frequency errors separately. Our discovery offers a new way for SOR smoothing in multigrid.

This paper was published in Applied Mathematics and Computation, Vol. 80 (1), 73--93 (1996).