Partitioned half-explicit Runge-Kutta methods for differential-algebraic systems of index 2

A class of half-explicit methods for index 2 differential-algebraic systems in Hessenberg form is proposed, which takes advantage of the partitioned structure of such problems. For this family of methods, which we call partitioned half-explicit Runge-Kutta methods, a better choice in the parameters of the method than for previously available half-explicit Runge-Kutta methods can be made. In particular we construct a family of 6-stage methods of order 5, and determine its parameters (based on the coefficients of the successful explicit Runge-Kutta method DOPRI5) in order to optimize the local error coefficients. Numerical experiments demonstrate the efficiency of this method for the solution of constrained multi-body systems.     

Interpolating Runge-Kutta methods for vanishing delay differential equations

In the numerical solution of delay differential equations by a continuous explicit Runge-Kutta method a difficulty arises when the delay vanishes or becomes smaller than the stepsize the method would like to use. In this situation the standard explicit sequential process of computing the Runge-Kutta stages becomes an implicit process and an iteration scheme must be adopted. We will consider alternative iteration schemes and investigate their order.     

GPG-stability of Runge-Kutta methods for generalized delay differential systems

The GP_G-stability of Runge-Kutta methods for the numerical solutions of the systems of delay differential equations is considered. The stability behaviour of implicit Runge-Kutta methods (IRK) is analyzed for the solution of the system of linear test equations with multiple delay terms. After an establishment of a sufficient condition for asymptotic stability of the solutions of the system, a criterion of numerical stability of IRK with the Lagrange interpolation process is given for any stepsize of the method.     

Second-order stabilized explicit Runge-Kutta methods for stiff problems

Stabilized Runge-Kutta methods (they have also been called Chebyshev-Runge-Kutta methods) are explicit methods with extended stability domains, usually along the negative real axis. They are easy to use (they do not require algebra routines) and are especially suited for MOL discretizations of two- and three-dimensional parabolic partial differential equations. Previous codes based on stabilized Runge-Kutta algorithms were tested with mildly stiff problems. In this paper we show that they have some difficulties to solve efficiently problems where the eigenvalues are very large in absolute value (over 10⁵). We also develop a new procedure to build this kind of algorithms and we derive second-order methods with up to 320 stages and good stability properties. These methods are efficient numerical integrators of very large stiff ordinary differential equations. Numerical experiments support the effectiveness of the new algorithms compared to well-known methods as RKC, ROCK2, DUMKA3 and ROCK4.     

Singly-implicit Runge-Kutta methods for retarded and ordinary differential equations

A continuous singly-implicit Runge-Kutta method is implemented for stiff retarded differential equations. The choice of this implicit Runge-Kutta method is based on stability investigations of wide classes of interpolationintegration schemes. The numerical results show the effectiveness of these methods for both stiff ordinary and retarded differential equations.     

Rational Runge-Kutta methods for solving systems of ordinary differential equations

Some nonlinear methods for solving single ordinary differiential equations are generalized to solve systems of equations. To perform this, a new vector product, compatible with the Samelson inverse of a vector, is defined. Conditions for a given order are derived.     

Fast algebraic methods for interval constraint problems

We describe an effective generic method for solving constraint problems, based on Tarski’s relation algebra, using path-consistency as a pruning technique. We investigate the performance of this method on interval constraint problems. Time performance is affected strongly by the path-consistency calculations, which involve the calculation of compositions of relations. We investigate various methods of tuning composition calculations, and also path-consistency computations. Space performance is affected by the branching factor during search. Reducing this branching factor depends on the existence of ‘nice’ subclasses of the constraint domain. Finally, we survey the statistics of consistency properties of interval constraint problems. Problems of up to 500 variables may be solved in expected cubic time. Evidence is presented that the ‘phase transition’ occurs in the range 6 ≤ n.c ≤15, where n is the number of variables, and c is the ratio of non-trivial constraints to possible constraints. This revised version was published online in June 2006 with corrections to the Cover Date.     

Efficient classes of Runge-Kutta methods for two-point boundary value problems

The standard approach to applying IRK methods in the solution of two-point boundary value problems involves the solution of a non-linear system ofn×s equations in order to calculate the stages of the method, wheren is the number of differential equations ands is the number of stages of the implicit Runge-Kutta method. For two-point boundary value problems, we can select a subset of the implicit Runge-Kutta methods that do not require us to solve a non-linear system; the calculation of the stages can be done explicitly, as is the case for explicit Runge-Kutta methods. However, these methods have better stability properties than the explicit Runge-Kutta methods. We have called these new formulas two-point explicit Runge-Kutta (TPERK) methods. Their most important property is that, because their stages can be computed explicity, the solution of a two-point boundary value problem can be computed more efficiently than is possible using an implicit Runge-Kutta method. We have also developed a symmetric subclass of the TPERK methods, called ATPERK methods, which exhibit a number of useful properties.     

Preconditioning in parallel Runge-Kutta methods for stiff initial value problems

From a theoretical point of view, Runge-Kutta methods of collocation type belong to the most attractive step-by-step methods for integrating stiff problems. These methods combine excellent stability features with the property of superconvergence at the step points. Like the initial-value problem itself, they only need the given initial value without requiring additional starting values, and therefore, are a natural discretization of the initial-value problem. On the other hand, from a practical point of view, these methods have the drawback of requiring in each step the solution of a system of equations of dimension sd, s and d being the number of stages and the dimension of the initial-value problem, respectively. In contrast, linear multistep methods, the main competitor of Runge-Kutta methods, require the solution of systems of dimension d. However, parallel computers have changed the scene and have motivated us to design parallel iteration methods for solving the implicit systems in such a way that the resulting methods become efficient step-by-step methods for integrating stiff initial-value problems.     

Characterization of B-convergent Runge-Kutta methods for strictly dissipative initial value problems

The property of algebraic stability turns out to be a sufficient and necessary condition for a Runge-Kutta method to beB-convergent on the class of problems with a negative one-sided Lipschitz constant.     

On modified Runge-Kutta trees and methods

Modified Runge-Kutta (mRK) methods can have interesting properties as their coefficients may depend on the step length. By a simple perturbation of very few coefficients we may produce various function-fitted methods and avoid the overload of evaluating all the coefficients in every step. It is known that, for Runge-Kutta methods, each order condition corresponds to a rooted tree. When we expand this theory to the case of mRK methods, some of the rooted trees produce additional trees, called mRK rooted trees, and so additional conditions of order. In this work we present the relative theory including a theorem for the generating function of these additional mRK trees and explain the procedure to determine the extra algebraic equations of condition generated for a major subcategory of these methods. Moreover, efficient symbolic codes are provided for the enumeration of the trees and the generation of the additional order conditions. Finally, phase-lag and phase-fitted properties are analyzed for this case and specific phase-fitted pairs of orders 8(6) and 6(5) are presented and tested.     

On symmetric Runge-Kutta methods of high order

The usual characterization of symmetry for Runge-Kutta methods is that given by Stetter. In this paper an equivalent characterization of symmetry based on theW-transformation of Hairer and Wanner is proposed. Using this characterization it is simple to show symmetry for some well-known classes of high order Runge-Kutta methods which are based on quadrature formulae. It can also be used to construct a one-parameter family of symmetric and algebraically stable Runge-Kutta methods based on Lobatto quadrature. Methods constructed in this way and presented in this paper extend the known class of implicit Runge-Kutta methods of high order.     

Preconditioners for Schwarz relaxation methods applied to differential algebraic equations

In this paper, the authors investigate the ability of Schwarz relaxation (SR) methods to deal with large systems of differential algebraic equations (DAEs) and assess their respective efficiency. Since the number of iterations required to achieve convergence of the classical SR method is strongly related to the number of subdomains and the time step size, two new preconditioning techniques are here developed. A preconditioner based on a correction using the algebraic equations is first introduced and leads to a number of iterations independent on the number of subdomains. A second preconditioner based on a correction using the Schur complement matrix makes the convergence independent on both the number of subdomains and the integration step size. Application on European electricity network is presented to outline the performance, efficiency, and robustness of the proposed preconditioning techniques for the solution of DAEs.     

On the use of parallel processors for implicit Runge-Kutta methods

An iteration scheme, for solving the non-linear equations arising in the implementation of implicit Runge-Kutta methods, is proposed. This scheme is particularly suitable for parallel computation and can be applied to any method which has a coefficient matrixA with all eigenvalues real (and positive). For such methods, the efficiency of a modified Newton scheme may often be improved by the use of a similarity transformation ofA but, even when this is the case, the proposed scheme can have advantages for parallel computation. Numerical results illustrate this. The new scheme converges in a finite number of iterations when applied to linear systems of differential equations, achieving this by using the nilpotency of a strictly lower triangular matrixS ^?1 AS — Λ, with Λ a diagonal matrix. The scheme reduces to the modified Newton scheme whenS ^?1 AS is diagonal.A convergence result is obtained which is applicable to nonlinear stiff systems.     

A geometric index reduction method for implicit systems of differential algebraic equations

This paper deals with the index reduction problem for the class of quasi-regular DAE systems. It is shown that any of these systems can be transformed to a generically equivalent first order DAE system consisting of a single purely algebraic (polynomial) equation plus an under-determined ODE (a differential Kronecker representation) in as many variables as the order of the input system. This can be done by means of a Kronecker-type algorithm with bounded complexity.     

On the algebraic structure of combinatorial problems

We describe a general algebraic formulation for a wide range of combinatorial problems including

Full-size image

and In this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. This result is used to identify tractable subproblems of , and to provide a simple test to establish whether a given set of Boolean relations gives rise to one of these tractable subproblems.     

On an energy minimizing basis for algebraic multigrid methods

This paper is devoted to the study of an energy minimizing basis first introduced in Wan, Chan and Smith (2000) for algebraic multigrid methods. The basis will be first obtained in an explicit and compact form in terms of certain local and global operators. The basis functions are then proved to be locally harmonic functions on each coarse grid element. Using these new results, it is illustrated that this basis can be numerically obtained in an optimal fashion. In addition to the intended application for algebraic multigrid method, the energy minimizing basis may also be applied for numerical homogenization.