Orderings, Multicoloring, and Consistently Ordered Matrices
David L. Harrar · SIAM Journal on Matrix Analysis and Applications · 1993
The use of multicoloring as a means for the efficient implementation of diverse iterative methods for the solution of linear systems of equations, arising from the finite difference discretization of partial differential equations, on both parallel (concurrent) and vector computers has been extensive; these include SOR-type and preconditioned conjugate gradient methods as well as smoothing procedures for use in multigrid methods. Multicolor orderings, corresponding to reorderings of the points of the discretization, often allow a local decoupling of the unknowns. Some new theory is presented which allows one to quickly verify whether or not a member of a certain class of matrices is consistently ordered (or $\pi $-consistently ordered) solely by looking at the structure of the matrix under consideration. This theory allows one to quickly ascertain that, while many well-known multicoloring schemes do give rise to coefficient matrices which are consistently ordered, many others do not. Some alternative orderings and multicoloring schemes proposed in the literature are surveyed and the theory is applied to the resulting coefficient matrices.