Multicolor Numbering of Irregular Triangular Meshes

摘要

Many iterative algorithms for the solution of large linear systems may be effectively vectorized only if the diagonal of the matrix is surrounded by a large band of zeroes, which 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 generalization of a known algorithm for regularly sparse matrices, executes in linear time, and produces a zero stretch approximately equal to n/2sigma, where sigma is the number of colors used in the algorithm. For triangular meshes, it is shown that sigma