A Caltech Library Service

Orderings, Multicoloring, and Consistently Ordered Matrices

Harrar, David L., II (1993) Orderings, Multicoloring, and Consistently Ordered Matrices. SIAM Journal on Matrix Analysis and Applications, 14 (1). pp. 259-278. ISSN 0895-4798. doi:10.1137/0614021.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1993 Society for Industrial and Applied Mathematics. Received by the editors July 2, 1990; accepted for publication (in revised form) May 8, 1991. This research was supported in part by Department of Energy grant DE-FG03-89ER25073 and by the National Science Foundation under Cooperative Agreement CCR-8809615. The government has certain rights in this material. The author would like to thank Professors Herbert B. Keller, James M. Ortega, and David M. Young for looking over preliminary versions of this manuscript and Douglas A. Waetjen for helpful discussions. The detailed comments of two of the referees (one of whom pointed out the similarity between Theorem 3.7 and Theorem 14.3.2 of Young [25]) are also greatly appreciated.
Funding AgencyGrant Number
Department of EnergyDE-FG03-89ER25073
National Science FoundationCCR-8809615
Subject Keywords:multicoloring, consistently ordered matrices, iterative methods, concurrent computers
Issue or Number:1
Record Number:CaltechAUTHORS:HARsiamjmaa93
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12198
Deposited By: Archive Administrator
Deposited On:28 Oct 2008 22:51
Last Modified:08 Nov 2021 22:26

Repository Staff Only: item control page