Reducing and monitoring round-off error propagation for symplectic implicit Runge-Kutta schemes

We propose an implementation of symplectic implicit Runge-Kutta schemes for highly accurate numerical integration of non-stiff Hamiltonian systems based on fixed point iteration. Provided that the computations are done in a given floating point arithmetic, the precision of the results is limited by round-off error propagation. We claim that our implementation with fixed point iteration is near-optimal with respect to round-off error propagation under the assumption that the function that evaluates the right-hand side of the differential equations is implemented with machine numbers (of the prescribed floating point arithmetic) as input and output. In addition, we present a simple procedure to estimate the round-off error propagation by means of a slightly less precise second numerical integration. Some numerical experiments are reported to illustrate the round-off error propagation properties of the proposed implementation.     

Family of symplectic implicit Runge-Kutta formulae

A family of formulae for the sympletic IRK method is investigated. Specifically, focus is given to general solutions for formula parameters of IRK under the symplectic and the order conditions. Examples of such formulae are constructed for up to three stages.     

Rational approximations by implicit Runge-Kutta schemes

Ehle [3] has pointed out that then-stage implicit Runge-Kutta (IRK) methods due to Butcher [1] areA-stable in the definition of Dahlquist [2] because they effect the operationR(Ah) whereR(μ) is the diagonal Padé approximation toe ^µ. The purpose of this note is to point out that ifR(μ)=P(μ)/Q(μ) is a rational polynomial whosen poles are distinct and nonzero, and if degreeP(μ)≦degreeQ(μ)=n, then ann-stage IRK method applied toy=A y can be used for the operation $$y^{n + 1} = R(Ah)y^n $$ This will no longer be of order 2n, nor necessarily the same order as the approximation ofR(Ah) toe ^Ah. However, if any particularly useful integration formsR can be found, they can be performed by the IRK method.     

The implementation of Runge-Kutta implicit processes

The application ofA-stable, implicit Runge-Kutta processes to the solution of stiff systems of ordinary differential equations is discussed, and an iterative procedure for solving the resulting nonlinear system of equations is suggested.     

An improved approximate Newton method for implicit Runge-Kutta formulas

Implicit Runge-Kutta (IRK) methods (such as the s-stage Radau IIA method with s=3,5, or 7) for solving stiff ordinary differential equation systems have excellent stability properties and high solution accuracy orders, but their high computing costs in solving their nonlinear stage equations have seriously limited their applications to large scale problems. To reduce such a cost, several approximate Newton algorithms were developed, including a commonly used one called the simplified Newton method. In this paper, a new approximate Jacobian matrix and two new test rules for controlling the updating of approximate Jacobian matrices are proposed, yielding an improved approximate Newton method. Theoretical and numerical analysis show that the improved approximate Newton method can significantly improve the convergence and performance of the simplified Newton method.     

On the implementation of implicit Runge-Kutta methods

The modified Newton iterations in the implementation of ans stage implicit Runge-Kutta method for ann dimensional differential equation system require 2s ³ n ³/3+O(n ²) operations for theLU factorisations and 2s ² n ²+O(n) operations for the back substitutions. This paper describes a method for transforming the linear system so as to reduce these operation counts.     

Three-and four-step implicit absolutely stable fourth-order Runge-Kutta schemes

Two types of implicit fourth-order Runge-Kutta schemes are constructed for first-order ordinary differential equations, multidimensional transfer equations, and compressible gas equations. The absolute stability of the schemes is proved by applying the principle of frozen coefficients. Adaptive artificial viscosity ensuring good time convergence and oscillations damping near discontinuities is used in solving gas dynamics equations. The comparative efficiency of the schemes is illustrated by numerical results obtained for compressible gas flows.     

Newton iterations in implicit time-stepping scheme for differential linear complementarity systems

We propose a generalized Newton method for solving the system of nonlinear equations with linear complementarity constraints in the implicit or semi-implicit time-stepping scheme for differential linear complementarity systems (DLCS). We choose a specific solution from the solution set of the linear complementarity constraints to define a locally Lipschitz continuous right-hand-side function in the differential equation. Moreover, we present a simple formula to compute an element in the Clarke generalized Jacobian of the solution function. We show that the implicit or semi-implicit time-stepping scheme using the generalized Newton method can be applied to a class of DLCS including the nondegenerate matrix DLCS and hidden Z-matrix DLCS, and has a superlinear convergence rate. To illustrate our approach, we show that choosing the least-element solution from the solution set of the Z-matrix linear complementarity constraints can define a Lipschitz continuous right-hand-side function with a computable Lipschitz constant. The Lipschitz constant helps us to choose the step size of the time-stepping scheme and guarantee the convergence.     

Computation of order conditions for symplectic partitioned Runge-Kutta schemes with application to optimal control

We derive order conditions for the discretization of (unconstrained) optimal control problems, when the scheme for the state equation is of Runge-Kutta type. This problem appears to be essentially the one of checking order conditions for symplectic partitioned Runge-Kutta schemes. We show that the computations using bi-coloured trees are naturally expressed in this case in terms of oriented free tree. This gives a way to compute them by an appropriate computer program. This study is supported by CNES and ONERA, in the framework of the CNES fellowship of the second author.     

An efficient scheme for the implementation of implicit Runge-Kutta methods

A scheme is proposed for solving nonlinear algebraic equations arising in the implementation of the implicit Runge-Kutta methods. In contrast to the available schemes, not only the starting values of the variables but also those of the derivatives are predicted. This makes it possible to reduce the number of evaluations of the function (the right-hand side) at each implicit stage without significantly reducing the accuracy of integration.     

Some linear stability results for iterative schemes for implicit Runge-Kutta methods

This article examines stability properties of some linear iterative schemes that have been proposed for the solution of the nonlinear algebraic equations arising in the use of implicit Runge-Kutta methods to solve a differential systemx =f(x). Each iteration step requires the solution of a set of linear equations, with constant matrixI –hJ, whereJ is the Jacobian off evaluated at some fixed point. It is shown that the stability properties of a Runge-Kutta method can be preserved only if is an eigenvalue of the coefficient matrixA. SupposeA has minimal polynomial (x – ) ^m p(x),p() 0. Then stability can be preserved only if the order of the method is at mostm + 2 (at mostm + 1 except for one case).This work was partially supported by a grant from the Science and Engineering Research Council.     

Stability of iterations of symplectic transformations

Novosibirsk. Translated from Sibirskii Matematicheskii Zhurnal, Vol. 30, No. 1, pp. 70–81, January–February, 1989.     

A sixth order diagonally implicit symmetric and symplectic Runge-Kutta method for solving Hamiltonian systems

The paper is concerned with construction of symmetric and symplectic Runge-Kutta methods for Hamiltonian systems. Based on the symplectic and symmetrical properties, a sixth-order diagonally implicit symmetric and symplectic Runge-Kutta method with seven stages is presented, the proposed method proved to be P-stable. Numerical experiments with some Hamiltonian oscillatory problems are presented to show the proposed method is as competitive as the existing Runge-Kutta methods in scientic literature.     

High order starting iterates for implicit Runge-Kutta methods: an improvement for variable-step symplectic integrators

When dealing with implicit Runge–Kutta methods, the equationsdefining the stages are usually solved by iterative methods.The closer the first iterate is to the solution, the fewer iterationsare required. In this paper the author presents and analysesnew high order algorithms to compute such initial iterates.Numerical experiments are given to illustrate the performanceof the new procedures when combined with a variable-step symplecticintegrator.     

On implicit Runge-Kutta methods with higher derivatives

Two families of implicit Runge-Kutta methods with higher derivatives are (re-)considered generalizing classical Runge-Kutta methods of Butcher type and f Ehle type. For generalized Butcher methods the characteristic functionG() is represented by means of the node polynomial directly, thereby showing that in methods of maximum order,G() is connected withs-orthogonal polynomials in exactly the same way as Padé approximations in the classical case.     

The non-existence of symplectic multi-derivative Runge-Kutta methods

A sufficient condition for the symplecticness ofq-derivative Runge-Kutta methods has been derived by F. M. Lasagni. In the present note we prove that this condition can only be satisfied for methods withq1, i.e., for standard Runge-Kutta methods. We further show that the conditions of Lasagni are also necessary for symplecticness so that no symplectic multi-derivative Runge-Kutta method can exist.This research has been supported by project PB89-0351 (Dirección General de Investigación Científica y Técnica) and by project No. 20-32354.91 of Swiss National Science Foundation.     

On theA-stability of implicit Runge-Kutta processes

A new technique to calculate the characteristic functions and to examine theA-stability of implicit Runge-Kutta processes is presented. This technique is based on a direct algebraic approach and an application of theC-polynomial theory of Nørsett. New processes are suggested. These processes can be exponentially fitted in anA-stable manner.     

Efficient implementation of WENO schemes to nonuniform meshes

Most of the standard papers about the WENO schemes consider their implementation to uniform meshes only. In that case the WENO reconstruction is performed efficiently by using the algebraic expressions for evaluating the reconstruction values and the smoothness indicators from cell averages. The coefficients appearing in these expressions are constant, dependent just on the scheme order, not on the mesh size or the reconstruction function values, and can be found, for example, in Jiang and Shu (J Comp Phys 126:202–228, 1996). In problems where the geometrical properties must be taken into account or the solution has localized fine scale structure that must be resolved, it is computationally efficient to do local grid refinement. Therefore, it is also desirable to have numerical schemes, which can be applied to nonuniform meshes. Finite volume WENO schemes extend naturally to nonuniform meshes although the reconstruction becomes quite complicated, depending on the complexity of the grid structure. In this paper we propose an efficient implementation of finite volume WENO schemes to nonuniform meshes. In order to save the computational cost in the nonuniform case, we suggest the way for precomputing the coefficients and linear weights for different orders of WENO schemes. Furthermore, for the smoothness indicators that are defined in an integral form we present the corresponding algebraic expressions in which the coefficients obtained as a linear combination of divided differences arise. In order to validate the new implementation, resulting schemes are applied in different test examples.      

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.     

Periodic solutions of difference Runge-Kutta schemes

Translated from Matematicheskie Zametki, Vol. 49, No. 6, pp. 92–97, June, 1991.