Multicolor Numbering of Irregular Triangular Meshes.

Abstract

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<or=3, and that it is possible to obtain o mega = 2 by applying a simple backtracking scheme.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1987
Accession Number
ADA186559

Entities

People

  • K. V. Ramarao
  • Rami G. Melhem

Organizations

  • University of Pittsburgh

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algebra
  • Algorithms
  • Applied Mathematics
  • Bandwidth
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Differential Equations
  • Equations
  • Linear Systems
  • Mathematical Programming
  • Mathematics
  • Numerical Analysis
  • Partial Differential Equations
  • Sparse Matrix
  • Supercomputers

Readers

  • Approximation Theory.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Systems Analysis and Design