@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$.}
}