Search

We present the derivation, implementation, and analysis of a multiresolution adaptive grid framework for numerical simulations on octree-based three-dimensional block-structured collocated grids with distributed computational architectures. Our approach provides a consistent handling of nonlifted and lifted interpolating wavelets of arbitrary order demonstrated using second-, fourth-, and sixth-order wavelets, combined with standard finite-difference-based discretization op-erators. We first validate that the wavelet family used provides strict and explicit error control when coarsening the grid, and show that lifting wavelets increase the grid compression rate while conserving discrete moments across levels. Further, we demonstrate that high-order PDE discretization schemes combined with sufficiently high-order wavelets retain the expected convergence order even at resolution jumps. We then simulate the advection of a scalar to analyze convergence for the temporal evolution of a PDE. The results shows that our wavelet-based refinement criterion is successful at controlling the overall error while the coarsening criterion is effective at retaining the relevant information on a compressed grid. Our software exploits a block-structured grid data structure for efficient multilevel operations, combined with a parallelization strategy that relies on a one-sided MPI-RMA communication approach with active post-start-complete-wait synchronization. Using performance tests up to 16,384 cores, we demonstrate that this leads to a highly scalable performance. The associated code is available under a BSD-3 license at https://github.com/vanreeslab/murphy. [ABSTRACT FROM AUTHOR]

We present a detailed comparison between two adaptive numerical approaches to solve partial differential equations, adaptive multiresolution (MR) and adaptive mesh refinement (AMR). Both discretizations are based on finite volumes in space with second order shock-capturing and explicit time integration either with or without local time stepping. The two methods are benchmarked for the compressible Euler equations in Cartesian geometry. As test cases a twodimensional Riemann problem, Lax-Liu #6, and a three-dimensional ellipsoidally expanding shock wave have been chosen. We compare and assess their computational efficiency in terms of CPU time and memory requirements. We evaluate the accuracy by comparing the results of the adaptive computations with those obtained with the corresponding FV scheme using a regular fine mesh. We find that both approaches yield similar trends for CPU time compression for increasing number of refinement levels. MR exhibits more efficient memory compression than AMR and shows slightly enhanced convergence; however, a larger absolute overhead is measured for the tested codes. [ABSTRACT FROM AUTHOR]

We present a computational method of coupling average interpolating wavelets with high-order finite volume schemes and its implementation on heterogeneous computer architectures for the simulation of multiphase compressible flows. The method is implemented to take advantage of the parallel computing capabilities of emerging heterogeneous multicore/multi-GPU architectures. A highly efficient parallel implementation is achieved by introducing the concept of wavelet blocks, exploiting the task-based parallelism for CPU cores, and by managing asynchronously all array of GPUs by means of OpenCL. We investigate the comparative accuracy of the GPU and CPU based simulations and analyze their discrepancy for two-dimensional simulations of shock-bubble interaction and Richtmeyer-Meshkov instability. The results indicate that the accuracy of the GPU/CPU heterogeneous solver is competitive with the one that uses exclusively the CPU cores. We report the performance improvements by employing up to 12 cores and 6 GPUs compared to the single-core execution. For the simulation of the shock-bubble interaction at Mach 3 with two million grid points, we observe a 100-fold speedup for the heterogeneous part and an overall speedup of 34. [ABSTRACT FROM AUTHOR]

We present an efficient method for computing the discrete orthonormal Stockwell transform (DOST). The Stockwell transform (ST) is a time-frequency decomposition transform that is showing great promise in various applications, but is limited because its computation is infeasible for most applications. The DOST is a nonredundant version of the ST, solving many of the memory and computational issues. However, computing the DOST of a signal of length N using basis vectors is still O(N²). The computational complexity of our method is O(N logN), putting it in the same category as the FFT. The algorithm is based on a simple decomposition of the DOST matrix. We also explore the way to gain conjugate symmetry for the DOST and propose a variation of the parameters that exhibits symmetry, akin to the conjugate symmetry of the FFT of a real-valued signal. Our fast method works equally well on this symmetric DOST. In this paper, we provide a mathematical proof of our results and derive that the computational complexity of our algorithm is O(N logN). Timing tests also confirm that the new method is orders-of-magnitude faster than the brute-force DOST, and they demonstrate that our fast DOST is indeed O(N logN) in complexity. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel multiresolution adaptive mesh refinement algorithm for solving initial-boundary value problems (IBVP) for evolution PDEs. The proposed algorithm dynamically adapts the grid to any existing or emerging irregularities in the solution, by refining the grid only at those places where the solution exhibits sharp features. The main advantage of the proposed grid adaptation method is that it results in a grid with a fewer number of nodes when compared to adaptive grids generated by existing multiresolution-based mesh refinement techniques. Several examples show the robustness and stability of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Hybrid or multiphysics algorithms provide an efficient computational tool for combining micro- and macroscale descriptions of physical phenomena. Their use becomes imperative when microscale descriptions are too computationally expensive to be conducted in the whole domain, while macroscale descriptions fail in a small portion of the computation domain. We present a hybrid algorithm to model a general class of reaction-diffusion processes in granular porous media, which includes mixing-induced mineral precipitation on, or dissolution of, the porous matrix. These processes cannot be accurately described using continuum (Darcy-scale) models. The pore-scale/Darcy-scale hybrid is constructed by coupling solutions of the reaction-diffusion equations (RDE) at the pore scale with continuum Darcy-level solutions of the averaged RDEs. The resulting hybrid formulation is solved numerically by employing a multiresolution meshless discretization based on the smoothed particle hydrodynamics method. This ensures seamless noniterative coupling of the two components of the hybrid model. Computational examples illustrate the accuracy and efficiency of the hybrid algorithm. [ABSTRACT FROM AUTHOR]

The Haar wavelets can represent exactly any piecewise constant function. The motivation for the present development is Alpert's family of compact orthogonal multiwavelets that can represent exactly any piecewise polynomial function. We choose to derive the algorithm in the style and notation of Harten's multiresolution analysis as extended to multiwavelets by the authors. We begin with a description of the nested grid hierarchy. Next comes the decomposition, which is the heart of the algorithm, and finally the reconstruction. The basis functions (which are nonfractal) retain the spatial compactness of the Haar basis functions, which enhances the algorithm application to nonperiodic and piecewise continuous data. [ABSTRACT FROM AUTHOR]

We generalize Harten's interpolatory multiresolution representation to include Her- mite interpolation. Compact Hermite interpolation with optimal order accuracy is used in both the decomposition and reconstruction algorithm. The resulting multiple basis functions (biorthogonal multiwavelets) are symmetric or skew-symmetric, compact, and analytic. Harten's approach has several advantages: the multiresolution scheme is inherently discrete, nonperiodic boundary conditions are easy to implement, and the representation can be extended to nonuniform grids in bounded do- mains. We demonstrate the compression features of the new multiple basis functions by application to several examples. [ABSTRACT FROM AUTHOR]

We present the details of a multiresolution method we proposed at the Taormina Wavelet Conference in 1993 (see ‘L-spline wavelets’ in Wavelets: Theory, Algorithms, and Applications, C. Chui, L. Montefusco, and L. Puccio, eds., Academic Press, New York, pp. 197–212) which is suitable for fitting functions or data on the sphere. The method is based on tensor products of polynomial splines and trigonometric splines and can be adapted to produce surfaces that are either tangent plane continuous or almost tangent plane continuous. The result is a convenient compression algorithm for dealing with large amounts of data on the sphere. We give full details of a computer implementation that is highly efficient with respect to both storage and computational cost. We also demonstrate the performance of the method on several test examples. [ABSTRACT FROM AUTHOR]

Classic wavelet methods were developed in the Euclidean spaces for multiscale representation and analysis of regularly sampled signals (time series) and images. This paper introduces a method of representing scattered spherical data by multiscale spherical wavelets. The method extends the recent pioneering work of Narcowich and Ward [Appl. Comput. Harmon. Anal., 3 (1996), pp. 324­336] by employing multiscale rather than single-scale spherical basis functions and by introducing a bottom-up procedure for network design and bandwidth selection. Decomposition and reconstruction algorithms are proposed for efficient computation. An analytical investigation confirms the localization property of the resulting spherical wavelets. The proposed method is illustrated by numerical examples. It is also employed to analyze and compress a real-data set consisting of the surface air temperatures observed on a global network of weather stations. [ABSTRACT FROM AUTHOR]

In this paper we describe and analyze a class of nonlinear multiresolution schemes for the multiresolution setting which corresponds to discretization by local averages with respect to the hat function. These schemes are based on the essentially-non-oscillatory (ENO) interpolatory procedure described in [A. Harten, B. Engquist, S. Osher, and S. Chakravarthy, J. Comput. Phys., 71 (1987), pp. 231–302]. We show that by allowing the approximation to fit the local nature of the data, one can improve the compression capabilities of the multiresolution algorithms. The question of stability for nonlinear (data-dependent) reconstruction techniques is also addressed. [ABSTRACT FROM AUTHOR]