Exponential integrator

Exponential integrators are a class of numerical methods for the solution of ordinary differential equations, specifically initial value problems. This large class of methods from numerical analysis is based on the exact integration of the linear part of the initial value problem. Because the linear part is integrated exactly, this can help to mitigate the stiffness of a differential equation. Exponential integrators can be constructed to be explicit or implicit for numerical ordinary differential equations or serve as the time integrator for numerical partial differential equations.

Background

edit

Dating back to at least the 1960s, these methods were recognized by Certaine[1] and Pope.[2] As of late exponential integrators have become an active area of research, see Hochbruck and Ostermann (2010).[3] Originally developed for solving stiff differential equations, the methods have been used to solve partial differential equations including hyperbolic as well as parabolic problems[4] such as the heat equation.

Introduction

edit

We consider initial value problems of the form,

 

where   is composed of linear terms, and   is composed of the non-linear terms. These problems can come from a more typical initial value problem

 

after linearizing locally about a fixed or local state  :

 

Here,   refers to the partial derivative of   with respect to   (the Jacobian of f).

Exact integration of this problem from time 0 to a later time   can be performed using matrix exponentials to define an integral equation for the exact solution:[3]

 

This is similar to the exact integral used in the Picard–Lindelöf theorem. In the case of  , this formulation is the exact solution to the linear differential equation.

Numerical methods require a discretization of equation (2). They can be based on Runge-Kutta discretizations,[5][6][7] linear multistep methods or a variety of other options.

Exponential Rosenbrock methods

edit

Exponential Rosenbrock methods were shown to be very efficient in solving large systems of stiff ordinary differential equations, usually resulted from spatial discretization of time dependent (parabolic) PDEs. These integrators are constructed based on a continuous linearization of (1) along the numerical solution  

 

where   This procedure enjoys the advantage, in each step, that   This considerably simplifies the derivation of the order conditions and improves the stability when integrating the nonlinearity  . Again, applying the variation-of-constants formula (2) gives the exact solution at time   as

 

The idea now is to approximate the integral in (4) by some quadrature rule with nodes   and weights   ( ). This yields the following class of   explicit exponential Rosenbrock methods, see Hochbruck and Ostermann (2006), Hochbruck, Ostermann and Schweitzer (2009):

 
 

with  . The coefficients   are usually chosen as linear combinations of the entire functions  , respectively, where

 

These functions satisfy the recursion relation

 

By introducing the difference  , they can be reformulated in a more efficient way for implementation (see also [3]) as

 
 

In order to implement this scheme with adaptive step size, one can consider, for the purpose of local error estimation, the following embedded methods

 

which use the same stages   but with weights  .

For convenience, the coefficients of the explicit exponential Rosenbrock methods together with their embedded methods can be represented by using the so-called reduced Butcher tableau as follows:

 
   
     
         
         
         

Stiff order conditions

edit

Moreover, it is shown in Luan and Ostermann (2014a)[8] that the reformulation approach offers a new and simple way to analyze the local errors and thus to derive the stiff order conditions for exponential Rosenbrock methods up to order 5. With the help of this new technique together with an extension of the B-series concept, a theory for deriving the stiff order conditions for exponential Rosenbrock integrators of arbitrary order has been finally given in Luan and Ostermann (2013).[9] As an example, in that work the stiff order conditions for exponential Rosenbrock methods up to order 6 have been derived, which are stated in the following table:

 

Here   denote arbitrary square matrices.

Convergence analysis

edit

The stability and convergence results for exponential Rosenbrock methods are proved in the framework of strongly continuous semigroups in some Banach space.

Examples

edit

All the schemes presented below fulfill the stiff order conditions and thus are also suitable for solving stiff problems.

Second-order method

edit

The simplest exponential Rosenbrock method is the exponential Rosenbrock–Euler scheme, which has order 2, see, for example Hochbruck et al. (2009):

 

Third-order methods

edit

A class of third-order exponential Rosenbrock methods was derived in Hochbruck et al. (2009), named as exprb32, is given as:

exprb32:

1
 
0

which reads as

 
 

where  

For a variable step size implementation of this scheme, one can embed it with the exponential Rosenbrock–Euler:

 

Fourth-order ETDRK4 method of Cox and Matthews

edit

Cox and Matthews[5] describe a fourth-order method exponential time differencing (ETD) method that they used Maple to derive.

We use their notation, and assume that the unknown function is  , and that we have a known solution   at time  . Furthermore, we'll make explicit use of a possibly time dependent right hand side:  .

Three stage values are first constructed:

 
 
 

The final update is given by,

 

If implemented naively, the above algorithm suffers from numerical instabilities due to floating point round-off errors.[10] To see why, consider the first function,

 

which is present in the first-order Euler method, as well as all three stages of ETDRK4. For small values of  , this function suffers from numerical cancellation errors. However, these numerical issues can be avoided by evaluating the   function via a contour integral approach [10] or by a Padé approximant.[11]

Applications

edit

Exponential integrators are used for the simulation of stiff scenarios in scientific and visual computing, for example in molecular dynamics,[12] for VLSI circuit simulation,[13][14] and in computer graphics.[15] They are also applied in the context of hybrid monte carlo methods.[16] In these applications, exponential integrators show the advantage of large time stepping capability and high accuracy. To accelerate the evaluation of matrix functions in such complex scenarios, exponential integrators are often combined with Krylov subspace projection methods.

See also

edit

Notes

edit

References

edit
edit