Coloring update methods (Q1387248)

It is known that for a special class of linear systems the iteration matrix of the lexicographically ordered successive overrelaxation (SOR) method and that of multicolor SOR with a special type of coloring have the same spectrum. However this does not imply similarity of the iteration matrices. In the present paper a coloring method for linear update methods (such as SOR) is introduced, whose iteration matrix also has the same spectrum as that of the sequential ordering. This result is more general in the following sense: it applies to general update methods and is independent of the definition of grids and stencils; it guarantees similarity of the iteration matrices of the multicolor and sequential orderings, provided that they are nonsingular.