Contractivity of Runge-Kutta methods

In this paper we present necessary and sufficient conditions for Runge-Kutta methods to be contractive. We consider not only unconditional contractivity for arbitrary dissipative initial value problems, but also conditional contractivity for initial value problems where the right hand side function satisfies a circle condition. Our results are relevant for arbitrary norms, in particular for the maximum norm.For contractive methods, we also focus on the question whether there exists a unique solution to the algebraic equations in each step. Further we show that contractive methods have a limited order of accuracy. Various optimal methods are presented, mainly of explicit type. We provide a numerical illustration to our theoretical results by applying the method of lines to a parabolic and a hyperbolic partial differential equation.Research supported by the Netherlands Organization for Scientific Research (N.W.O.) and the Royal Netherlands Academy of Arts and Sciences (K.N.A.W.)     

Contractivity of domain decomposition splitting methods for nonlinear parabolic problems

This work deals with the efficient numerical solution of nonlinear parabolic problems posed on a two-dimensional domain Ω. We consider a suitable decomposition of domain Ω and we construct a subordinate smooth partition of unity that we use to rewrite the original equation. Then, the combination of standard spatial discretizations with certain splitting time integrators gives rise to unconditionally contractive schemes. The efficiency of the resulting algorithms stems from the fact that the calculations required at each internal stage can be performed in parallel.     

Comparing the contractivity properties of semi-implicit methods

Contractivity is a desirable property of numerical integration methods for stiff systems of ordinary differential equations. In this paper, numerical parameters are used to allow a direct and quantitative comparison of the contractivity properties of various methods for non-linear stiff problems. Results are provided for popular Rosenbrock methods and some more recently developed semi-implicit methods.     

Error and extrapolation of a compact LOD method for parabolic differential equations

This paper is concerned with a compact locally one-dimensional (LOD) finite difference method for solving two-dimensional nonhomogeneous parabolic differential equations. An explicit error estimate for the finite difference solution is given in the discrete infinity norm. It is shown that the method has the accuracy of the second-order in time and the fourth-order in space with respect to the discrete infinity norm. A Richardson extrapolation algorithm is developed to make the final computed solution fourth-order accurate in both time and space when the time step equals the spatial mesh size. Numerical results demonstrate the accuracy and the high efficiency of the extrapolation algorithm.     

Dimension splitting for evolution equations

In this paper, we are concerned with splitting methods for the time integration of abstract evolution equations. We introduce an analytic framework which allows us to prove optimal convergence orders for various splitting methods, including the Lie and Peaceman–Rachford splittings. Our setting is applicable for a wide variety of linear equations and their dimension splittings. In particular, we analyze parabolic problems with Dirichlet boundary conditions, as well as degenerate equations on bounded domains. We further illustrate our theoretical results with a set of numerical experiments. This work was supported by the Austrian Science Fund under grant M961-N13.     

Locally linearized fractional step methods for nonlinear parabolic problems

This work deals with the efficient numerical solution of a class of nonlinear time-dependent reaction-diffusion equations. Via the method of lines approach, we first perform the spatial discretization of the original problem by applying a mimetic finite difference scheme. The system of ordinary differential equations arising from that process is then integrated in time with a linearly implicit fractional step method. For that purpose, we locally decompose the discrete nonlinear diffusion operator using suitable Taylor expansions and a domain decomposition splitting technique. The totally discrete scheme considers implicit time integrations for the linear terms while explicitly handling the nonlinear ones. As a result, the original problem is reduced to the solution of several linear systems per time step which can be trivially decomposed into a set of uncoupled parallelizable linear subsystems. The convergence of the proposed methods is illustrated by numerical experiments.     

Meshless local Petrov-Galerkin (MLPG) approximation to the two dimensional sine-Gordon equation

During the past few years, the idea of using meshless methods for numerical solution of partial differential equations (PDEs) has received much attention throughout the scientific community, and remarkable progress has been achieved on meshless methods. The meshless local Petrov-Galerkin (MLPG) method is one of the “truly meshless” methods since it does not require any background integration cells. The integrations are carried out locally over small sub-domains of regular shapes, such as circles or squares in two dimensions and spheres or cubes in three dimensions. In this paper the MLPG method for numerically solving the non-linear two-dimensional sine-Gordon (SG) equation is developed. A time-stepping method is employed to deal with the time derivative and a simple predictor-corrector scheme is performed to eliminate the non-linearity. A brief discussion is outlined for numerical integrations in the proposed algorithm. Some examples involving line and ring solitons are demonstrated and the conservation of energy in undamped SG equation is investigated. The final numerical results confirm the ability of proposed method to deal with the unsteady non-linear problems in large domains.     

A-priori error estimates of Galerkin backward differentiation methods in time-inhomogeneous parabolic problems

Summary Backward differentiation methods up to orderk=5 are applied to solve linear ordinary and partial (parabolic) differential equations where in the second case the space variables are discretized by Galerkin procedures. Using a mean square norm over all considered time levels a-priori error estimates are derived. The emphasis of the results lies on the fact that the obtained error bounds do not depend on a Lipschitz constant and the dimension of the basic system of ordinary differential equations even though this system is allowed to have time-varying coefficients. It is therefore possible to use the bounds to estimate the error of systems with arbitrary varying dimension as they arise in the finite element regression of parabolic problems.     

Contractivity preserving explicit linear multistep methods

Summary We investigate contractivity properties of explicit linear multistep methods in the numerical solution of ordinary differential equations. The emphasis is on the general test-equation , whereA is a square matrix of arbitrary orders1. The contractivity is analysed with respect to arbitrary norms in thes-dimensional space (which are not necessarily generated by an inner product). For given order and stepnumber we construct optimal multistep methods allowing the use of a maximal stepsize.This research has been supported by the Netherlands organisation for scientific research (NWO)     

On the Contractivity Region of Runge-Kutta Methods

In this paper we first introduce the definition of contractivity region of Runge-Kutta methods and then examine the general features of the contractivity regions. We find that the intersections of the contractivity region and the axis place is $C^s$ are always either the whole axis plane or a generalized disk introduced by Dahlquist and Jeltsch. We also define the AN-contractivity and show that it is equivalent to the algebraic stability and can be determined locally in a neighborhood of the origion. However, many implicit methods are only r-circle contractive but not AN-contractive. A simple bound for the radius r of the r-circle contractive methods is given.     

Global extrapolation with a parallel splitting method

Extrapolation with a parallel splitting method is discussed. The parallel splitting method reduces a multidimensional problem into independent one-dimensional problems and can improve the convergence order of space variables to an order as high as the regularity of the solution permits. Therefore, in order to match the convergence order of the space variables, a high order method should also be used for the time integration. Second and third order extrapolation methods are used to improve the time convergence and it was found that the higher order extrapolation method can produce a more accurate solution than the lower order extrapolation method, but the convergence order of high order extrapolation may be less than the actual order of the extrapolation. We also try to show a fact that has not been studied in the literature, i.e. when the extrapolation is used, it may decrease the convergence of the space variables. The higher the order of the extrapolation method, the more it decreases the convergence of the space variables. The global extrapolation method also improves the parallel degree of the parallel splitting method. Numerical tests in the paper are done in a domain of a unit circle and a unit square.Supported by the Academy of Finland.     

A convergence analysis of hopscotch methods for fourth order parabolic equations

Summary Consider the ODE (ordinary differential equation) that arises from a semi-discretization (discretization of the spatial coordinates) of a first order system form of a fourth order parabolic PDE (partial differential equation). We analyse the stability of the finite difference methods for this fourth order parabolic PDE that arise if one applies the hopscotch idea to this ODE.Often the error propagation of these methods can be represented by a three terms matrix-vector recursion in which the matrices have a certain anti-hermitian structure. We find a (uniform) expression for the stability bound (or error propagation bound) of this recursion in terms of the norms of the matrices. This result yields conditions under which these methods are strongly asymptotically stable (i.e. the stability is uniform both with respect to the spatial and the time stepsizes (tending to 0) and the time level (tending to infinity)), also in case the PDE has (spatial) variable coefficients. A convergence theorem follows immediately.     

A note on contractivity in the numerical solution of initial value problems

This paper concerns the stability analysis of numerical methods for approximating the solutions to (stiff) initial value problems. Our analysis includes the case of (nonlinear) systems of differential equations that are essentially more general than the classical test equationU=U, with a complex constant.We explore the relation between two stability concepts, viz. the concepts of contractivity and weak contractivity.General Runge-Kutta methods, one-stage Rosenbrock methods and a notable rational Runge-Kutta method are analysed in some detail.     

On the convergence of multistep methods for nonlinear stiff differential equations

Summary Convergence estimates are given forA()-stable multistep methods applied to singularly perturbed differential equations and nonlinear parabolic problems. The approach taken here combines perturbation arguments with frequency domain techniques.     

Unconditionally stable explicit methods for parabolic equations

Summary This paper discussesrational Runge-Kutta methods for stiff differential equations of high dimensions. These methods are explicit and in addition do not require the computation or storage of the Jacobian. A stability analysis (based onn-dimensional linear equations) is given. A second orderA ₀-stable method with embedded error control is constructed and numerical results of stiff problems originating from linear and nonlinear parabolic equations are presented.     

Operator splitting methods for pricing American options under stochastic volatility

We consider the numerical pricing of American options under Heston’s stochastic volatility model. The price is given by a linear complementarity problem with a two-dimensional parabolic partial differential operator. We propose operator splitting methods for performing time stepping after a finite difference space discretization. The idea is to decouple the treatment of the early exercise constraint and the solution of the system of linear equations into separate fractional time steps. With this approach an efficient numerical method can be chosen for solving the system of linear equations in the first fractional step before making a simple update to satisfy the early exercise constraint. Our analysis suggests that the Crank–Nicolson method and the operator splitting method based on it have the same asymptotic order of accuracy. The numerical experiments show that the operator splitting methods have comparable discretization errors. They also demonstrate the efficiency of the operator splitting methods when a multigrid method is used for solving the systems of linear equations.     

Analysis of a one-dimensional free boundary flow problem

A one-dimensional free surface problem is considered. It consists in Burgers’ equation with an additional diffusion term on a moving interval. The well-posedness of the problem is investigated and existence and uniqueness results are obtained locally in time. A semi-discretization in space with a piecewise linear finite element method is considered. A priori and a posteriori error estimates are given for the semi-discretization in space. A time splitting scheme allows to obtain numerical results in agreement with the theoretical investigations.Supported by the Swiss National Science Foundation     

A parareal waveform relaxation algorithm for semi-linear parabolic partial differential equations

We report a new parallel iterative algorithm for semi-linear parabolic partial differential equations (PDEs) by combining a kind of waveform relaxation (WR) techniques into the classical parareal algorithm. The parallelism can be simultaneously exploited by WR and parareal in different directions. We provide sharp error estimations for the new algorithm on bounded time domain and on unbounded time domain, respectively. The iterations of the parareal and the WR are balanced to optimize the performance of the algorithm. Furthermore, the speedup and the parallel efficiency of the new approach are analyzed. Numerical experiments are carried out to verify the effectiveness of the theoretic work.     

An exponential transformation based splitting method for fast computations of highly oscillatory solutions

Splitting, or decomposition, methods have been widely used for achieving higher computational efficiency in solving wave equations. A major concern has remained, however, if the wave number involved is exceptionally large. In the case, merits of a conventional splitting method may diminish due to the fact that tiny discretization steps need to be employed to compensate high oscillations. This paper studies an alternative way for solving highly oscillatory paraxial wave problems via a modified splitting strategy. In the process, an exponential transformation is first introduced to convert the underlying differential equation to coupled nonlinear equations. Then the resulted oscillation-free system is treated by a Local-One-Dimensional (LOD) scheme for desired accuracy, efficiency and computability. The splitting method acquired is asymptotically stable and easy to use. Computational experiments are given to illustrate our numerical procedures.     

Flux-splitting schemes for parabolic problems

Splitting with respect to space variables can be used in solving boundary value problems for second-order parabolic equations. Classical alternating direction methods and locally one-dimensional schemes could be examples of this approach. For problems with rapidly varying coefficients, a convenient tool is the use of fluxes (directional derivatives) as independent variables. The original equation is written as a system in which not only the desired solution but also directional derivatives (fluxes) are unknowns. In this paper, locally one-dimensional additional schemes (splitting schemes) for second-order parabolic equations are examined. By writing the original equation in flux variables, certain two-level locally one-dimensional schemes are derived. The unconditional stability of locally one-dimensional flux schemes of the first and second approximation order with respect to time is proved.