Data structures and algorithms for high-dimensional structured adaptive mesh refinement. (April 2015)

• Record Type: Journal Article
• Authors: Grandin, Magnus
• Is Part Of: Advances in engineering software. Volume 82(2015)
• Page Start: 75
• Page End: 86
• Publication Date: 2015-04
• Subjects: Structured adaptive mesh refinement -- Anisotropic mesh -- High-dimensional -- Hierarchical data structure -- kd-tree -- Morton order -- 2:1 balancing; Computer-aided engineering -- Periodicals; Engineering -- Computer programs -- Periodicals; Engineering -- Software -- Periodicals; Periodicals; 620.0028553
• DOI: 10.1016/j.advengsoft.2014.12.001
• Languages: English
• ISSNs: 0965-9978

Abstract

Highlights: Structured anisotropic refinement of high-dimensional domains. Recursive bisection of hyperrectangular mesh elements. Linearized kd-tree for storage of the hierarchical mesh decomposition. Examples and scalability studies of meshes in up to 6 dimensions. Complete scheme scales better than n log n, although worst case is O ( n 2 ) . 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 unnecessarily large if care is not taken as to where refinement is done. This paper proposes 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. Within this framework, the mesh blocks are organized in a linear kd-tree with an explicit node index map corresponding to the hierarchical splitting of internal nodes. Algorithms for refinement, coarsening and 2:1 balancing of a mesh hierarchy are derived. To demonstrate the capabilities of the framework, examples of generated meshes are presented and the algorithmic scalability is evaluated on a suite of test problems. In conclusion, although the worst-case complexity of sorting the nodes and building the node map index is n 2, the average runtime scaling in the studied examples is no worse than n log n .