Convergence Results of One-Leg and Linear Multistep Methods for Multiply Stiff Singular Perturbation Problems

One-leg methods and linear multistep methods are two class of important numerical methods applied to stiff initial value problems of ordinary differential equations. The purpose of this paper is to present some convergence results of A-stable one-leg and linear multistep methods for one-parameter multiply stiff singular perturbation problems and their corresponding reduced problems which are a class of stiff differential-algebraic equations. Received April 14, 2000; revised June 30, 2000     

Order results for Krylov-W-methods

We consider ROW-methods for stiff initial value problems, where the stage equations are solved by Krylov techniques. By using a certain ‘multiple Arnoldi process’ over all stages the order of the fully-implicit one-step scheme can be preserved with low Krylov dimensions. Explicit estimates for minimal order preserving dimensions are derived. They depend on the parameters of the method only, not on the dimension of the ODE. Stability restrictions usually require larger dimensions, of course, but this can be done adaptively. These results justify to adopt the step size control of the underlying ROW-method. The widely used ROW-methods of order 4 are discussed in detail and numerical illustrations are given. For the special class of semilinear systems with stiffness in a constant linear part we establish the order 2 of B-consistency for these Krylov-W-methods. This work was supported by the Deutsche Forschungsgemeinschaft.     

General linear methods for ordinary differential equations

General linear methods were introduced as the natural generalizations of the classical Runge–Kutta and linear multistep methods. They have potential applications, especially for stiff problems. This paper discusses stiffness and emphasises the need for efficient implicit methods for the solution of stiff problems. In this context, a survey of general linear methods is presented, including recent results on methods with the inherent RK stability property.     

Stabilized starting algorithms for collocation Runge-Kutta methods

In this paper, we propose a technique to stabilize some starting algorithms often used in the Newton-type iterations appearing when collocation Runge-Kutta methods are applied to solve stiff initial value problems. By following the ideas given in [1], we analyze the order (classical and stiff) of the new starting algorithms and pay special attention to their error amplifying functions. From the computational point of view, the new algorithms require the solution of an additional linear system per integration step, but as shown in the numerical experiments, this extra cost is compensated in most of the problems by their better stability properties.     

A Semi-smooth Newton Method for Regularized State-constrained Optimal Control of the Navier-Stokes Equations

In this paper, we study semi-smooth Newton methods for the numerical solution of regularized pointwise state-constrained optimal control problems governed by the Navier-Stokes equations. After deriving an appropriate optimality system for the original problem, a class of Moreau-Yosida regularized problems is introduced and the convergence of their solutions to the original optimal one is proved. For each regularized problem a semi-smooth Newton method is applied and its local superlinear convergence verified. Finally, selected numerical results illustrate the behavior of the method and a comparison between the max-min and the Fischer-Burmeister as complementarity functionals is carried out.     

Sixth order non-dissipative C 1 spline collocation method for oscillatory ordinary initial value problems

In this paper we construct a global method, based on quintic C ¹-spline, for the integration of first order ordinary initial value problems (IVPs) including stiff equations and those possessing oscillatory solutions as well. The method will be shown to be of order six and in particular is A-stable. Attention is also paid for the phase error (or dispersion) and it is proved that the method is dispersive and has dispersion order six with small phase-lag (compared with the extant methods having the same order (cf. [7])). Moreover, the method may be regarded as a continuous extension of the closed four-panel Newton–Cotes formula (NC4) (typically it is a continuous extension of an implicit Runge–Kutta method). In additiona priori error estimates, in the uniform norm, together with illustrative test examples will also be presented.     

Asymptotic error expansions for stiff equations: Applications

In a series of foregoing papers we have studied the structure of the global discretization error for the implicit Euler scheme and the implicit midpoint and trapezoidal rules applied to a general class of nonlinear stiff initial value problems. Full asymptotic error expansions (in the conventional sense) exist only in special situations; for the general case, asymptotic expansions in a weaker sense have been derived. In the present paper we demonstrate how these results can be used for an analysis of acceleration techniques applied to stiff problems. In particular, extrapolation and defect correction algorithms are considered. Various numerical results are presented and discussed.     

Computation of travelling wave solutions of scalar conservation laws with a stiff source term

In this paper we propose a nonoscillatory numerical technique to compute the travelling wave solution of scalar conservation laws with a stiff source term. This procedure is based on the dynamical behavior described by the associated stationary ODE and it reduces/avoids numerical errors usually encountered with these problems, i.e., spurious oscillations and incorrect wave propagation speed. We combine this treatment with either the first order Lax-Friedrichs scheme or the second order Nessyahu-Tadmor scheme. We have tested several model problems by LeVeque and Yee for which the stiffness coefficient can be increased. We have also tested a problem with a nonlinear flux and a discontinuous source term.     

Exponential fitting BDF-Runge-Kutta algorithms

In other papers, the authors presented exponential fitting methods of BDF type. Now, these methods are used to derive some BDF-Runge-Kutta type formulas (of second-, third- and fourth-order), capable of the exact integration (with only round-off errors) of differential equations whose solutions are linear combinations of an exponential with parameter A and ordinary polynomials. Theorems of the truncation error reveal the good behavior of the new methods for stiff problems. Plots of their absolute stability regions that include the whole of the negative real axis are provided. Different procedures to find the parameter of the method are proposed, using these techniques there will not be necessary to compute the exponential matrix at each step, even when nonlinear problems are integrated. Numerical examples underscore the efficiency of the proposed codes, especially when they are integrating stiff problems.     

Numerical integration of semidiscrete evolution systems

Methods and algorithms for integrating initial value systems are examined. Of particular interest is efficient and accurate numerical integration of systems of ordinary differential equations that arise on semidiscrete spatial differencing or finite element projection for evolution problems characterized by partial differential equations. Integration schemes for general systems are described. Stiff and oscillatory systems are considered and these motivate selection of specific types of algorithms for certain problem classes. For example, we show that Runge-Kutta methods with extended regions of stability are particularly efficient for moderately stiff dissipative systems derived from parabolic transport equations. The theoretical developments of an earlier paper [1] determine bounds on stiffness and stability and may be used to examine the stiff dissipative or oscillatory nature of the system qualitatively. Order control and stepsize adjustment in variable-order, variable-step algorithms are compared for several integrators applied to stiff and nonstiff initial-value systems arising from representative parabolic evolution problems.     

An exponential time differencing method for the nonlinear Schrödinger equation

The spectral methods offer very high spatial resolution for a wide range of nonlinear wave equations, so, for the best computational efficiency, it should be desirable to use also high order methods in time but without very strict restrictions on the step size by reason of numerical stability. In this paper we study the exponential time differencing fourth-order Runge-Kutta (ETDRK4) method; this scheme was derived by Cox and Matthews in [S.M. Cox, P.C. Matthews, Exponential time differencing for stiff systems, J. Comp. Phys. 176 (2002) 430-455] and was modified by Kassam and Trefethen in [A. Kassam, L.N. Trefethen, Fourth-order time stepping for stiff PDEs, SIAM J. Sci. Comp. 26 (2005) 1214-1233]. We compute its amplification factor and plot its stability region, which gives us an explanation of its good behavior for dissipative and dispersive problems. We apply this method to the Schrödinger equation, obtaining excellent results for the cubic equation and the critical exponent case and, later, as an experimental approach to describe the various possible asymptotic behaviors with two space variables.     

Relations Between Forcing Sequences and Inexact Newton Iterates in Banach Space

We use inexact Newton iterates to approximate a solution of a nonlinear equation in a Banach space. Solving a nonlinear equation using Newton iterates at each stage is very expensive in general. That is why we consider inexact Newton methods, where the Newton equations are solved only approximately and in some unspecified manner. In the elegant paper [6] natural assumptions under which the forcing sequence is uniformly less than one were given based on the first-Fréchet derivative of the operator involved. Here, we use assumptions on the second Fréchet-derivative. This way, we essentially reproduce all results found earlier. However, our upper error bounds on the distances involved are smaller. Received: March 3, 1998; revised April 23, 1999     

Using integral equations and the immersed interface method to solve immersed boundary problems with stiff forces

We propose a fast, explicit numerical method for computing approximations for the immersed boundary problem in which the boundaries that separate the fluid into two regions are stiff. In the numerical computations of such problems, one frequently has to contend with numerical instability, as the stiff immersed boundaries exert large forces on the local fluid. When the boundary forces are treated explicitly, prohibitively small time-steps may be required to maintain numerical stability. On the other hand, when the boundary forces are treated implicitly, the restriction on the time-step size is reduced, but the solution of a large system of coupled non-linear equations may be required. In this work, we develop an efficient method that combines an integral equation approach with the immersed interface method. The present method treats the boundary forces explicitly. To reduce computational costs, the method uses an operator-splitting approach: large time-steps are used to update the non-stiff advection terms, and smaller substeps are used to advance the stiff boundary. At each substep, an integral equation is computed to yield fluid velocity local to the boundary; those velocity values are then used to update the boundary configuration. Fluid variables are computed over the entire domain, using the immersed interface method, only at the end of the large advection time-steps. Numerical results suggest that the present method compares favorably with an implementation of the immersed interface method that employs an explicit time-stepping and no fractional stepping.     

Implementing Radau IIA Methods for Stiff Delay Differential Equations

This article discusses the numerical solution of a general class of delay differential equations, including stiff problems, differential-algebraic delay equations, and neutral problems. The delays can be state dependent, and they are allowed to become small and vanish during the integration. Difficulties encountered in the implementation of implicit Runge–Kutta methods are explained, and it is shown how they can be overcome. The performance of the resulting code – RADAR5 – is illustrated on several examples, and it is compared to existing programs. Received October 12, 2000     

A note on convergence concepts for stiff problems

Most convergence concepts for discretizations of nonlinear stiff initial value problems are based on one-sided Lipschitz continuity. Therefore only those stiff problems that admit moderately sized one-sided Lipschitz constants are covered in a satisfactory way by the respective theory. In the present note we show that the assumption of moderately sized one-sided Lipschitz constants is violated for many stiff problems. We recall some convergence results that are not based on one-sided Lipschitz constants; the concept of singular perturbations is one of the key issues. Numerical experience with stiff problems that are not covered by available convergence results is reported.     

Composite Finite Elements for Elliptic Boundary Value Problems with Discontinuous Coefficients

In this paper, we will introduce composite finite elements for solving elliptic boundary value problems with discontinuous coefficients. The focus is on problems where the geometry of the interfaces between the smooth regions of the coefficients is very complicated. On the other hand, efficient numerical methods such as, e.g., multigrid methods, wavelets, extrapolation, are based on a multi-scale discretization of the problem. In standard finite element methods, the grids have to resolve the structure of the discontinuous coefficients. Thus, straightforward coarse scale discretizations of problems with complicated coefficient jumps are not obvious. In this paper, we define composite finite elements for problems with discontinuous coefficients. These finite elements allow the coarsening of finite element spaces independently of the structure of the discontinuous coefficients. Thus, the multigrid method can be applied to solve the linear system on the fine scale. We focus on the construction of the composite finite elements and the efficient, hierarchical realization of the intergrid transfer operators. Finally, we present some numerical results for the multigrid method based on the composite finite elements (CFE–MG).     

A variable step method for the numerical integration of the one-dimensional Schrödinger equation

Most numerical methods which have been proposed for the approximate integration of the one-dimensional Schrödinger equation use a fixed step length of integration. Such an approach can of course result in gross inefficiency since the small step length which must normally be used in the initial part of the range of integration to obtain the desired accuracy must then be used throughout the integration. In this paper we consider the method of embedding, which is widely used with explicit Runge-Kutta methods for the solution of first order initial value problems, for use with the special formulae used to integrate the Schrödinger equation. By adopting this technique we have available at each step an estimate of the local truncation error and this estimate can be used to automatically control the step length of integration. Also considered is the problem of estimating the global truncation error at the end of the range of integration. The power of the approaches considered is illustrated by means of some numerical examples.     

A note on the stability of rational Runge-Kutta methods

Computing - The present paper deals with the stability of rational Runge-Kutta methods in the numerical solution of stiff initial value problems. A natural stability requirement, calledA...     

Improving nonlinear electronic circuit simulation

The resolution of systems of stiff differential equations is required in the transient analysis of a large electronic network simulation. Resultant stability problems and the methods used in solving first order stiff nonlinear differential equations are reviewed. An improved algorithm is presented using BDF formulas given by Brayton et al. IEEE Vol 60 (1972) pp 98–108 and has been implemented in the IMAG electronic circuit simulation program. Reducing computer time has been achieved by controlling the number of Newton iterations, the number of integration steps, and the number of Jacobian matrix evaluations without producing additional errors or instability phenomena. Experimental results are shown.     

The use of quadratures for solving convective and highly stiff transport problems

In this paper we introduce a method for the numerical solutions of initial value problems, that combines finite differences with Simpson’s rule. The effectiveness of the method is proved by solving, in one spatial dimension, a stiff and convection-dominated transport problem. To solve the same problem in two spatial dimensions, the proposed method was used successfully in combination with Strang’s operator decomposition method.