The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-SIPI-139

“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.

To download the report in PDF format click here: USC-SIPI-139.pdf (1.4Mb)