Is SOR Color-Blind?

Abstract

The work of Young in 1950, see Young [1950], [1971], showed that the Red/ Black ordering and the natural rowwise ordering of matrices with Property A, such as those arising from the 5-point discretization of Poisson’s equation, lead to SOR iteration matrices with identical eigenvalues. With the advent of parallel computers, multicolor point SOR schemes have been proposed for more complicated stencils on 2-dimensional rectangular grids, see Adams and Ortega [1982] for example, but to our knowledge, no theory has been provided for the rate of convergence of these methods relative to that of the natural rowwise scheme. New results show that certain matrices may be reordered so the resulting multicolor SOR matrix has the same eigenvalues as that for the original ordering. In addition, for a wide range of stencils, we show how to choose multicolor orderings so the multicolor SOR matrices have the same eigenvalues as the natural rowwise SOR matrix. The strategy for obtaining these orderings is based on “data flow” concepts and can be used to reach Young’s conclusions above for the 5-point stencil. The importance of these results is threefold. Firstly, a constructive and easy means of finding these multicolorings is a direct consequence of the theory; secondly, multicolor SOR methods can be found that have the same rate of convergence as the natural rowwise SOR method for a wide range of stencils used to discretize partial differential equations; and thirdly, these multicolor SOR methods can be efficiently implemented on a wide class of parallel computers.