Total variation diminishing Runge-Kutta schemes

In this paper we further explore a class of high order TVD (total variation diminishing) Runge-Kutta time discretization initialized in a paper by Shu and Osher, suitable for solving hyperbolic conservation laws with stable spatial discretizations. We illustrate with numerical examples that non-TVD but linearly stable Runge-Kutta time discretization can generate oscillations even for TVD (total variation diminishing) spatial discretization, verifying the claim that TVD Runge-Kutta methods are important for such applications. We then explore the issue of optimal TVD Runge-Kutta methods for second, third and fourth order, and for low storage Runge-Kutta methods.

     

Preconditioners for nonconforming discretizations

We prove an abstract norm equivalence for a two-level method, which allows us to reduce the construction of preconditioners for nonconforming finite element discretizations to known cases of conforming elements.

     

On Error Estimates of the Projection Methods for the Navier-Stokes Equations: Second-order Schemes

We present in this paper a rigorous error analysis of several projection schemes for the approximation of the unsteady incompressible Navier-Stokes equations. The error analysis is accomplished by interpreting the respective projection schemes as second-order time discretizations of a perturbed system which approximates the Navier-Stokes equations. Numerical results in agreement with the error analysis are also presented.

     

Convergence analysis of a covolume scheme for Maxwell's equations in three dimensions

This paper contains error estimates for covolume discretizations of Maxwell's equations in three space dimensions. Several estimates are proved. First, an estimate for a semi-discrete scheme is given. Second, the estimate is extended to cover the classical interlaced time marching technique. Third, some of our unstructured mesh results are specialized to rectangular meshes, both uniform and nonuniform. By means of some additional analysis it is shown that the spatial convergence rate is one order higher than for the unstructured case.

     

Backward Euler discretization of fully nonlinear parabolic problems

This paper is concerned with the time discretization of nonlinear evolution equations. We work in an abstract Banach space setting of analytic semigroups that covers fully nonlinear parabolic initial-boundary value problems with smooth coefficients. We prove convergence of variable stepsize backward Euler discretizations under various smoothness assumptions on the exact solution. We further show that the geometric properties near a hyperbolic equilibrium are well captured by the discretization. A numerical example is given.

     

The convergence of V-cycle multigrid algorithms for axisymmetric Laplace and Maxwell equations

We investigate some simple finite element discretizations for the axisymmetric Laplace equation and the azimuthal component of the axisymmetric Maxwell equations as well as multigrid algorithms for these discretizations. Our analysis is targeted at simple model problems and our main result is that the standard V-cycle with point smoothing converges at a rate independent of the number of unknowns. This is contrary to suggestions in the existing literature that line relaxations and semicoarsening are needed in multigrid algorithms to overcome difficulties caused by the singularities in the axisymmetric Maxwell problems. Our multigrid analysis proceeds by applying the well known regularity based multigrid theory. In order to apply this theory, we prove regularity results for the axisymmetric Laplace and Maxwell equations in certain weighted Sobolev spaces. These, together with some new finite element error estimates in certain weighted Sobolev norms, are the main ingredients of our analysis.

     

Primal Dual Methods for Wasserstein Gradient Flows

Combining the classical theory of optimal transport with modern operator splitting techniques, we develop a new numerical method for nonlinear, nonlocal partial differential equations, arising in models of porous media, materials science, and biological swarming. Our method proceeds as follows: first, we discretize in time, either via the classical JKO scheme or via a novel Crank–Nicolson-type method we introduce. Next, we use the Benamou–Brenier dynamical characterization of the Wasserstein distance to reduce computing the solution of the discrete time equations to solving fully discrete minimization problems, with strictly convex objective functions and linear constraints. Third, we compute the minimizers by applying a recently introduced, provably convergent primal dual splitting scheme for three operators (Yan in J Sci Comput 1–20, 2018). By leveraging the PDEs’ underlying variational structure, our method overcomes stability issues present in previous numerical work built on explicit time discretizations, which suffer due to the equations’ strong nonlinearities and degeneracies. Our method is also naturally positivity and mass preserving and, in the case of the JKO scheme, energy decreasing. We prove that minimizers of the fully discrete problem converge to minimizers of the spatially continuous, discrete time problem as the spatial discretization is refined. We conclude with simulations of nonlinear PDEs and Wasserstein geodesics in one and two dimensions that illustrate the key properties of our approach, including higher-order convergence our novel Crank–Nicolson-type method, when compared to the classical JKO method.

     

Finite difference methods for a class of two-point boundary value problems with mixed boundary conditions

We discuss the construction of three-point finite difference aproximations for the class of two-point boundary value problems: [p(x)y′]′ = f(x, y), α₀y(a) - α₁y′(a) = A, β₀y(b) + β₁y′(b) = B.We first establish an identity from which general three-point finite difference approximations of various orders can be obtained. We then consider in detail obtaining fourth-order methods based on three evaluations of f. We obtain a family of fourth-order discretizations for the differential equations; appropriate discretizations for the boundary conditions are also obtained for use with fourth-order methods. We select the free parameters available in this discretizations which lead to a “simplest” fourth-order method. This method is described and its convergence is established; numerical examples are given to illustrate this new fourth-order method.     

Approximate momentum conservation for spatial semidiscretizations of semilinear wave equations

Summary. We prove that a standard second order finite difference uniform space discretization of the semilinear wave equation with periodic boundary conditions, analytic nonlinearity, and analytic initial data conserves momentum up to an error which is exponentially small in the stepsize. Our estimates are valid for as long as the trajectories of the full semilinear wave equation remain real analytic. The method of proof is that of backward error analysis, whereby we construct a modified equation which is itself Lagrangian and translation invariant, and therefore also conserves momentum. This modified equation interpolates the semidiscrete system for all time, and we prove that it remains exponentially close to the trigonometric interpolation of the semidiscrete system. These properties directly imply approximate momentum conservation for the semidiscrete system. We also consider discretizations that are not variational as well as discretizations on non-uniform grids. Through numerical example as well as arguments from geometric mechanics and perturbation theory we show that such methods generically do not approximately preserve momentum.Mathematics Subject Classification (2000): 65M20, 58J70, 70H33     

Advection-diffusion equations: Temporal sinc methods

A fully Sinc–Galerkin method for solving advection–diffusion equations subject to arbitrary radiation boundary conditions is presented. This procedure gives rise to a discretization, which has its most natural representation in the form of a Sylvester system where the coefficient matrix for the temporal discretization is full. The word “full” often implies a computationally more complex method compared to, for example, temporal marching. In a comparison of time-marching versus this sinc-temporal procedure, the Sylvester formulation defines a common framework within which these procedures can be evaluated. This framework has been included in the introduction to illustrate an efficiency measure for either method. Similar remarks with regard to fullness versus sparseness in the Sylvester formulation apply when the spatial discretization is spectral or, for example, differencing. Although it is indicated how this sinc-temporal method can be combined with alternative spatial discretizations, the natural affinity between sinc methods for space and time discretizations motivate carrying out the numerical illustrations using the sinc basis in each. © 1995 John Wiley & Sons, Inc.     

A posteriori error estimates for the Crank-Nicolson method for parabolic equations

We derive optimal order a posteriori error estimates for time discretizations by both the Crank-Nicolson and the Crank-Nicolson-Galerkin methods for linear and nonlinear parabolic equations. We examine both smooth and rough initial data. Our basic tool for deriving a posteriori estimates are second-order Crank-Nicolson reconstructions of the piecewise linear approximate solutions. These functions satisfy two fundamental properties: (i) they are explicitly computable and thus their difference to the numerical solution is controlled a posteriori, and (ii) they lead to optimal order residuals as well as to appropriate pointwise representations of the error equation of the same form as the underlying evolution equation. The resulting estimators are shown to be of optimal order by deriving upper and lower bounds for them depending only on the discretization parameters and the data of our problem. As a consequence we provide alternative proofs for known a priori rates of convergence for the Crank-Nicolson method.

     

Convergence analysis of domain decomposition algorithms with full overlapping for the advection-diffusion problems

The aim of this paper is to study the convergence properties of a time marching algorithm solving advection-diffusion problems on two domains using incompatible discretizations. The basic algorithm is first described, and theoretical and numerical results that illustrate its convergence properties are then presented.

     

Global optimization of explicit strong-stability-preserving Runge-Kutta methods

Strong-stability-preserving Runge-Kutta (SSPRK) methods are a type of time discretization method that are widely used, especially for the time evolution of hyperbolic partial differential equations (PDEs). Under a suitable stepsize restriction, these methods share a desirable nonlinear stability property with the underlying PDE; e.g., positivity or stability with respect to total variation. This is of particular interest when the solution exhibits shock-like or other nonsmooth behaviour. A variety of optimality results have been proven for simple SSPRK methods. However, the scope of these results has been limited to low-order methods due to the detailed nature of the proofs. In this article, global optimization software, BARON, is applied to an appropriate mathematical formulation to obtain optimality results for general explicit SSPRK methods up to fifth-order and explicit low-storage SSPRK methods up to fourth-order. Throughout, our studies allow for the possibility of negative coefficients which correspond to downwind-biased spatial discretizations. Guarantees of optimality are obtained for a variety of third- and fourth-order schemes. Where optimality is impractical to guarantee (specifically, for fifth-order methods and certain low-storage methods), extensive numerical optimizations are carried out to derive numerically optimal schemes. As a part of these studies, several new schemes arise which have theoretically improved time-stepping restrictions over schemes appearing in the recent literature.

     

On conservative spatial discretizations of the barotropic quasi-gasdynamic system of equations with a potential body force

A multidimensional barotropic quasi-gasdynamic system of equations in the form of mass and momentum conservation laws with a general gas equation of state p = p(ρ) with p′(ρ) > 0 and a potential body force is considered. For this system, two new symmetric spatial discretizations on nonuniform rectangular grids are constructed (in which the density and velocity are defined on the basic grid, while the components of the regularized mass flux and the viscous stress tensor are defined on staggered grids). These discretizations involve nonstandard approximations for ?p(ρ), div(ρu), and ρ. As a result, a discrete total mass conservation law and a discrete energy inequality guaranteeing that the total energy does not grow with time can be derived. Importantly, these discretizations have the additional property of being well-balanced for equilibrium solutions. Another conservative discretization is discussed in which all mass flux components and viscous stresses are defined on the same grid. For the simpler barotropic quasi-hydrodynamic system of equations, the corresponding simplifications of the constructed discretizations have similar properties.     

Convergence Analysis of Spatially Adaptive Rothe Methods

This paper is concerned with the convergence analysis of the horizontal method of lines for evolution equations of the parabolic type. Following a semidiscretization in time by \(S\) -stage one-step methods, the resulting elliptic stage equations per time step are solved with adaptive space discretization schemes. We investigate how the tolerances in each time step must be tuned in order to preserve the asymptotic temporal convergence order of the time stepping also in the presence of spatial discretization errors. In particular, we discuss the case of linearly implicit time integrators and adaptive wavelet discretizations in space. Using concepts from regularity theory for partial differential equations and from nonlinear approximation theory, we determine an upper bound for the degrees of freedom for the overall scheme that are needed to adaptively approximate the solution up to a prescribed tolerance.     

Attractors and approximations for lattice dynamical systems

We present a sufficient condition for the existence of a global attractor for general lattice dynamical systems, then consider the existence of attractors and their approximation for second-order and first-order lattice systems which, in particular case, can be regarded as the spatial discretizations of corresponding wave equations and reaction-diffusion equations in R^k.     

On the Explicit Two-Stage Fourth-Order Accurate Time Discretizations

This paper continues to study the explicit two-stage fourth-order accurate time discretizations [5-7]. By introducing variable weights, we propose a class of more general explicit one-step two-stage time discretizations, which are different from the existing methods, e.g. the Euler methods, Runge-Kutta methods, and multistage multiderivative methods etc. We study the absolute stability, the stability interval, and the intersection between the imaginary axis and the absolute stability region. Our results show that our two-stage time discretizations can be fourth-order accurate conditionally, the absolute stability region of the proposed methods with some special choices of the variable weights can be larger than that of the classical explicit fourth- or fifth-order Runge-Kutta method, and the interval of absolute stability can be almost twice as much as the latter. Several numerical experiments are carried out to demonstrate the performance and accuracy as well as the stability of our proposed methods.     

Uniform convergence of the multigrid V-cycle for an anisotropic problem

In this paper, we consider the linear systems arising from the standard finite element discretizations of certain second order anisotropic problems with variable coefficients on a rectangle. We study the performance of a V-cycle multigrid method applied to the finite element equations. Since the usual ``regularity and approximation' assumption does not hold for the anisotropic finite element problems, the standard multigrid convergence theory cannot be applied directly. In this paper, a modification of the theory of Braess and Hackbusch will be presented. We show that the V-cycle multigrid iteration with a line smoother is a uniform contraction in the energy norm. In the verification of the hypotheses in our theory, we use a weighted -norm estimate for the error in the Galerkin finite element approximation and a smoothing property of the line smoothers which is proved in this paper.

     

On a certain class of linear Hamiltonian maps

We discovered a certain class of linear Hamiltonian maps which are defined by explicit time dependent Hamiltonian functions. Our method is the analogy of Moser's construction in 1986, although it is not so difficult, but we think the results are new.

     

Time discretizations for Maxwell‐Bloch equations

In this article we derive new time discretizations for the numerical simulation of Maxwell‐Bloch equations. These discretizations decouple the equations, thus leading to improved efficiency. This approach may be combined with the fulfilment of physical properties, such as positiveness properties, which are not accounted for by classical schemes. Our time discretizations are moreover proved to be nonlinearly stable. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 284–300, 2003.