Cost-effective Multiresolution schemes for Shock Computations

Harten's Multiresolution framework has provided a fruitful environment for the development of adaptive codes for hyperbolic PDEs. The so-called cost-effective alternative [4,8,21] seeks to achieve savings in the computational cost of the underlying numerical technique, but not in the overall memory requirements of the code. Since the data structure of the basic algorithm does not need to be modified, it provides a set of tools that can be easily implemented into existing codes and that can be very useful in order to speed up the numerical simulations involved in the testing process that is associated to the development of new numerical schemes.
In this paper we present two different applica…

Applications of Harten’s Framework for Multiresolution: From Conservation Laws to Image Compression

We briefly review Harten’s framework for multiresolution decompositions and describe two situations in which two different instances of the general framework have been used with success.

A Flux-Split Algorithm Applied to Relativistic Flows

The equations of RFD can be written as a hyperbolic system of conservation laws by choosing an appropriate vector of unknowns. We give an explicit formulation of the full spectral decomposition of the Jacobian matrices associated with the fluxes in each spatial direction, which is the essential ingredient of the techniques we propose in this paper. These techniques are based on the recently derived flux formula of Marquina, a new way to compute the numerical flux at a cell interface which leads to a conservative, upwind numerical scheme. Using the spectral decompositions in a fundamental way, we construct high order versions of the basic first-order scheme described by R. Donat and A. Marqu…

A Novel Multi-Scale Strategy for Multi-Parametric Optimization

The motion of a sailing yacht is the result of an equilibrium between the aerodynamic forces, generated by the sails, and the hydrodynamic forces, generated by the hull(s) and the appendages (such as the keels, the rudders, the foils, etc.), which may be fixed or movable and not only compensate the aero-forces, but are also used to drive the boat. In most of the design, the 3D shape of an appendage is the combination of a plan form (2D side shape) and a planar section(s) perpendicular to it, whose design depends on the function of the appendage. We often need a section which generates a certain quantity of lift to fulfill its function, but the lift comes with a penalty which is the drag. Th…

Multiresolution-based adaptive schemes for Hyperbolic Conservation Laws

Starting in the early nineties, wavelet and wavelet-like techniques have been successfully used to design adaptive schemes for the numerical solution of certain types of PDE. In this paper we review two representative examples of the development of such techniques for Hyperbolic Conservation Laws.

Equilibrium real gas computations using Marquina's scheme

Marquina's approximate Riemann solver for the compressible Euler equations for gas dynamics is generalized to an arbitrary equilibrium equation of state. Applications of this solver to some test problems in one and two space dimensions show the desired accuracy and robustness

The PCHIP subdivision scheme

In this paper we propose and analyze a nonlinear subdivision scheme based on the monotononicity-preserving third order Hermite-type interpolatory technique implemented in the PCHIP package in Matlab. We prove the convergence and the stability of the PCHIP nonlinear subdivision process by employing a novel technique based on the study of the generalized Jacobian of the first difference scheme. MTM2011-22741

Discrete multiresolution based on hermite interpolation: computing derivatives

Abstract Harten’s framework for multiresolution representation of data has been extended by Warming and Beam in [SIAM J. Sci. Comp. 22 (2000) 1269] to include Hermite interpolation. It needs the point-values of the derivative, which are usually unavailable, so they have to be approximated. In this work we show that the way in which the derivatives are approximated is crucial for the success of the method, and we present a new way to compute them that makes the scheme adequate for non-smooth data.

A fully adaptive multiresolution scheme for image processing

A nonlinear multiresolution scheme within Harten's framework [A. Harten, Discrete multiresolution analysis and generalized wavelets, J. Appl. Numer. Math. 12 (1993) 153-192; A. Harten, Multiresolution representation of data II, SIAM J. Numer. Anal. 33 (3) (1996) 1205-1256] is presented. It is based on a centered piecewise polynomial interpolation fully adapted to discontinuities. Compression properties of the multiresolution scheme are studied on various numerical experiments on images.

The Two-Jacobian Scheme for Systems of Conservation Laws

Proving convexity preserving properties of interpolatory subdivision schemes through reconstruction operators

We introduce a new approach towards proving convexity preserving properties for interpolatory subdivision schemes. Our approach is based on the relation between subdivision schemes and prediction operators within Harten's framework for multiresolution, and hinges on certain convexity properties of the reconstruction operator associated to prediction. Our results allow us to recover certain known results [10,8,1,7]. In addition, we are able to determine the necessary conditions for convexity preservation of the family of subdivision schemes based on the Hermite interpolation considered in [4].

A numerical treatment of wet/dry zones in well-balanced hybrid schemes for shallow water flow

The flux-limiting technology that leads to hybrid, high resolution shock capturing schemes for homogeneous conservation laws has been successfully adapted to the non-homogeneous case by the second and third authors. In dealing with balance laws, a key issue is that of well-balancing, which can be achieved in a rather systematic way by considering the 'homogeneous form' of the balance law.The application of these techniques to the shallow water system requires also an appropriate numerical treatment for the wetting/drying interfaces that appear initially or as a result of the flow evolution. In this paper we propose a numerical treatment for wet/dry interfaces that is specifically designed f…

Tensor product multiresolution analysis with error control for compact image representation

A class of multiresolution representations based on nonlinear prediction is studied in the multivariate context based on tensor product strategies. In contrast to standard linear wavelet transforms, these representations cannot be thought of as a change of basis, and the error induced by thresholding or quantizing the coefficients requires a different analysis. We propose specific error control algorithms which ensure a prescribed accuracy in various norms when performing such operations on the coefficients. These algorithms are compared with standard thresholding, for synthetic and real images.

A nonlinear Chaikin-based binary subdivision scheme

Abstract In this work we introduce and analyze a new nonlinear subdivision scheme based on a nonlinear blending between Chaikin’s subdivision rules and the linear 3-cell subdivision scheme. Our scheme seeks to improve the lack of convergence in the uniform metric of the nonlinear scheme proposed in Amat et al. (2012), where the authors define a cell-average version of the PPH subdivision scheme (Amat et al., 2006). The properties of the new scheme are analyzed and its performance is illustrated through numerical examples.

A High-Resolution Penalization Method for large Mach number Flows in the presence of Obstacles

International audience; A penalization method is applied to model the interaction of large Mach number compressible flows with obstacles. A supplementary term is added to the compressible Navier-Stokes system, seeking to simulate the effect of the Brinkman-penalization technique used in incompressible flow simulations including obstacles. We present a computational study comparing numerical results obtained with this method to theoretical results and to simulations with Fluent software. Our work indicates that this technique can be very promising in applications to complex flows.

Capturing Shock Reflections: An Improved Flux Formula

Godunov type schemes, based on exact or approximate solutions to the Riemann problem, have proven to be an excellent tool to compute approximate solutions to hyperbolic systems of conservation laws. However, there are many instances in which a particular scheme produces inappropriate results. In this paper we consider several situations in which Roe's scheme gives incorrect results (or blows up all together) and we propose an alternative flux formula that produces numerical approximations in which the pathological behavior is either eliminated or reduced to computationally acceptable levels.

Edge detection insensitive to changes of illumination in the image

In this paper we present new edge detection algorithms which are motivated by recent developments on edge-adapted reconstruction techniques [F. Arandiga, A. Cohen, R. Donat, N. Dyn, B. Matei, Approximation of piecewise smooth functions and images by edge-adapted (ENO-EA) nonlinear multiresolution techniques, Appl. Comput. Harmon. Anal. 24 (2) (2008) 225-250]. They are based on comparing local quantities rather than on filtering and thresholding. This comparison process is invariant under certain transformations that model light changes in the image, hence we obtain edge detection algorithms which are insensitive to changes in illumination.

Well-Balanced Adaptive Mesh Refinement for shallow water flows

Well-balanced shock capturing (WBSC) schemes constitute nowadays the state of the art in the numerical simulation of shallow water flows. They allow to accurately represent discontinuous behavior, known to occur due to the non-linear hyperbolic nature of the shallow water system, and, at the same time, numerically maintain stationary solutions. In situations of practical interest, these schemes often need to be combined with some kind of adaptivity, in order to speed up computing times. In this paper we discuss what ingredients need to be modified in a block-structured AMR technique in order to ensure that, when combined with a WBSC scheme, the so-called 'water at rest' stationary solutions…

A numerical study of postshock oscillations in slowly moving shock waves

Abstract Godunov-type methods and other shock capturing schemes can display pathological behavior in certain flow situations. This paper discusses the numerical anomaly associated to slowly moving shocks. We present a series of numerical experiments that illustrate the formation and propagation of this pathology, and allows us to establish some conclusions and question some previous conjectures for the source of the numerical noise. A simple diagnosis on an explicit Steger-Warming scheme shows that some intermediate states in the first time steps deviate from the true direction and contaminate the flow structure. A remedy is presented in the form of a new flux split method with an entropy i…

A secular equation for the Jacobian matrix of certain multispecies kinematic flow models

Weighted-Power p Nonlinear Subdivision Schemes

In this paper we present and analyze a generalization of the Powerp subdivision schemes proposed in [3,12]. The Weighted-Powerp schemes are based on a harmonic weighted version of the Power<emp average considered in [12], and their development is motivated by the desire to generalize the nonlinear analysis in [3,5] to interpolatory subdivision schemes with higher than second order accuracy.

On the reconstruction of discontinuous functions using multiquadric RBF–WENO local interpolation techniques

Abstract We discuss several approaches involving the reconstruction of discontinuous one-dimensional functions using parameter-dependent multiquadric radial basis function (MQ-RBF) local interpolants combined with weighted essentially non-oscillatory (WENO) techniques, both in the computation of the locally optimized shape parameter and in the combination of RBF interpolants. We examine the accuracy of the proposed reconstruction techniques in smooth regions and their ability to avoid Gibbs phenomena close to discontinuities. In this paper, we propose a true MQ-RBF–WENO method that does not revert to the classical polynomial WENO approximation near discontinuities, as opposed to what was pr…

Solving a model for 1-D, three-phase flow vertical equilibrium processes in a homogeneous porous medium by means of a Weighted Essentially Non Oscillatory numerical scheme

Mathematical models of multi-phase flow are useful in some engineering applications like enhanced oil recovery, filtration of pollutants into subsurface, etc. In this work, we derive a mathematical model for the motion of one-dimensional three-phase flow in a porous medium under the condition of vertical equilibrium, which can be viewed as an extension of some two-phase flow models described in the literature. Our model involves a system of two partial differential equations in the form of viscous conservation laws, whose solutions may contain very sharp transitions. We show that a high-order/high resolution Weighted Essentially Non Oscillatory scheme is an appropriate tool to discretize th…

Approximation of piecewise smooth functions and images by edge-adapted (ENO-EA) nonlinear multiresolution techniques

Abstract This paper introduces and analyzes new approximation procedures for bivariate functions. These procedures are based on an edge-adapted nonlinear reconstruction technique which is an intrinsically two-dimensional extension of the essentially non-oscillatory and subcell resolution techniques introduced in the one-dimensional setting by Harten and Osher. Edge-adapted reconstructions are tailored to piecewise smooth functions with geometrically smooth edge discontinuities, and are therefore attractive for applications such as image compression and shock computations. The local approximation order is investigated both in L p and in the Hausdorff distance between graphs. In particular, i…

On specific stability bounds for linear multiresolution schemes based on piecewise polynomial Lagrange interpolation

Abstract The Deslauriers–Dubuc symmetric interpolation process can be considered as an interpolatory prediction scheme within Harten's framework. In this paper we express the Deslauriers–Dubuc prediction operator as a combination of either second order or first order differences. Through a detailed analysis of certain contractivity properties, we arrive to specific l ∞ -stability bounds for the multiresolution transform. A variety of tests indicate that these l ∞ bounds are closer to numerical estimates than those obtained with other approaches.

On the hyperbolicity of certain models of polydisperse sedimentation

The sedimentation of a polydisperse suspension of small spherical particles dispersed in a viscous fluid, where particles belong to N species differing in size, can be described by a strongly coupled system of N scalar, nonlinear first-order conservation laws for the evolution of the volume fractions. The hyperbolicity of this system is a property of theoretical importance because it limits the range of validity of the model and is of practical interest for the implementation of numerical methods. The present work, which extends the results of R. Burger, R. Donat, P. Mulet, and C.A. Vega (SIAM Journal on Applied Mathematics 2010; 70:2186–2213), is focused on the fluxes corresponding to the …

Computing Strong Shocks in Ultrarelativistic Flows: A Robust Alternative

In recent years, shock capturing methods have started to be used in numerical simulations in Relativistic Fluid Dynamics (RFD). These techniques lead to explicit numerical codes that are able to successfully simulate the extreme conditions of the ultrarelativistic regime. After [2], an explicit, ready-to-use description of the full spectral decomposition of the Jacobian matrices of the RFD system is available, and this allows us to implement Marquina’s scheme [3] in RFD. The scheme is seen to maintain the good behavior shown in [3] with respect to certain numerical pathologies.

Some Theoretical Results About Stability for IMEX Schemes Applied to Hyperbolic Equations with Stiff Reaction Terms

In this work we are concerned with certain numerical difficulties associated to the use of high order Implicit–Explicit Runge–Kutta (IMEX-RK) schemes in a direct discretization of balance laws with stiff source terms. We consider a simple model problem, introduced by LeVeque and Yee in [J. Comput. Phys 86 (1990)], as the basic test case to explore the ability of IMEX-RK schemes to produce and maintain non-oscillatory reaction fronts.

On stability issues for IMEX schemes applied to 1D scalar hyperbolic equations with stiff reaction terms

The application of a Method of Lines to a hyperbolic PDE with source terms gives rise to a system of ODEs containing terms that may have very different stiffness properties. In this case, Implicit-Explicit Runge-Kutta (IMEX-RK) schemes are particularly useful as high order time integrators because they allow an explicit handling of the convective terms, which can be discretized using the highly developed shock capturing technology, together with an implicit treatment of the source terms, necessary for stability reasons. Motivated by the structure of the source term in a model problem introduced by LeVeque and Yee in [J. Comput. Phys. 86 (1990)], in this paper we study the preservation of ce…

Data Compression with ENO Schemes: A Case Study

Abstract We study the compresion properties of ENO-type nonlinear multiresolution transformations on digital images. Specific error control algorithms are used to ensure a prescribed accuracy. The numerical results reveal that these methods strongly outperform the more classical wavelet decompositions in the case of piecewise smooth geometric images.

Cell-Average Multiwavelets Based on Hermite Interpolation

Multiresolution based on weighted averages of the hat function I: Linear reconstruction techniques

In this paper we analyze a particular example of the general framework developed in [A. Harten, {\it SIAM J. Numer. Anal}., 33 (1996) pp. 1205--1256], the case in which the discretization operator is obtained by taking local averages with respect to the hat function. We consider a class of reconstruction procedures which are appropriate for this multiresolution setting and describe the associated prediction operators that allow us to climb up the ladder from coarse to finer levels of resolution. In Part I we use data-independent (linear) reconstruction techniques as our approximation tool. We show how to obtain multiresolution transforms in bounded domains and analyze their stability with r…

On the implementation of weno schemes for a class of polydisperse sedimentation models

The sedimentation of a polydisperse suspension of small rigid spheres of the same density, but which belong to a finite number of species (size classes), can be described by a spatially one-dimensional system of first-order, nonlinear, strongly coupled conservation laws. The unknowns are the volume fractions (concentrations) of each species as functions of depth and time. Typical solutions, e.g. for batch settling in a column, include discontinuities (kinematic shocks) separating areas of different composition. The accurate numerical approximation of these solutions is a challenge since closed-form eigenvalues and eigenvectors of the flux Jacobian are usually not available, and the characte…

Gradient design for liquid chromatography using multi-scale optimization.

Abstract In reversed phase-liquid chromatography, the usual solution to the “general elution problem” is the application of gradient elution with programmed changes of organic solvent (or other properties). A correct quantification of chromatographic peaks in liquid chromatography requires well resolved signals in a proper analysis time. When the complexity of the sample is high, the gradient program should be accommodated to the local resolution needs of each analyte. This makes the optimization of such situations rather troublesome, since enhancing the resolution for a given analyte may imply a collateral worsening of the resolution of other analytes. The aim of this work is to design mul…

The Spanish Society for Applied Mathematics and ICIAM 2019 – Valencia

Numerical Experiments with Multilevel Schemes for Conservation Laws

Main steps of a point-value multilevel algorithm are presented and numerical results for a two dimensional test case of gas dynamics are discussed in terms of quality and efficiency.

Fine-Mesh Numerical Simulations for 2D Riemann Problems with a Multilevel Scheme

The numerical simulation of physical problems modeled by systems of conservation laws can be difficult due to the occurrence of discontinuities and other non-smooth features in the solution.

Flux-gradient and source-term balancing for certain high resolution shock-capturing schemes

Abstract We present an extension of Marquina’s flux formula, as introduced in Fedkiw et al. [Fedkiw RP, Merriman B, Donat R, Osher S. The penultimate scheme for systems of conservation laws: finite difference ENO with Marquina’s flux splitting. In: Hafez M, editor. Progress in numerical solutions of partial differential equations, Arcachon, France; July 1998], for the shallow water system. We show that the use of two different Jacobians at cell interfaces prevents the scheme from satisfying the exact C -property [Bermudez A, Vazquez ME. Upwind methods for hyperbolic conservation laws with source terms. Comput Fluids 1994;23(8):1049–71] while the approximate C -property is satisfied for high…

Error bounds for a convexity-preserving interpolation and its limit function

AbstractError bounds between a nonlinear interpolation and the limit function of its associated subdivision scheme are estimated. The bounds can be evaluated without recursive subdivision. We show that this interpolation is convexity preserving, as its associated subdivision scheme. Finally, some numerical experiments are presented.

High-accuracy approximation of piecewise smooth functions using the Truncation and Encode approach

Abstract In the present work, we analyze a technique designed by Geraci et al. in [1,11] named the Truncate and Encode (TE) strategy. It was presented as a non-intrusive method for steady and non-steady Partial Differential Equations (PDEs) in Uncertainty Quantification (UQ), and as a weakly intrusive method in the unsteady case. We analyze the TE algorithm applied to the approximation of functions, and in particular its performance for piecewise smooth functions. We carry out some numerical experiments, comparing the performance of the algorithm when using different linear and non-linear interpolation techniques and provide some recommendations that we find useful in order to achieve a hig…