Recursive Mesh Refinement on Hypercubes

Abstract

Adaptive methods for partial differential equations can be viewed as a graph problem. Parallel methods must distribute this graph efficiently among the processors. In doing this, the cost of communication between processors and the structure of the graph must be considered. The author divides this problem into two phases: labeling of graph nodes and subsequent mapping of these labels onto processors. He describes a new form of Gray-code which we calls an interleaved Gray-code that allows easy labeling of graph nodes even 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 efficiently across a hypercube. The theoretical results are supported by computational experiments on the Connection Machine.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1988
Accession Number
ADA198695

Entities

People

  • I. C. Ipsen
  • W. D. Gropp

Organizations

  • Yale University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Differential Equations
  • Equations
  • Grids
  • Hierarchies
  • Military Research
  • Parallel Processors
  • Partial Differential Equations
  • Plastic Explosives
  • Three Dimensional
  • Two Dimensional
  • Workload

Fields of Study

  • Computer science

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.