A multilevel adaptive mesh generation scheme using Kd-trees

Abstract

We introduce a mesh refinement strategy for PDE based simulations that benefits from a multilevel decomposition. Using Harten's MRA in terms of Schroder-Pander linear multiresolution analysis [20], we are able to bound discontinuities in $mathbb{R}$. This MRA is extended to $mathbb{R}^n$ in terms of n-orthogonal linear transforms and utilized to identify cells that contain a codimension-one discontinuity. These refinement cells become leaf nodes in a balanced Kd-tree such that a local dyadic MRA is produced in $mathbb{R}^n$, while maintaining a minimal computational footprint. The nodes in the tree form an adaptive mesh whose density increases in the vicinity of a discontinuity.

Keywords

• Adaptive grid refinement
• Wavelet refined mesh
• quadtree grids
• multilevel decomposition
• codimension-one discontinuities