Technical Report 2014-019

Data Structures and Algorithms for High-Dimensional Structured Adaptive Mesh Refinement

Magnus Grandin

October 2014

Spatial discretization of high-dimensional partial differential equations requires data representations that are of low overhead in terms of memory and complexity. Uniform discretization of computational domains quickly grows out of reach due to an exponential increase in problem size with dimensionality. Even with spatial adaptivity, the number of mesh data points can be unnecesarily large if care is not taken as to where refinement is done. We propose an adaptive scheme that generates the mesh by recursive bisection, allowing mesh blocks to be arbitrarily anisotropic to allow for fine structures in some directions without over-refining in those directions that suffice with less refinement. We describe in detail how the mesh blocks are organized in a kd-tree and the algorithms that update the mesh as is necessary for preserved accuracy in the solution. Algorithms for refinement, coarsening and 2:1 balancing of a mesh hierarchy are derived, and we describe how information is retrieved from the tree structure by means of binary search. To show the capabilities of our framework, we present results showing examples of generated meshes and evaluate the algorithmic scalability on a suite of test problems. In summary, we conclude that although the worst-case complexity of sorting the nodes and building the node map index is n2, the average runtime scaling in our examples is no worse than n log n.

Available as PDF (2.3 MB, no cover)

Download BibTeX entry.