A Two-Level Four-Color SOR Method

A two-level four-color SOR method is proposed for the nine-point discretization of the Poisson equation on a square. Instead of examining the Jacobi iteration matrix in the space domain, we consider an equivalent but much simpler four-color iteration matrix in the frequency domain. A two-level SOR method is introduced to increase the convergence rate for the frequency-domain iteration matrix. At the first level, the red and orange points, and then the black and green points are treated as groups, and a block SOR iteration is performed on these two groups. At the second level, another SOR iteration is used to decouple values at the red and orange points, and then at the black and green points. The conventional red/black SOR iteration for a five-point stencil is shown to be a degenerate case of the general two-level four-color SOR method. For the case of the nine-point stencil, a closed-form expression for the optimal relaxation parameters ω b^ * and ω ₚ^ * at the two iteration levels is. given, and the efficiency of the resulting method is shown both analytically and numerically.