A C0 interior penalty discontinuous Galerkin method for fourth‐order total variation flow. I: Derivation of the method and numerical results

We consider the numerical solution of a fourth‐order total variation flow problem representing surface relaxation below the roughening temperature. Based on a regularization and scaling of the nonlinear fourth‐order parabolic equation, we perform an implicit discretization in time and a C⁰ Interior Penalty Discontinuous Galerkin (C⁰IPDG) discretization in space. The C⁰IPDG approximation can be derived from a mixed formulation involving numerical flux functions where an appropriate choice of the flux functions allows to eliminate the discrete dual variable. The fully discrete problem can be interpreted as a parameter dependent nonlinear system with the discrete time as a parameter. It is solved by a predictor corrector continuation strategy featuring an adaptive choice of the time step sizes. A documentation of numerical results is provided illustrating the performance of the C⁰IPDG method and the predictor corrector continuation strategy. The existence and uniqueness of a solution of the C⁰IPDG method will be shown in the second part of this paper.     

A relaxation scheme for the approximation of the pressureless Euler equations

In the present work, we consider the numerical approximation of pressureless gas dynamics in one and two spatial dimensions. Two particular phenomena are of special interest for us, namely δ‐shocks and vacuum states. A relaxation scheme is developed which reliably captures these phenomena. In one space dimension, we prove the validity of several stability criteria, i.e., we show that a maximum principle as well as the TVD property for the discrete velocity component and the validity of discrete entropy inequalities hold. Several numerical tests considering not only the developed first‐order scheme but also a classical MUSCL‐type second‐order extension confirm the reliability and robustness of the relaxation approach. The article extends previous results on the topic: the stability conditions for relaxation methods for the pressureless case are refined, useful properties for the time stepping procedure are established, and two‐dimensional numerical results are presented. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Relaxation approximation to bed-load sediment transport

In this work we propose and apply a numerical method based on finite volume relaxation approximation for computing the bed-load sediment transport in shallow water flows, in one and two space dimensions. The water flow is modeled by the well-known nonlinear shallow water equations which are coupled with a bed updating equation. Using a relaxation approximation, the nonlinear set of equations (and for two different formulations) is transformed to a semilinear diagonalizable problem with linear characteristic variables. A second order MUSCL-TVD method is used for the advection stage while an implicit–explicit Runge–Kutta scheme solves the relaxation stage. The main advantages of this approach are that neither Riemann problem solvers nor nonlinear iterations are required during the solution process. For the two different formulations, the applicability and effectiveness of the presented scheme is verified by comparing numerical results obtained for several benchmark test problems.     

Relaxation WENO schemes for multidimensional hyperbolic systems of conservation laws

We present a class of high‐order weighted essentially nonoscillatory (WENO) reconstructions based on relaxation approximation of hyperbolic systems of conservation laws. The main advantage of combining the WENO schemes with relaxation approximation is the fact that the presented schemes avoid solution of the Riemann problems due to the relaxation approach and high‐resolution is obtained by applying the WENO approach. The emphasis is on a fifth‐order scheme and its performance for solving a wide class of systems of conservation laws. To show the effectiveness of these methods, we present numerical results for different test problems on multidimensional hyperbolic systems of conservation laws. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Higher order numerical methods for solving fractional differential equations

In this paper we introduce higher order numerical methods for solving fractional differential equations. We use two approaches to this problem. The first approach is based on a direct discretisation of the fractional differential operator: we obtain a numerical method for solving a linear fractional differential equation with order 0<α<1. The order of convergence of the numerical method is O(h ^3?α ). Our second approach is based on discretisation of the integral form of the fractional differential equation and we obtain a fractional Adams-type method for a nonlinear fractional differential equation of any order α>0. The order of convergence of the numerical method is O(h ³) for α≥1 and O(h ^1+2α ) for 0<α≤1 for sufficiently smooth solutions. Numerical examples are given to show that the numerical results are consistent with the theoretical results.     

Convergence of relaxation schemes for hyperbolic conservation laws with stiff source terms

We focus in this study on the convergence of a class of relaxation numerical schemes for hyperbolic scalar conservation laws including stiff source terms. Following Jin and Xin, we use as approximation of the scalar conservation law, a semi-linear hyperbolic system with a second stiff source term. This allows us to avoid the use of a Riemann solver in the construction of the numerical schemes. The convergence of the approximate solution toward a weak solution is established in the cases of first and second order accurate MUSCL relaxed methods.

     

Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables

We present a hierarchy of semidefinite programming (SDP) relaxations for solving the concave cost transportation problem (CCTP), which is known to be NP-hard, with p suppliers and q demanders. In particular, we study cases in which the cost function is quadratic or square-root concave. The key idea of our relaxation methods is in the change of variables to CCTPs, and due to this, we can construct SDP relaxations whose matrix variables are of size O((min {p, q}) ^ω ) in the relaxation order ω. The sequence of optimal values of SDP relaxations converges to the global minimum of the CCTP as the relaxation order ω goes to infinity. Furthermore, the size of the matrix variables can be reduced to O((min {p, q}) ^ω-1 ), ω ≥  2 by using Reznick’s theorem. Numerical experiments were conducted to assess the performance of the relaxation methods.     

A roe-type Riemann solver for hyperbolic systems with relaxation based on time-dependent wave decomposition

Summary. The paper is devoted to the construction of a higher order Roe-type numerical scheme for the solution of hyperbolic systems with relaxation source terms. It is important for applications that the numerical scheme handles both stiff and non stiff source terms with the same accuracy and computational cost and that the relaxation variables are computed accurately in the stiff case. The method is based on the solution of a Riemann problem for a linear system with constant coefficients: a study of the behavior of the solutions of both the nonlinear and linearized problems as the relaxation time tends to zero enables to choose a convenient linearization such that the numerical scheme is consistent with both the hyperbolic system when the source terms are absent and the correct relaxation system when the relaxation time tends to zero. The method is applied to the study of the propagation of sound waves in a two-phase medium. The comparison between our numerical scheme, usual fractional step methods, and numerical simulation of the relaxation system shows the necessity of using the solutions of a fully coupled hyperbolic system with relaxation terms as the basis of a numerical scheme to obtain accurate solutions regardless of the stiffness. Received October 7, 1994 / Revised version received September 27, 1995     

The relaxation schemes for systems of conservation laws in arbitrary space dimensions

We present a class of numerical schemes (called the relaxation schemes) for systems of conservation laws in several space dimensions. The idea is to use a local relaxation approximation. We construct a linear hyperbolic system with a stiff lower order term that approximates the original system with a small dissipative correction. The new system can be solved by underresolved stable numerical discretizations without using either Riemann solvers spatially or a nonlinear system of algebraic equations solvers temporally. Numerical results for 1-D and 2-D problems are presented. The second-order schemes are shown to be total variation diminishing (TVD) in the zero relaxation limit for scalar equations. ©1995 John Wiley & Sons, Inc.     

A system of conservation laws including a stiff relaxation term; the 2D case

We analyze a system of conservation laws in two space dimensions with a stiff relaxation term. A semi-implicit finite difference method approximating the system is studied and an error bound of order measured inL ¹ is derived. This error bound is independent of the relaxation time > 0. Furthermore, it is proved that the solutions of the system converge towards the solution of an equilibrium model as the relaxation time tends to zero, and that the rate of convergence measured inL ¹ is of order . Finally, we present some numerical illustrations.This research has been supported by the Norwegian Research Council (NFR), program no. STP 110673/420, at the Department of Applied Mathematics, SINTEF, Oslo, Norway     

Une nouvelle méthode de relaxation pour les équations de Navier–Stokes compressibles

We consider the compressible Navier–Stokes equations for gas flows endowed with general pressure and temperature laws as long as they are compatible with the existence of an entropy and Gibbs relations. We extend the relaxation method introduced for the Euler equations by Coquel and Perthame. Keeping the same “sub-characteristic” conditions for the hyperbolic fluxes and using a consistent splitting of the diffusive fluxes based on a global temperature, we prove the stability of the relaxation system via the sign of the production of a suitable entropy. A first order asymptotic analysis around equilibrium states confirms the stability result. Finally, we present a numerical implementation of the method. To cite this article: E. Bongiovanni et al., C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

High‐order numerical methods for one‐dimensional parabolic singularly perturbed problems with regular layers

In this work we construct and analyze some finite difference schemes used to solve a class of time‐dependent one‐dimensional convection‐diffusion problems, which present only regular layers in their solution. We use the implicit Euler or the Crank‐Nicolson method to discretize the time variable and a HODIE finite difference scheme, defined on a piecewise uniform Shishkin mesh, to discretize the spatial variable. In both cases we prove that the numerical method is uniformly convergent with respect to the diffusion parameter, having order near two in space and order one or 3/2, depending on the method used, in time. We show some numerical examples which illustrate the theoretical results, in the case of using the Euler implicit method, and give better numerical behaviour than that predicted theoretically, showing order two in time and order N^?2log²N in space, if the Crank‐Nicolson scheme is used to discretize the time variable. Finally, we construct a numerical algorithm by combining a third order A‐stable SDIRK with two stages and a third‐order HODIE difference scheme, showing its uniformly convergent behavior, reaching order three, up to a logarithmic factor. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

Continuous-time accelerated block successive overrelaxation methods for time-dependent Stokes equations

In order to solve the time-dependent Stokes equation, we follow the “Method of Lines” to obtain structured linear constant-coefficient differential–algebraic equations (DAEs). By taking advantage of the structure, we propose a class of waveform relaxation methods, called continuous-time accelerated block SOR (CABSOR) methods, for solving the obtained DAEs. The new methods are theoretically analyzed. The theory is applied to a two-dimensional time-dependent Stokes equation and verified by numerical experiments.     

Second Order Nonlinear Evolution Inclusions Ⅰ： Existence and Relaxation Results

This is the first part of a work on second order nonlinear, nonmonotone evolution inclusions defined in the framework of an evolution triple of spaces and with a multivalued nonlinearity depending on both x（t） and x（t）. In this first part we prove existence and relaxation theorems. We consider the case of an usc, convex valued nonlinearity and we show that for this problem the solution set is nonempty and compact in C^1 （T, H）. Also we examine the Isc, nonconvex case and again we prove the existence of solutions. In addition we establish the existence of extremal solutions and by strengthening our hypotheses, we show that the extremal solutions are dense in C^1 （T, H） to the solutions of the original convex problem （strong relaxation）. An example of a nonlinear hyperbolic optimal control problem is also discussed.     

An iterative scheme for variational inequalities

In this paper we introduce and study a general iterative scheme for the numerical solution of finite dimensional variational inequalities. This iterative scheme not only contains, as special cases the projection, linear approximation and relaxation methods but also induces new algorithms. Then, we show that under appropriate assumptions the proposed iterative scheme converges by establishing contraction estimates involving a sequence of norms in Eⁿ induced by symmetric positive definite matrices G_m. Thus, in contrast to the above mentioned methods, this technique allows the possibility of adjusting the norm at each step of the algorithm. This flexibility will generally yield convergence under weaker assumptions.     

Modified tangential frequency filtering decomposition and its fourier analysis

In this paper, a modified tangential frequency filtering decomposition (MTFFD) preconditioner is proposed. The optimal order of the modification and the optimal relaxation parameter is determined by Fourier analysis. With the choice of optimal order of modification, the Fourier results show that the condition number of the preconditioned matrix is O(h^-\frac23){{\mathcal O}(h^{-\frac{2}{3}})}, and the spectrum distribution of the preconditioned matrix can be predicted by the Fourier results. The performance of MTFFD preconditioner is compared with tangential frequency filtering (TFFD) preconditioner on a variety of large sparse matrices arising from the discretization of PDEs with discontinuous coefficients. The numerical results show that the MTFFD preconditioner is much more efficient than the TFFD preconditioner.     

A finite volume method on general surfaces and its error estimates

In this paper, we study a finite volume method and its error estimates for the numerical solution of some model second order elliptic partial differential equations defined on a smooth surface. The discretization is defined via a surface mesh consisting of piecewise planar triangles and piecewise polygons. The optimal error estimates of the approximate solution are proved in both the H¹ and L² norms which are of first order and second order respectively under mesh regularity assumptions. Some numerical tests are also carried out to experimentally verify our theoretical analysis.     

Second order unconditionally convergent and energy stable linearized scheme for MHD equations

In this paper, we propose an efficient numerical scheme for magnetohydrodynamics (MHD) equations. This scheme is based on a second order backward difference formula for time derivative terms, extrapolated treatments in linearization for nonlinear terms. Meanwhile, the mixed finite element method is used for spatial discretization. We present that the scheme is unconditionally convergent and energy stable with second order accuracy with respect to time step. The optimal L ² and H ¹ fully discrete error estimates for velocity, magnetic variable and pressure are also demonstrated. A series of numerical tests are carried out to confirm our theoretical results. In addition, the numerical experiments also show the proposed scheme outperforms the other classic second order schemes, such as Crank-Nicolson/Adams-Bashforth scheme, linearized Crank-Nicolson’s scheme and extrapolated Gear’s scheme, in solving high physical parameters MHD problems.     

Domain Decomposition of Optimal Control Problems for Dynamic Networks of Elastic Strings

We consider optimal control problems related to exact- and approximate controllability of dynamic networks of elastic strings. In this note we concentrate on problems with linear dynamics, no state and no control constraints. The emphasis is on approximating target states and velocities in part of the network using a dynamic domain decomposition method (d³m) for the optimality system on the network. The decomposition is established via a Uzawa-type saddle-point iteration associated with an augmented Lagrangian relaxation of the transmission conditions at multiple joints. We consider various cost functions and prove convergence of the infinite dimensional scheme for an exemplaric choice of the cost. We also give numerical evidence in the case of simple exemplaric networks.