Two-stage and Three-stage Diagonally Implicit Runge-Kutta Nystrom Methods of Orders Three and Four

We investigate the existence of two-stage and three-stage R-stable,P-stable, RL-stable, and dispersively enhanced diagonally implicitRunge-Kutta Nyström methods of orders three and four. Wefirst show that a one-parameter family of two-stage third-orderR-stable diagonally implicit methods exists, and that theirdispersive order is at most four. From this we show that two-stagefourth-order R-stable, and third-order P-stable and RL-stablediagonally implicit methods do not exist. Next we show a two-parameterfamily of three-stage fourth-order R-stable diagonally implicitmethods exists with dispersive order at most four, and thatthis family contains a one-parameter family of P-stable methodsand a unique RL-stable. We also show that a one-parameter familyof fourth-order diagonally implicit methods with dispersiveorder at least six exists, and that they are not R-stable. Wepresent third- and fourth-order R-stable and P-stable methodswith small principal truncation coefficients and discuss howthese methods might be implemented in an efficient integrator.     

How to avoid accuracy and order reduction in Runge–Kutta methods as applied to stiff problems

The solution of stiff problems is frequently accompanied by a phenomenon known as order reduction. The reduction in the actual order can be avoided by applying methods with a fairly high stage order, ideally coinciding with the classical order. However, the stage order sometimes fails to be increased; moreover, this is not possible for explicit and diagonally implicit Runge–Kutta methods. An alternative approach is proposed that yields an effect similar to an increase in the stage order. New implicit and stabilized explicit Runge–Kutta methods are constructed that preserve their order when applied to stiff problems.     

Singly diagonally implicit runge‐kutta method for time‐dependent reaction‐diffusion equation

In this article, an efficient fourth‐order accurate numerical method based on Padé approximation in space and singly diagonally implicit Runge‐Kutta method in time is proposed to solve the time‐dependent one‐dimensional reaction‐diffusion equation. In this scheme, we first approximate the spatial derivative using the second‐order central finite difference then improve it to fourth‐order by applying Padé approximation. A three stage fourth‐order singly diagonally implicit Runge‐Kutta method is then used to solve the resulting system of ordinary differential equations. It is also shown that the scheme is unconditionally stable, and is suitable for stiff problems. Several numerical examples are solved by the scheme and the efficiency and accuracy of the new scheme are compared with two widely used high‐order compact finite difference methods. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1423–1441, 2011     

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.     

Second derivative methods with RK stability

General linear methods are extended to the case in which second derivatives, as well as first derivatives, can be calculated. Methods are constructed of third and fourth order which are A-stable, possess the Runge–Kutta stability property and have a diagonally implicit structure for efficient implementation. AMS subject classification 65L05 G. Hojjati: Corresponding author.     

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.     

Singly Diagonally Implicit Runge–Kutta Methods with an Explicit First Stage

The purpose of this paper is to construct methods for solving stiff ODEs, in particular singular perturbation problems. We consider embedded pairs of singly diagonally implicit Runge–Kutta methods with an explicit first stage (ESDIRKs). Stiffly accurate pairs of order 3/2, 4/3 and 5/4 are constructed.     

A simple technique for constructing two-step Runge-Kutta methods

A technique is proposed for constructing two-step Runge-Kutta methods on the basis of one-step methods. Explicit and diagonally implicit two-step methods with the second or third stage order are examined. Test problems are presented showing that the proposed methods are superior to conventional one-step techniques.     

Two-Stage Stochastic Runge-Kutta Methods for Stochastic Differential Equations

In this paper we discuss two-stage diagonally implicit stochastic Runge-Kutta methods with strong order 1.0 for strong solutions of Stratonovich stochastic differential equations. Five stochastic Runge-Kutta methods are presented in this paper. They are an explicit method with a large MS-stability region, a semi-implicit method with minimum principal error coefficients, a semi-implicit method with a large MS-stability region, an implicit method with minimum principal error coefficients and another implicit method. We also consider composite stochastic Runge-Kutta methods which are the combination of semi-implicit Runge-Kutta methods and implicit Runge-Kutta methods. Two composite methods are presented in this paper. Numerical results are reported to compare the convergence properties and stability properties of these stochastic Runge-Kutta methods.     

Efficient Finite Element Analysis of Inelastic Structures with Iterative Solvers

This article treats the efficient solution of linear systems of equations which arise during the iterative process within the finite element analysis of inelastic structures. For the finite element analysis high order time integration methods and diagonally implicit Runge–Kutta methods (DIRK), in combination with an inexact Multilevel–Newton algorithm (MLNA) are applied. Up to 80% of the total computation time is spent by the solver for the linear systems, which suggests investigating this process. Two simple strategies to speed up the solution of the linear systems are described. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Exploiting structure in the construction of DIMSIMs

We describe the structure of the nonlinear system for the coefficients of diagonally implicit multistage integration methods for ordinary differential equations. This structure is then utilized in the search for methods of high order and stage order with a given stability function. New methods were obtained by solving the nonlinear systems by state-of-the-art software based on least squares minimization.     

A fast singly diagonally implicit runge–kutta method for solving 1D unsteady convection‐diffusion equations

In this article, a fast singly diagonally implicit Runge–Kutta method is designed to solve unsteady one‐dimensional convection diffusion equations. We use a three point compact finite difference approximation for the spatial discretization and also a three‐stage singly diagonally implicit Runge–Kutta (RK) method for the temporal discretization. In particular, a formulation evaluating the boundary values assigned to the internal stages for the RK method is derived so that a phenomenon of the order of the reduction for the convergence does not occur. The proposed scheme not only has fourth‐order accuracy in both space and time variables but also is computationally efficient, requiring only a linear matrix solver for a tridiagonal matrix system. It is also shown that the proposed scheme is unconditionally stable and suitable for stiff problems. Several numerical examples are solved by the new scheme and the numerical efficiency and superiority of it are compared with the numerical results obtained by other methods in the literature. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 788–812, 2014     

Three-stage Stiffly Accurate Runge-Kutta Methods for Stiff Stochastic Differential Equations

In this paper we discuss diagonally implicit and semi-implicit methods based on the three-stage stiffly accurate Runge-Kutta methods for solving Stratonovich stochastic differential equations（SDEs）.Two methods,a three-stage stiffly accurate semi-implicit（SASI3） method and a three-stage stiffly accurate diagonally implicit （SADI3） method,are constructed in this paper.In particular,the truncated random variable is used in the implicit method.The stability properties and numerical results show the effectiveness of these methods in the pathwise approximation of stiff SDEs.     

A-stable diagonally implicit Runge-Kutta-Nyström methods for parallel computers

In this paper, we study diagonally implicit Runge-Kutta-Nyström methods (DIRKN methods) for use on parallel computers. These methods are obtained by diagonally implicit iteration of fully implicit Runge-Kutta-Nyström methods (corrector methods). The number of iterations is chosen such that the method has the same order of accuracy as the corrector, and the iteration parameters serve to make the method at least A-stable. Since a large number of the stages can be computed in parallel, the methods are very efficient on parallel computers. We derive a number of A-stable, strongly A-stable and L-stable DIRKN methods of orderp withs ^* (p) sequential, singly diagonal-implicit stages wheres ^*(p)=[(p+1)/2] ors ^* (p)=[(p+1)/2]+1,[°] denoting the integer part function.These investigations were supported by the University of Amsterdam with a research grant to enable the author to spend a total of two years in Amsterdam.     

Automatic step size and order control in implicit one-step extrapolation methods

A theory is presented for implicit one-step extrapolation methods for ordinary differential equations. The computational schemes used in such methods are based on the implicit Runge-Kutta methods. An efficient implementation of implicit extrapolation is based on the combined step size and order control. The emphasis is placed on calculating and controlling the global error of the numerical solution. The aim is to achieve the user-prescribed accuracy in an automatic mode (ignoring round-off errors). All the theoretical conclusions of this paper are supported by the numerical results obtained for test problems.     

Highest possible order of algebraically stable diagonally implicit runge-kutta methods

We prove that the highest possible order of an algebraically stable diagonally implicit RK-method isfour; the highest possible order of a circle contractive singly diagonally implicit RK-method isfour; the highest possible order of a circle contractive diagonally implicit RK-method issix.     

A nonlinear optimization approach to the construction of general linear methods of high order

We describe the construction of diagonally implicit multistage integration methods of order and stage order p = q = 7 and p = q = 8 for ordinary differential equations. These methods were obtained using state-of-the-art optimization methods, particularly variable-model trust-region least-squares algorithms.     

Factorized SM-stable two-level schemes

Additional requirements for unconditionally stable schemes were formulated by analyzing higher order accurate difference schemes in time as applied to boundary value problems for second-order parabolic equations. These requirements concern the inheritance of the basic properties of the differential problem and lead to the concept of an SM-stable difference scheme. An earlier distinguished class of SM-stable schemes consists of the schemes based on various Padé approximations. The computer implementation of such higher order accurate schemes deserves special consideration because certain matrix polynomials must be inverted at each new time level. Factorized SM-stable difference schemes are constructed that can be interpreted as diagonally implicit Runge-Kutta methods.     

Numerical solution of a problem in the theory of epidemics

We propose a numerical algorithm for a model of the spread of infection in the theory of epidemics. This model involves a threshold for becoming infective and leads to a system of delay-differential equations with the delay function which depends on the values of the unknowns over an interval. The numerical algorithm is based on diagonally implicit multistage integration formulas with stage order equal to the order of the method. This makes possible the efficient evaluation of past values to the accuracy compatible with the requested error tolerance. This algorithm is appicable to the general model without any simplifying assumptions on the parameters of the delay-differential system. Numerical results illustrate the effect of varying various parameters of the model on the spread of infection in a constant population.     

High order accurate semi-implicit WENO schemes for hyperbolic balance laws

In this paper we propose a family of well-balanced semi-implicit numerical schemes for hyperbolic conservation and balance laws. The basic idea of the proposed schemes lies in the combination of the finite volume WENO discretization with Roe’s solver and the strong stability preserving (SSP) time integration methods, which ensure the stability properties of the considered schemes [S. Gottlieb, C.-W. Shu, E. Tadmor, Strong stability-preserving high-order time discretization methods, SIAM Rev. 43 (2001) 89-112]. While standard WENO schemes typically use explicit time integration methods, in this paper we are combining WENO spatial discretization with optimal SSP singly diagonally implicit (SDIRK) methods developed in [L. Ferracina, M.N. Spijker, Strong stability of singly diagonally implicit Runge-Kutta methods, Appl. Numer. Math. 58 (2008) 1675-1686]. In this way the implicit WENO numerical schemes are obtained. In order to reduce the computational effort, the implicit part of the numerical scheme is linearized in time by taking into account the complete WENO reconstruction procedure. With the proposed linearization the new semi-implicit finite volume WENO schemes are designed.A detailed numerical investigation of the proposed numerical schemes is presented in the paper. More precisely, schemes are tested on one-dimensional linear scalar equation and on non-linear conservation law systems. Furthermore, well-balanced semi-implicit WENO schemes for balance laws with geometrical source terms are defined. Such schemes are then applied to the open channel flow equations. We prove that the defined numerical schemes maintain steady state solution of still water. The application of the new schemes to different open channel flow examples is shown.