|
|
|
“Two-color Fourier Analysis of Iterative Algorithms for Elliptic Problems with Red/Black Ordering”
by C.-C. Jay Kuo and Tony F. Chan
April 1989
The red/black ordering scheme is often used to increase the parallelism of iteractive methods for solving elliptic PDEs. However, the convergence rates are also affected, often adversely. This paper provides a unified approach, called the two-color Fourier analysis, to study the convergence rates of iterative algorithms for elliptic problems with the red/black ordering. This Fourier tool is used to analyze different types of iterative algorithms, including the successive over-relaxation (SOR) method, symmetric successive over-relaxation (SSOR) method, preconditioned iterative methods with SSOR, ILU and MILU preconditioners and multigrid (MG) methods. By comparing the convergence rates of algorithms with the natural and red/black orderings, we show that although the red/black ordering does not affect the rate of convergence in the context of SOR and MG methods, it slows down the convergence significantly in the context of SSOR and preconditioned iterative methods.