Multicolor reordering of sparse matrices resulting from irregular grids

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&sgr;, where 2&sgr; is the number of colors used in the algorithm. For triangular meshes, it is shown that &sgr; ≤ 3, and that it is possible to obtain &sgr; = 2 by applying a simple backtracking scheme.

REFERENCES

• 1: ADAMS, L., AND ORTEGA, J. A multi-color SOR method for parallel computation, in Proceedings of the 1982 International Conference on Parallel Processing. Computer Society Press, 1982, pp. 53-56.
• 2: CHARTRAND, G., AND HARARY. F. Planar permutation graphs. Ann. Inst. H. Poincare, Sect. B 3 (1967), 433-438.
• 3: CHARTRAND, G., AND GELLER, D., AND I-IEDETRIEMI, S. Graphs with forbidden subgraphs. J. Comb. Theor. Set. B 10, (1971), 12-41.
• 4: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 5: GAREY, M., GRAHAM, R., JOHNSON, D., AND KNUTH, D. Complexity results for bandwidth minimization. SIAM J. App. Math. 34, 3 (1978), 477-495.
• 6: Norman E. Gibbs , William G. Poole, Jr. , Paul K. Stockmeyer, A Comparison of Several Bandwidth and Profile Reduction Algorithms, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.322-330, Dec. 1976 [doi>10.1145/355705.355707]
• 7: HAGEMAN, L., AND YOUNG. D. Applied Iterative Methods. Academic Press, New York, 1981.
• 8: KINCAID, D., OPPE, T., AND YOUNG, D. Vector computations for sparse linear systems. Tech. Rep. CNA-189, Center for Numerical Analysis, Univ. of Texas at Austin, 1984.
• 9: Kincho H. Law , Steven J. Fenives, A node-addition model for symbolic factorization, ACM Transactions on Mathematical Software (TOMS), v.12 n.1, p.37-50, March 1986 [doi>10.1145/5960.5963]
• 10: Joseph Y-T. Leung , Oliver Vornberger , James D. Witthoff, On some variants of the bandwidth minimization problem, SIAM Journal on Computing, v.13 n.3, p.650-667, August 1984 [doi>10.1137/0213040]
• 11: MANTEUFFEL, T. An incomplete factorization technique for positive definit linear systems. Math. Comput. 34, 150 (1980), 473-497.
• 12: L Marro, A linear time implementation of profile reduction algorithms for sparse matrices, SIAM Journal on Scientific and Statistical Computing, v.7 n.4, p.1212-1231, Oct. 1986 [doi>10.1137/0907082]
• 13: MEIJERINK, J., AND VAN DER VORST, S. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comput. 31,137 (1977), 148-162.
• 14: Rami Melhem, Determination of stripe structures for finite element matrics, SIAM Journal on Numerical Analysis, v.24 n.6, p.1419-1433, December 1, 1987 [doi>10.1137/0724091]
• 15: MELHEM, R. Toward efficient implementations of preconditioned conjugate gradient methods on vector supercomputers. Int. J. Supercomput. Appl. 1, 1 (1987), 70-98.
• 16: MELHEM, R. Iterative solution of sparse linear systems on systolic arrays. In Proceedings of the 1987 International Conference on Parallel Processing (Aug. 1987). The Pennsylvania State University Press, 1987, pp. 560-563.
• 17: MELHEM, R. Parallel solution of linear systems with striped sparse matrices. Parallel Comput. 6, 2 (1988), 165-184.
• 18: PAPADIMITRIOU, C. The NP-completeness of the bandwidth minimization problem. Computing 16 (1976), 263-270.
• 19: POOLS, E., AND ORTEOA, J. Multicolor ICCG methods for vector computers. Applied Math. Rep. RM-86-06, Univ. of Virginia, Charlottesville, 1986.
• 20: Richard Rosen, Matrix bandwidth minimization, Proceedings of the 1968 23rd ACM national conference, p.585-595, August 27-29, 1968 [doi>10.1145/800186.810622]
• 21: SAAD, Y., AND SCHULTZ, M. Parallel implementations of preconditioned conjugate gradient methods. Tech. Rep. YALEU/DCS/RR425, Dept. of Computer Science, Yale Univ., Oct. 1985.
• 22: TANG, D.T. A class of planar graphs containing hamilton circuits. IBM Res. Note, NC 503, 1965.
• 23: Jonathan S Turner, On the probable performance of Heuristics for bandwidth minimization, SIAM Journal on Computing, v.15 n.2, p.561-580, May 1986 [doi>10.1137/0215041]
• 24: Pamela Zave , Werner C. Rheinboldt, Design of an Adaptive, Parallel Finite-Element System, ACM Transactions on Mathematical Software (TOMS), v.5 n.1, p.1-17, March 1979 [doi>10.1145/355815.355816]
• 25: ZIENKIEWICZ, O. The Finite Element Method 3rd ed., McGraw-Hill, New York, 1979.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Iterative methods
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance, Theory

Keywords:
irregular grids, multicolor numbering, preconditioned conjugate gradient method, reordering sparse matrices, vectorization