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 http://resolver.caltech.edu/CaltechAUTHORS:HARsiamjmaa93
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:HARsiamjmaa93
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.
|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 ) are also greatly appreciated.|
|Subject Keywords:||multicoloring, consistently ordered matrices, iterative methods, concurrent computers|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||28 Oct 2008 22:51|
|Last Modified:||26 Dec 2012 10:28|
Repository Staff Only: item control page