On the Theory of Discrete, Adaptive Space Filling Curves

Kurzfassung

We present a newly developed, self-contained theory for discrete space-filling curves (SFCs). Mesh partitioning according to such SFCs has been established as a fast and reliable technique, in particular when combined with frequent adaptive mesh refinement (AMR) and coarsening. SFCs map the elements of a uniform or adaptive mesh onto a finite index set, thus providing a linear order of the elements. AMR operations change this order only locally. In addition to practical use in HPC, investigating the properties of SFCs and developing new constructions are subjects of many theoretical studies. The definition for discrete SFCs is usually stated as an iteration step in a sequence that converges to an analytical SFC, or provided in the language of L-systems. Both of these definitions, however, are not ideally suited to represent the complexity of arbitrarily refined adaptive meshes. To address this issue, we provide a set of self-contained concepts and definitions, introducing new underlying structures such as refinement spaces and refinement rules. Discrete SFCs map these refinement spaces to an index set and satisfy certain locality properties. Our construction is independent of any particular geometric embedding. To demonstrate the usefulness of this approach, we present as first application the cross-product binary operation between SFCs that allows us to construct a new SFC for prism elements.