Mono-implicit Runge-Kutta schemes for the parallel solution of initial value ODEs

Among the numerical techniques commonly considered for the efficient solution of stiff initial value ordinary differential equations are the implicit Runge-Kutta (IRK) schemes. The calculation of the stages of the IRK method involves the solution of a nonlinear system of equations usually employing some variant of Newton's method. Since the costs of the linear algebra associated with the implementation of Newton's method generally dominate the overall cost of the computation, many subclasses of IRK schemes, such as diagonally implicit Runge-Kutta schemes, singly implicit Runge-Kutta schemes, and mono-implicit (MIRK) schemes, have been developed to attempt to reduce these costs. In this paper we are concerned with the design of MIRK schemes that are inherently parallel in that smaller systems of equations are apportioned to concurrent processors. This work builds on that of an earlier investigation in which a special subclass of the MIRK formulas were implemented in parallel. While suitable parallelism was achieved, the formulas were limited to some extent because they all had only stage order 1. This is of some concern since in the application of a Runge-Kutta method to a system of stiff ODEs the phenomenon of order reduction can arise; the IRK method can behave as if its order were only its stage order (or its stage order plus one), regardless of its classical order. The formulas derived in the current paper represent an improvement over the previous investigation in that the full class of MIRK formulas is considered and therefore it is possible to derive efficient, parallel formulas of orders 2, 3, and 4, having stage orders 2 or 3.     

On the generation of mono-implicit Runge-Kutta-Nyström methods by mono-implicit Runge-Kutta methods

Mono-implicit Runge-Kutta methods can be used to generate implicit Runge-Kutta-Nyström (IRKN) methods for the numerical solution of systems of second-order differential equations. The paper is concerned with the investigation of the conditions to be fulfilled by the mono-implicit Runge-Kutta (MIRK) method in order to generate a mono-implicit Runge-Kutta-Nyström method (MIRKN) that is P-stable. One of the main theoretical results is the property that MIRK methods (in standard form) cannot generate MIRKN methods (in standard form) of order greater than 4. Many examples of MIRKN methods generated by MIRK methods are presented.     

The order ofB-convergence of algebraically stable Runge-Kutta methods

In a previous paper it was shown that for a class of semi-linear problems many high order Runge-Kutta methods have order of optimalB-convergence one higher than the stage order. In this paper we show that for the more general class of nonlinear dissipative problems such as result holds only for a small class of Runge-Kutta methods and that such methods have at most classical order 3.     

ORDER PROPERTIES AND CONSTRUCTION OF SYMPLECTIC RUNGE-KUTTA METHODS

1. IntroductionFOr a given s stage Runge-Kutta methodwith A = [ail], p = [pl, PZt... 5 P.]T and ac = [afl, ry23... ) %]T / 0, we introduce thefollowing simplifying conditions as in Butcher [1]and make the notational convensionwhere 1 5 m? pi(x), i ~ 1, 2, 3,' ? are arbitrarily given i--th polynomials with the property that pi(0) = 0,Note that B(P), C(P) and D(P) are equivalent to BI,. = 0, CI,P = 0 and DI,. = 0respectively. We shall always denote BI,., CI,., DI,. and VI,. by B, …     

A mono-implicit Runge-Kutta-Nyström modification of the Numerov method

We present two two-parameter families of fourth-order mono-implicit Runge-Kutta-Nyström methods. Each member of these families can be considered as a modification of the Numerov method. We analyze the stability and periodicity properties of these methods. It is shown that (i) within one of these families there exist A-stable (even L-stable) and P-stable methods, and (ii) in both families there exist methods with a phase lag of order six.     

Symplectic RK Methods and Symplectic PRK Methods with Real Eigenvalues

Properties of symplectic Runge-Kutta (RK) methods and symplectic partitioned Runge-Kutta (PRK) methods with real eigenvalues are discussed in this paper. It is shown that an s stage such method can‘t reach order more than s 1. Particularly, we prove that no symplectic RK method with real eigenvalues exists in stage s of order s 1 when s is even. But an example constructed by using the W-transformation shows that PRK method of this type does not necessarily meet this order barrier. Another useful way other than W-transformation to construct symplectic PRK method with real eigenvalues is then presented. Finally, a class of efficient symplectic methods is recommended.     

On implicit Runge-Kutta methods with high stage order

It is well known that high stage order is a desirable property for implicit Runge-Kutta methods. In this paper it is shown that it is always possible to construct ans-stage IRK method with a given stability function and stage orders−1 if the stability function is an approximation to the exponential function of at least orders. It is further indicated how to construct such methods as well as in which cases the constructed methods will be stiffly accurate.     

Half-explicit Runge-Kutta methods for semi-explicit differential-algebraic equations of index 1

Summary For the numerical solution of non-stiff semi-explicit differentialalgebraic equations (DAEs) of index 1 half-explicit Runge-Kutta methods (HERK) are considered that combine an explicit Runge-Kutta method for the differential part with a simplified Newton method for the (approximate) solution of the algebraic part of the DAE. Two principles for the choice of the initial guesses and the number of Newton steps at each stage are given that allow to construct HERK of the same order as the underlying explicit Runge-Kutta method. Numerical tests illustrate the efficiency of these methods.     

A bound on the maximum strong order of stochastic Runge-Kutta methods for stochastic ordinary differential equations

In Burrage and Burrage [1] it was shown that by introducing a very general formulation for stochastic Runge-Kutta methods, the previous strong order barrier of order one could be broken without having to use higher derivative terms. In particular, methods of strong order 1.5 were developed in which a Stratonovich integral of order one and one of order two were present in the formulation. In this present paper, general order results are proven about the maximum attainable strong order of these stochastic Runge-Kutta methods (SRKs) in terms of the order of the Stratonovich integrals appearing in the Runge-Kutta formulation. In particular, it will be shown that if ans-stage SRK contains Stratonovich integrals up to orderp then the strong order of the SRK cannot exceed min{(p+1)/2, (s−1)/2},p≥2,s≥3 or 1 ifp=1.     

The efficiency of Singly-implicit Runge-Kutta methods for stiff differential equations

Singly-implicit Runge-Kutta methods are considered to be good candidates for stiff problems because of their good stability and high accuracy. The existing methods, SIRK (Singly-implicit Runge-Kutta), DESI (Diagonally Extendable Singly-implicit Runge-Kutta), ESIRK (Effective order Singly-implicit Rung-Kutta) and DESIRE (Diagonally Extended Singly-implicit Runge-Kutta Effective order) methods have been shown to be efficient for stiff differential equations, especially for high dimensional stiff problems. In this paper, we measure the efficiency for the family of singly-implicit Runge-Kutta methods using the local truncation error produced within one single step and the count of number of operations. Verification of the error and the computational costs for these methods using variable stepsize scheme are presented. We show how the numerical results are effected by the designed factors: additional diagonal-implicit stages and effective order.     

Mono-Implicit Runge-Kutta-Nyström Methods with Application to Boundary Value Ordinary Differential Equations

The successful use of mono-implicit Runge—Kutta methods has been demonstrated by several researchers who have employed these methods in software packages for the numerical solution of boundary value ordinary differential equations. However, these methods are only applicable to first order systems of equations while many boundary value systems involve higher order equations. While it is straightforward to convert such systems to first order, several advantages, including substantial gains in efficiency, higher continuity of the approximate solution, and lower storage requirements, are realized when the equations can be treated in their original higher order form. In this paper, we consider generalizations of mono-implicit Runge—Kutta methods, called mono-implicit Runge—Kutta—Nyström methods, suitable for systems of second order ordinary differential equations having the general form, y(t) = f(t,y(t),y(t)), and derive optimal symmetric methods of orders two, four, and six. We also introduce continuous mono-implicit Runge—Kutta—Nyström methods which allow us to provide continuous solution and derivative approximations. Numerical results are included to demonstrate the effectiveness of these methods; savings of 65% are attained in some instances.This revised version was published online in October 2005 with corrections to the Cover Date.     

Runge-Kutta methods for third order weak approximation of SDEs with multidimensional additive noise

A new class of third order Runge-Kutta methods for stochastic differential equations with additive noise is introduced. In contrast to Platen’s method, which to the knowledge of the author has been up to now the only known third order Runge-Kutta scheme for weak approximation, the new class of methods affords less random variable evaluations and is also applicable to SDEs with multidimensional noise. Order conditions up to order three are calculated and coefficients of a four stage third order method are given. This method has deterministic order four and minimized error constants, and needs in addition less function evaluations than the method of Platen. Applied to some examples, the new method is compared numerically with Platen’s method and some well known second order methods and yields very promising results.     

Singly implicit diagonally extended Runge-Kutta methods of fourth order

Singly implicit diagonally extended Runge-Kutta methods make it possible to combine the merits of diagonally implicit methods (namely, the simplicity of implementation) and fully implicit ones (high stage order). Due to this combination, they can be very efficient at solving stiff and differential-algebraic problems. In this paper, fourth-order methods with an explicit first stage are examined. The methods have the third or fourth stage order. Consideration is given to an efficient implementation of these methods. The results of tests in which the proposed methods were compared with the fifth-order RADAU IIA method are presented.     

Time integration of inelastic material models exhibits an order reduction for higher-order methods – can this be avoided?

For the numerical treatment of inelastic material behavior within the finite element method a partitioned ansatz is standard in most of the software frameworks; the weak form of equilibrium is discretized in space and solved on a global level, whereas the initial value problem for the evolution equations of internal state variables is separately solved on a local, i.e. Gauss-point level, where strains, derived from global displacements, serve as input, [1]. Applying higher order methods (p > 2) to the time integration of plasticity models an order reduction is reported where Runge-Kutta schemes have shown hardly more than order two at best [2, 3]. In the present contribution, we analyze the reason for order reduction and in doing so, introduce an improved strain approximation and switching point detection which play a crucial role for the convergence order of multi-stage methods used in this context. We apply Runge-Kutta methods of Radau IIa class to the evolution equations of viscoelastic and elastoplastic material models and show ther improved performence in numerical examples. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Class of Single Step Methods with a Large Interval of Absolute Stability

In this paper, a class of integration formulas is derived from the approximation so that the first derivative can be expressed within an interval $[nh,(n+1)h]$ as $$\frac{dy}{dt}=-P(y-y_n)+f_n+Q_n(t).$$ The class of formulas is exact if the differential equation has the shown form, where $P$ is a diagonal matrix, whose elements $$-pj=\frac{\partial}{\partial y_j}f_j(t_n,y_n),j=1,\cdots,m$$ are constant in the interval $[nh,(n+1)h]$, and $Q_n(t)$ is a polynomial in $t$. Each of the formulas derived in this paper includes only the first derivative $f$ and $$-pj=\frac{\partial}{\partial y_j}f_j(t_n,y_n).$$ It is identical with a certain Runge-Kutta method. In particular, when $Q_n(t)$ is a polynomial of degree two, one of our formulas is an extension of Treanor's method, and possesses better stability properties. Therefore the formulas derived in this paper can be regarded as a modified or an extended form of the classical Runge-Kutta methods. Preliminary numerical results indicate that our fourth order formula is superior to Treanor's in stability properties.     

A New Integrator for Special Third Order Differential Equations With Application to Thin Film Flow Problem

In recent time, Runge-Kutta methods that integrate special third order ordinary differential equations (ODEs) directly are proposed to address efficiency issues associated with classical Runge-Kutta methods. Albeit, the methods require evaluation of three set of equations to proceed with the numerical integration. In this paper, we propose a class of multistep-like Runge-Kutta methods (hybrid methods), which integrates special third order ODEs directly. The method is completely derivative-free. Algebraic order conditions of the method are derived. Using the order conditions, a four-stage method is presented. Numerical experiment is conducted on some test problems. The method is also applied to a practical problem in Physics and engineering to ascertain its validity. Results from the experiment show that the new method is more accurate and efficient than the classical Runge-Kutta methods and a class of direct Runge-Kutta methods recently designed for special third order ODEs.     

A comparison of Rosenbrock and ESDIRK methods combined with iterative solvers for unsteady compressible flows

In this article, we endeavour to find a fast solver for finite volume discretizations for compressible unsteady viscous flows. Thereby, we concentrate on comparing the efficiency of important classes of time integration schemes, namely time adaptive Rosenbrock, singly diagonally implicit (SDIRK) and explicit first stage singly diagonally implicit Runge-Kutta (ESDIRK) methods. To make the comparison fair, efficient equation system solvers need to be chosen and a smart choice of tolerances is needed. This is determined from the tolerance TOL that steers time adaptivity. For implicit Runge-Kutta methods, the solver is given by preconditioned inexact Jacobian-free Newton-Krylov (JFNK) and for Rosenbrock, it is preconditioned Jacobian-free GMRES. To specify the tolerances in there, we suggest a simple strategy of using TOL/100 that is a good compromise between stability and computational effort. Numerical experiments for different test cases show that the fourth order Rosenbrock method RODASP and the fourth order ESDIRK method ESDIRK4 are best for fine tolerances, with RODASP being the most robust scheme.     

High-Order Accurate Runge-Kutta (Local) Discontinuous Galerkin Methods for One- and Two-Dimensional Fractional Diffusion Equations

As the generalization of the integer order partial differential equations (PDE), the fractional order PDEs are drawing more and more attention for their applications in fluid flow, finance and other areas. This paper presents high-order accurate Runge-Kutta local discontinuous Galerkin (DG) methods for one- and two-dimensional fractional diffusion equations containing derivatives of fractional order in space. The Caputo derivative is chosen as the representation of spatial derivative, because it may represent the fractional derivative by an integral operator. Some numerical examples show that the convergence orders of the proposed local $P^k$-DG methods are $O(h^{k+1})$ both in one and two dimensions, where $P^k$ denotes the space of the real-valued polynomials with degree at most $k$.     

A comparison of time adaptive integration methods for small and large strain viscoelasticity

In quasistatic solid mechanics the initial boundary value problem has to be solved in the space and time domain. The spatial discretization is done using finite elements. For the temporal discretization three different classes of Runge-Kutta methods are compared. These methods are diagonally implicit Runge-Kutta schemes (DIRK), linear implicit Runge-Kutta methods (Rosenbrock type methods) and half-explicit Runge-Kutta schemes (HERK). It will be shown that the application of half-explicit or linear-implicit Runge-Kutta methods can enormously reduce the computational time in particular situations. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The non-existence of ten stage eighth order explicit Runge-Kutta methods

It is shown that forn a non-negative integer, there does not exist an explicit Runge-Kutta method with 10 +n stages and order 8 +n. It follows that for order 8, the minimum number of stages is 11.Presented at the symposium in Stockholm, 7–10 January 1985, in honour of G. Dahlquist.