Parallel iteration of the extended backward differentiation formulas

The extended backward differentiation formulas (EBDFs) and theirmodified form (MEBDF) were proposed by Cash in the 1980s forsolving initial value problems (IVPs) for stiff systems of ordinarydifferential equations (ODEs). In a recent performance evaluationof various IVP solvers, including a variable-step-variable-orderimplementation of the MEBDF method by Cash, it turned out thatthe MEBDF code often performs more efficiently than codes likeRADAU5, DASSL and VODE. This motivated us to look at possibleparallel implementations of the MEBDF method. Each MEBDF stepessentially consists of successively solving three non-linearsystems by means of modified Newton iteration using the sameJacobian matrix. In a direct implementation of the MEBDF methodon a parallel computer system, the only scope for (coarse grain)parallelism consists of a number of parallel vector updates.However, all forward–backward substitutions and all right-hand-sideevaluations have to be done in sequence. In this paper, ourstarting point is the original (unmodified) EBDF method. Asa consequence, two different Jacobian matrices are involvedin the modified Newton method, but on a parallel computer system,the effective Jacobian-evaluation and the LU decomposition costsare not increased. Furthermore, we consider the simultaneoussolution, rather than the successive solution, of the threenon-linear systems, so that in each iteration the forward–backwardsubstitutions and the right-hand-side evaluations can be doneconcurrently. A mutual comparison of the performance of theparallel EBDF approach and the MEBDF approach shows that wecan expect a speed-up factor of about 2 on three processors.     

On the solvability of the systems of equations arising in implicit Runge-Kutta methods

In this paper we present a new condition under which the systems of equations arising in the application of an implicit Runge-Kutta method to a stiff initial value problem, has unique solutions. We show that our condition is weaker than related conditions presented previously. It is proved that the Lobatto IIIC methods fulfil the new condition.     

On improving the absolute stability of local extrapolation

Summary A widely used technique for improving the accuracy of solutions of initial value problems in ordinary differential equations is local extrapolation. It is well known, however, that when using methods appropriate for solving stiff systems of ODES, the stability of the method can be seriously degraded if local extrapolation is employed. This is due to the fact that performing local extrapolation on a low order method is equivalent to using a higher order formula and this high order formula may not be suitable for solving stiff systems. In the present paper a general approach is proposed whereby the correction term added on in the process of local extrapolation is in a sense a rational, rather than a polynomial, function. This approach allows high order formulae with bounded growth functions to be developed. As an example we derive anA-stable rational correction algorithm based on the trapezoidal rule. This new algorithm is found to be efficient when low accuracy is requested (say a relative accuracy of about 1%) and its performance is compared with that of the more familiar Richardson extrapolation method on a large set of stiff test problems.     

Choice of strategies for extrapolation with symmetrization in the constant stepsize setting

Symmetrization has been shown to be efficient in solving stiff problems. In the constant stepsize setting, we study four ways of applying extrapolation with symmetrization. We observe that for stiff linear problems the symmetrized Gauss methods are more efficient than the symmetrized Lobatto IIIA methods of the same order. However, for two-dimensional nonlinear problems, the symmetrized 4-stage Lobatto IIIA method is more efficient. In all cases, we observe numerically that passive symmetrization with passive extrapolation is more efficient than active symmetrization with active extrapolation.     

On the construction of error estimators for implicit Runge-Kutta methods

For implicit Runge-Kutta methods intended for stiff ODEs or DAEs, it is often difficult to embed a local error estimating method which gives realistic error estimates for stiff/algebraic components. If the embedded method's stability function is unbounded at z=∞, stiff error components are grossly overestimated. In practice, some codes ‘improve’ such inadequate error estimates by premultiplying the estimate by a ‘filter’ matrix which damps or removes the large, stiff error components. Although improving computational performance, this technique is somewhat arbitrary and lacks a sound theoretical backing. In this scientific note we resolve this problem by introducing an implicit error estimator. It has the desired properties for stiff/algebraic components without invoking artificial improvements. The error estimator contains a free parameter which determines the magnitude of the error, and we show how this parameter is to be selected on the basis of method properties. The construction principles for the error estimator can be adapted to all implicit Runge-Kutta methods, and a better agreement between actual and estimated errors is achieved, resulting in better performance.     

用加权平均方法构造新的隐式线性多步法公式

在已知的线性多步法公式中,用两个较适合的线性多步法进行加权平均就能构造出一系列新的隐式线性多步法公式,而且其中有些公式可能具有较好的性质,如稳定域增大.从而使得解刚性方程时,可以根据对稳定域与截断误差不同的需求来选择公式,以达到在适合的稳定域下,截断误差最小.经过数值试验验证,本文举出的实例中用加权平均方法构造出的有些新公式的稳定域大于原来两个公式任一个的稳定域,可应用于求解常微分方程初值问题的刚性问题.     

Variable-Order ESIRK Methods for Stiff Differential Equations

ESIRK methods (Effective order Singly-Implicit Runge–Kutta methods) have been shown to be efficient for the numerical solution of stiff differential equations. In this paper, we consider a new implementation of these methods with a variable order strategy. We show that the efficiency of the ESIRK method for stiff problems is improved by using the proposed variable order schemes.     

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.     

Geometrically adaptive grids for stiff Cauchy problems

A new method for automatic step size selection in the numerical integration of the Cauchy problem for ordinary differential equations is proposed. The method makes use of geometric characteristics (curvature and slope) of an integral curve. For grids generated by this method, a mesh refinement procedure is developed that makes it possible to apply the Richardson method and to obtain a posteriori asymptotically precise estimate for the error of the resulting solution (no such estimates are available for traditional step size selection algorithms). Accordingly, the proposed methods are more robust and accurate than previously known algorithms. They are especially efficient when applied to highly stiff problems, which is illustrated by numerical examples.     

Hybrid BDF methods for the numerical solutions of ordinary differential equations

In this article, we have presented the details of hybrid methods which are based on backward differentiation formula (BDF) for the numerical solutions of ordinary differential equations (ODEs). In these hybrid BDF, one additional stage point (or off-step point) has been used in the first derivative of the solution to improve the absolute stability regions. Stability domains of our presented methods have been obtained showing that all these new methods, we say HBDF, of order p, p = 2,4,..., 12, are A(α)-stable whereas they have wide stability regions comparing with those of some known methods like BDF, extended BDF (EBDF), modified EBDF (MEBDF), adaptive EBDF (A-EBDF), and second derivtive Enright methods. Numerical results are also given for five test problems.     

Blended extended linear multistep methods for the accurate numerical integration of stiff initial value problems

A class of blended extended linear multistep methods suitable for the approximate numerical integration of stiff systems of first order ordinary differential equations is described. These methods are formulated as a result of combining the second derivative extended backward differentiation formulae of Cash and the blended linear multistep methods of Skeel and Kong. The new methods combine a high order or accuracy with good stability properties and, as a direct consequence, they are often suitable for the numerical integration of stiff differential systems when high accuracy is requested. In the first part of the present paper we consider the derivation of these new blended methods and give the coefficients and stability regions for formulae of order up to and including 10. In the second half we consider their practical implementation. In particular we describe a variable order/variable step package based on these blended formulae and we evaluate the performance of this package on the well known DETEST test set. It is shown that the new code is reliable on this test set and is competitive with the well known second derivative method of Enright.     

Modified defect correction algorithms for ODEs. Part II: Stiff initial value problems

As shown in part I of this paper and references therein, the classical method of Iterated Defect Correction (IDeC) can be modified in several nontrivial ways, extending the flexibility and range of applications of this approach. The essential point is an adequate definition of the defect, resulting in a significantly more robust convergence behavior of the IDeC iteration, in particular, for nonequidistant grids. The present part II is devoted to the efficient high-order integration of stiff initial value problems. By means of model problem investigation and systematic numerical experiments with a set of stiff test problems, our new versions of defect correction are systematically evaluated, and further algorithmic measures are proposed for the stiff case. The performance of the different variants under consideration is compared, and it is shown how strong coupling between non-stiff and stiff components can be successfully handled. AMS subject classification 65L05 Supported by the Austrian Research Fund (FWF) grant P-15030.     

The combined Laplace transform and new homotopy perturbation methods for stiff systems of ODEs

In this paper, we propose new technique for solving stiff system of ordinary differential equations. This algorithm is based on Laplace transform and homotopy perturbation methods. The new technique is applied to solving two mathematical models of stiff problem. We show that the present approach is relatively easy, efficient and highly accurate.     

飞机辅助动力装置引气特性计算方法

作为飞机环控系统与主发动机起动的气源,以目前广泛应用的带负载压气机结构APU(Auxiliary Power Unit)为研究对象,进行引气特性计算模型与计算方法研究。首先介绍了APU结构与引气工作特点,然后分析了建模时喘振控制阀SCV(Surge Control Valve)控制方法与APU共同工作机理,最后采用部件法建立了该类型APU引气计算数学模型。以某型APU为对象进行数值仿真并与实际试车数据比较,计算误差小于3%,表明所采用的建模方法是正确的,所建立的模型能够满足工程需求。      

The adaptive operational Tau method for systems of ODEs

As the Tau method, like many other numerical methods, has the limitation of using a fixed step size with some high degree (order) of approximation for solving initial value problems over long intervals, we introduce here the adaptive operational Tau method. This limitation is very much problem dependent and in such case the fixed step size application of the Tau method loses the true track of the solution. But when we apply this new adaptive method the true solution is recovered with a reasonable number of steps. To illustrate the effectiveness of this method we apply it to some stiff systems of ordinary differential equations (ODEs). The numerical results confirm the efficiency of the method.     

Capacity switching options under rivalry and uncertainty

Deregulated infrastructure industries exhibit stiff competition for market share. Firms may be able to limit the effects of competition by launching new projects in stages. Using a two-stage real options model, we explore the value of such flexibility. We first demonstrate that the value of investing in a sequential manner for a monopolist is positive but decreases with uncertainty. Next, we find that a typical duopoly firm’s value relative to a monopolist’s decreases with uncertainty as long as the loss in market share is high. Intriguingly, this result is reversed for a low loss in market share. We finally show that this loss in value is reduced if a firm invests in a sequential manner and specify the conditions under which sequential capacity expansion is more valuable for a duopolist firm than for a monopolist.     

A Third Order Small Parameter Method and Its Nordsieck Expression

A third order small parameter method and its Nordsieck expression are given in this paper. It is based on Gear's method of order 2 and order 3. For moderate stiff problems this method is suitable. In [1] we proposed a second order numerical method for stiff ODEs. The purpose of this paper is to raise the order from 2 to 3 and give its Nordsieck expression, making it automatically suit varying stepsize calculation.     

Stable Runge–Kutta–Nyström methods for dissipative stiff problems

The definition of stability for Runge–Kutta–Nyström methods applied to stiff second-order in time problems has been recently revised, proving that it is necessary to add a new condition on the coefficients in order to guarantee the stability. In this paper, we study the case of second-order in time problems in the nonconservative case. For this, we construct an $RThe definition of stability for Runge–Kutta–Nystr?m methods applied to stiff second-order in time problems has been recently revised, proving that it is necessary to add a new condition on the coefficients in order to guarantee the stability. In this paper, we study the case of second-order in time problems in the nonconservative case. For this, we construct an -stable Runge–Kutta–Nystr?m method with two stages satisfying this condition of stability and we show numerically the advantages of this new method.This research was supported by MTM 2004-08012 and JCYL VA103/04.     

Second order Chebyshev methods based on orthogonal polynomials

Summary. Stabilized methods (also called Chebyshev methods) are explicit Runge-Kutta methods with extended stability domains along the negative real axis. These methods are intended for large mildly stiff problems, originating mainly from parabolic PDEs. The aim of this paper is to show that with the use of orthogonal polynomials, we can construct nearly optimal stability polynomials of second order with a three-term recurrence relation. These polynomials can be used to construct a new numerical method, which is implemented in a code called ROCK2. This new numerical method can be seen as a combination of van der Houwen-Sommeijer-type methods and Lebedev-type methods. Received January 14, 2000 / Revised version received November 3, 2000 / Published online May 4, 2001     

Iterative operator-splitting methods with higher-order time integration methods and applications for parabolic partial differential equations

In this paper we design higher-order time integrators for systems of stiff ordinary differential equations. We combine implicit Runge–Kutta and BDF methods with iterative operator-splitting methods to obtain higher-order methods. The idea of decoupling each complicated operator in simpler operators with an adapted time scale allows to solve the problems more efficiently. We compare our new methods with the higher-order fractional-stepping Runge–Kutta methods, developed for stiff ordinary differential equations. The benefit is the individual handling of each operator with adapted standard higher-order time integrators. The methods are applied to equations for convection–diffusion reactions and we obtain higher-order results. Finally we discuss the applications of the iterative operator-splitting methods to multi-dimensional and multi-physical problems.