Recursive mesh refinement on hypercubes

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.