ftp ejde.math.txstate.edu A MULTILEVEL ADAPTIVE MESH GENERATION SCHEME USING KD-TREES

Abstract. We introduce a mesh refinement strategy for PDE based simu-lations that benefits from a multilevel decomposition. Using Harten’s MRA in terms of Schröder-Pander linear multiresolution analysis [20], we are able to bound discontinuities in R. This MRA is extended to Rn 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 Rn, while maintaining a minimal computational footprint. The nodes in the tree form an adaptive mesh whose density increases in the vicinity of a discontinuity. 1. Multilevel Representation There are several methods by which to locate fast transitions across multiple scales. Most commonly used are wavelets [6, 9, 22], and their lifted extensions [7, 15, 23, 24]. Also used are the adaptive stencil selection methods first proposed by Harten [13] and their subsequent extensions by Aràndiga, et al. [1] and Schröder-Pander, et. al. [20] to form a general multiresolution analysis. 1.1. Harten’s MRA. The following multiresolution analysis (MRA) holds for Ba-nach spaces [20]; however, for our exposition purposes, we restrict this introduction to finite sets of operators on Euclidean spaces. Let {D0,...,Dk,...,DL} be a set of linear operators such that Dk: V → V k, where V and V k are Euclidean spaces. The operators {Dk}Lk=0 have the following two properties: (1) Dk is onto for all k. (2) if Dkf = 0, then Dk−1f = 0 for any f ∈ V. Operators having these two properties are said to be nested. A restriction operator Rk−1k projects elements from a finite dimensional linear space V k to V k−1, and has the property that Rk−1k vk = Dk−1f for all vk, where vk = Dkf ∈ V k. Moreover, this restriction operator is well defined because Rk−1k is independent of the particular f ∈ V. Note that there is at least one element of f ∈ V such that Dkf = vk because Dk is onto. Therefore, supposing Dkf1