Recursive mesh refinement on hypercubes

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

Research output: Contribution to journalArticlepeer-review


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
Issue number2
StatePublished - Jun 1989
Externally publishedYes


  • AMS classifications: 65N50, 68P99

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Computational Mathematics
  • Applied Mathematics


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

Cite this