Multicolor reordering of sparse matrices resulting from irregular grids

Publisher Website
Google Scholar
Abstract
Many iterative algorithms for the solution of large linear systems may be effectively vectorized if the diagonal of the matrix is surrounded by a large band of zeroes, whose width is called the zero stretch. In this paper, a multicolor numbering technique is suggested for maximizing the zero stretch of irregularly sparse matrices. The technique, which is a generalization of a known multicoloring algorithm for regularly sparse matrices, executes in linear time, and produces a zero stretch approximately equal to n /2σ, where 2σ is the number of colors used in the algorithm. For triangular meshes, it is shown that σ ≤ 3, and that it is possible to obtain σ = 2 by applying a simple backtracking scheme.

This publication has 14 references indexed in Scilit: