Recursive mesh refinement on hypercubes

W. D. Gropp, I. C.F. Ipsen

Research output: Contribution to journalArticlepeer-review

Abstract

Adaptive methods for PDEs can be viewed as a graph problem. An efficient parallel implementation of adaptive PDE methods then requires distributing the nodes of the associated graph uniformly across the processors so that the resulting cost of communication between processors is low. We solve this problem in two phases: labeling of graph nodes and subsequent mapping of these labels onto processors. We describe a new form of Gray-code which we call an interleaved Gray-code that allows easy labeling of graph nodes when the maximal level of refinement is unknown, allows easy determination of nearby nodes in the graph, is completely deterministic, and often (in a well-defined sense) distributes the graph uniformly across a hypercube. The theoretical results are supported by computational experiments on the Connection Machine.

Original languageEnglish (US)
Pages (from-to)186-211
Number of pages26
JournalBIT
Volume29
Issue number2
DOIs
StatePublished - Jun 1 1989
Externally publishedYes

Keywords

  • AMS classifications: 65N50, 68P99

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Recursive mesh refinement on hypercubes'. Together they form a unique fingerprint.

Cite this