A composition law for Runge-Kutta methods applied to index-2 differential-algebraic equations

This paper presents a new composition law for Runge-Kutta methods when applied to index-2 differential-algebraic systems. Applications of this result to the study of the order of composite methods and of symmetric methods are given.     

A multirate time stepping strategy for stiff ordinary differential equations

To solve ODE systems with different time scales which are localized over the components, multirate time stepping is examined. In this paper we introduce a self-adjusting multirate time stepping strategy, in which the step size for a particular component is determined by its own local temporal variation, instead of using a single step size for the whole system. We primarily consider implicit time stepping methods, suitable for stiff or mildly stiff ODEs. Numerical results with our multirate strategy are presented for several test problems. Comparisons with the corresponding single-rate schemes show that substantial gains in computational work and CPU times can be obtained. AMS subject classification (2000)  65L05, 65L06, 65L50     

Highest order multistep formula for solving index-2 differential-algebraic equations

In this paper, the maximum order of linear multistep methods (LMM) for solving semi-explict index-2 differential-algebraic equations (DAEs) is discussed. For ak-step formula, we prove that the orders of differential variables and algebraic variables do not exceedk+1 andk respectively whenk is odd and both orders do not exceedk whenk is even. In order to achieve the orderk+1, the coefficients in the formula should satisfy some strict conditions. Examples which can achieve the maximum order are given fork=1,2,3. Especially, a class of multistep formula fork=3, not appearing in the literature before, are proposed. Further, a class of predictor-corrector methods are constructed to remove the restriction of the infinite stability. They give the same maximum order as that for solving ODEs. Numerical tests confirm the theoretical results. This work was partially supported by the National Natural Science Foundation of China.     

On index-2 linear implicit difference equations

This paper deals with an index-2 notion for linear implicit difference equations (LIDEs) and with the solvability of initial value problems (IVPs) for index-2 LIDEs. Besides, the cocycle property as well as the multiplicative ergodic theorem of Oseledets type are also proved.     

A note on bifurcation points for index-1 differential-algebraic problems

The arclength continuation method is proposed for index-1 DAEs with singular points. In particular, the cusp points, the tangency points and equilibrium points are investigated. The numerical iterative matrix is studied at a singular point. The numerical examples are given to illustrate the robustness of the continuation method.     

Jacobi spectral solution for integral algebraic equations of index-2

This paper is concerned with obtaining the approximate solution of a class of semi-explicit Integral Algebraic Equations (IAEs) of index-2. A Jacobi collocation method including the matrix-vector multiplication representation is proposed for the IAEs of index-2. A rigorous analysis of error bound in weighted L² norm is also provided which theoretically justifies the spectral rate of convergence while the kernels and the source functions are sufficiently smooth. Results of several numerical experiments are presented which support the theoretical results.     

Wavelet-based adaptive grids for multirate partial differential-algebraic equations

The mathematical model of electric circuits yields systems of differential-algebraic equations (DAEs). In radio frequency applications, a multivariate model of oscillatory signals transforms the DAEs into a system of multirate partial differential-algebraic equations (MPDAEs). Considering quasiperiodic signals, an approach based on a method of characteristics yields efficient numerical schemes for the MPDAEs in time domain. If additionally digital signal structures occur, an adaptive grid is required to achieve the efficiency of the technique. We present a strategy applying a wavelet transformation to construct a mesh for resolving steep gradients in respective signals. Consequently, we employ finite difference methods to determine an approximative solution of characteristic systems in according grid points. Numerical simulations demonstrate the performance of the adaptive grid generation, where radio frequency signals with digital structures are resolved.     

Numerical solutions of index-1 differential algebraic equations can be computed in polynomial time

The cost of solving an initial value problem for index-1 differential algebraic equations to accuracy ɛ is polynomial in ln(1/ɛ). This cost is obtained for an algorithm based on the Taylor series method for solving differential algebraic equations developed by Pryce. This result extends a recent result by Corless for solutions of ordinary differential equations. The results of the standard theory of information-based complexity give exponential cost for solving ordinary differential equations, being based on a different model.     

Polynomial chaos for multirate partial differential algebraic equations with random parameters

In radio frequency applications, a multivariate model yields an efficient representation of signals with amplitude modulation and/or frequency modulation. Periodic boundary value problems of multirate partial differential algebraic equations (MPDAEs) have to be solved to reproduce the quasiperiodic signals. Typically, technical parameters appear in the system, which may exhibit some uncertainty. Substitution by random variables results in a corresponding stochastic model. We apply the technique of the generalised polynomial chaos to obtain according solutions. A Galerkin approach yields larger coupled systems of MPDAEs. We analyse the properties of the coupled systems with respect to the original formulations. Thereby, we focus on the case of frequency modulation, since the case of amplitude modulation alone is straightforward.     

Global error estimation for index-1 and -2 DAEs

In this paper, we consider the extension of three classical ODE estimation techniques (Richardson extrapolation, Zadunaisky's technique and solving for the correction) to DAEs. Their convergence analysis is carried out for semi-explicit index-1 DAEs solved by a wide set of Runge-Kutta methods. Experimentation of the estimation techniques with RADAU5 is also presented: their behaviour for index-1 and -2 problems, and for variable step size integration is investigated. This revised version was published online in June 2006 with corrections to the Cover Date.     

Existence and uniqueness of optimal solutions for multirate partial differential algebraic equations

The numerical simulation of electric circuits including multirate signals can be done by a model based on partial differential algebraic equations. In the case of frequency modulated signals, a local frequency function appears as a degree of freedom in the model. Thus the determination of a solution with a minimum amount of variation is feasible, which allows for resolving on relatively coarse grids. We prove the existence and uniqueness of the optimal solutions in the case of initial-boundary value problems as well as biperiodic boundary value problems. The minimisation problems are also investigated and interpreted in the context of optimal control. Furthermore, we construct a method of characteristics for the computation of optimal solutions in biperiodic problems. Numerical simulations of test examples are presented.     

Stability and bifurcation properties of index-1 DAEs

It is well known that an equilibrium of a semi-explicit, index-1 differential-algebraic equation under a parameter variation may encounter the singularity manifold. It is a generic property of this encounter that one eigenvalue of the linear stability mapping associated with the equilibrium will pass from one half of the complex plane to the other without passing through the imaginary axis. This is known as singularity-induced bifurcation and an equivalent result is proven in this paper. While this property is generic, it is shown how more than one eigenvalue can diverge in an analogous manner, with applications in electrical power systems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Enclosure of all index-1 saddle points of general nonlinear functions

Transition states (index-1 saddle points) play a crucial role in determining the rates of chemical transformations but their reliable identification remains challenging in many applications. Deterministic global optimization methods have previously been employed for the location of transition states (TSs) by initially finding all stationary points and then identifying the TSs among the set of solutions. We propose several regional tests, applicable to general nonlinear, twice continuously differentiable functions, to accelerate the convergence of such approaches by identifying areas that do not contain any TS or that may contain a unique TS. The tests are based on the application of the interval extension of theorems from linear algebra to an interval Hessian matrix. They can be used within the framework of global optimization methods with the potential of reducing the computational time for TS location. We present the theory behind the tests, discuss their algorithmic complexity and show via a few examples that significant gains in computational time can be achieved by using these tests.     

A critically loaded multirate link with trunk reservation

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type ί customers requiring A _ί servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type ί customer is accepted only if there are Rί(⩾A_ί ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R ₁,..., R _K-1 remain bounded, while R _K ^N ←∞ and R _K ^N /√N ← 0 as N ← ∞. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Parallel collocation solution of index-1 BVP-DAEs arising from constrained optimal control problems

The indirect solution of constrained optimal control problems gives rise to two-point boundary value problems (BVPs) that involve index-1 differential-algebraic equations (DAEs) and inequality constraints. This paper presents a parallel collocation algorithm for the solution of these inequality constrained index-1 BVP-DAEs. The numerical algorithm is based on approximating the DAEs using piecewise polynomials on a nonuniform mesh. The collocation method is realized by requiring that the BVP-DAE be satisfied at Lobatto points within each interval of the mesh. A Newton interior-point method is used to solve the collocation equations, and maintain feasibility of the inequality constraints. The implementation of the algorithm involves: (i) parallel evaluation of the collocation equations; (ii) parallel evaluation of the system Jacobian; and (iii) parallel solution of a boarded almost block diagonal (BABD) system to obtain the Newton search direction. Numerical examples show that the parallel implementation provides significant speedup when compared to a sequential version of the algorithm.     

Analysis of a multirate theta-method for stiff ODEs

This paper contains a study of a simple multirate scheme, consisting of the θ-method with one level of temporal local refinement. Issues of interest are local accuracy, propagation of interpolation errors and stability. The theoretical results are illustrated by numerical experiments, including results for more levels of refinement with automatic partitioning.     

A numerical C1-shadowing result for retarded functional differential equations

The aim of the present paper is to give a numerical C¹-shadowing between the exact solutions of a functional differential equation and its numerical approximations. The shadowing result is obtained by comparing exact solutions with numerical approximation which do not share the same initial value. Behavior of stable manifolds of functional differential equations under numerics will follow from the shadowing result.     

A high-order exponential scheme for solving 1D unsteady convection-diffusion equations

In this paper, a high-order exponential (HOE) scheme is developed for the solution of the unsteady one-dimensional convection-diffusion equation. The present scheme uses the fourth-order compact exponential difference formula for the spatial discretization and the (2,2) Padé approximation for the temporal discretization. The proposed scheme achieves fourth-order accuracy in temporal and spatial variables and is unconditionally stable. Numerical experiments are carried out to demonstrate its accuracy and to compare it with analytic solutions and numerical results established by other methods in the literature. The results show that the present scheme gives highly accurate solutions for all test examples and can get excellent solutions for convection dominated problems.     

Construction of a multirate RODAS method for stiff ODEs

Multirate time stepping is a numerical technique for efficiently solving large-scale ordinary differential equations (ODEs) with widely different time scales localized over the components. This technique enables one to use large time steps for slowly varying components, and small steps for rapidly varying ones. Multirate methods found in the literature are normally of low order, one or two. Focusing on stiff ODEs, in this paper we discuss the construction of a multirate method based on the fourth-order RODAS method. Special attention is paid to the treatment of the refinement interfaces with regard to the choice of the interpolant and the occurrence of order reduction. For stiff, linear systems containing a stiff source term, we propose modifications for the treatment of the source term which overcome order reduction originating from such terms and which we can implement in our multirate method.     

A Runge-Kutta method for index 1 stochastic differential-algebraic equations with scalar noise

The paper deals with the numerical treatment of stochastic differential-algebraic equations of index one with a scalar driving Wiener process. Therefore, a particularly customized stochastic Runge-Kutta method is introduced. Order conditions for convergence with order 1.0 in the mean-square sense are calculated and coefficients for some schemes are presented. The proposed schemes are stiffly accurate and applicable to nonlinear stochastic differential-algebraic equations. As an advantage they do not require the calculation of any pseudo-inverses or projectors. Further, the mean-square stability of the proposed schemes is analyzed and simulation results are presented bringing out their good performance.