@TechReport{ it:2014-019,
author = {Magnus Grandin},
title = {Data Structures and Algorithms for High-Dimensional
Structured Adaptive Mesh Refinement},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Scientific Computing},
year = {2014},
number = {2014-019},
month = oct,
abstract = {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 $n^2$, the average runtime scaling in our
examples is no worse than $n \log n$.}
}