求解刚性常微分方程的并行广义Rosenbrock方法

本文构造了求解刚性常微分方程的并行广义Rosenbrock方法（PEROWs），分析了方法的收敛性和数值稳定性。通过用Powell方法优化方法的稳定域，构造了二级四阶并行格式PEROW4，并证明该方法是A－稳定的。新方法比同级的并行Rosenbrock方法MPROW3及PRM3均高一阶，因而在计算精度上处于优势。此外，PEROW4能使得各处理机上的负载基本均衡，从而达到非常理想的加速比和并行效率。     

PARALLEL ROSENBROCK METHODS FOR SOLVING STIFF SYSTEMS IN REAL-TIME SIMULATION

1. IntroductionIn the fields of astronautics engineering and continuous system simulation, manymodels are described by stiff ODE's. In order to simulate (especially in real-time) thesesystems we have to use speedy algorithms so as to complete the computation withinthe designated time. Papers [5,7,8] present parallel-iterated Runge-Kutta methods andimplicit Runge-Kutta methods. Although these methods have higher stabilityt a heavierworkload will be imposed by the iteration. And our inabilit…     

The best choice of subsample size (M,K) in 3 stage sampling

In this paper we extend the best choice of subsample size m in the 2-stage sampling,which suggested by Mohammad(1986), to the 3-stage sampling in cases of known and of unknown cost and variance ratio. We find the subsample size m,k which ensures more than the relative efficiency 90 %. Also we see that the choice of 3-stage subsample size depends on the design parameters using in 2-stage sampling.     

Comparing the contractivity properties of semi-implicit methods

Contractivity is a desirable property of numerical integration methods for stiff systems of ordinary differential equations. In this paper, numerical parameters are used to allow a direct and quantitative comparison of the contractivity properties of various methods for non-linear stiff problems. Results are provided for popular Rosenbrock methods and some more recently developed semi-implicit methods.     

ROS3P—An Accurate Third-Order Rosenbrock Solver Designed for Parabolic Problems

In this note we present a new Rosenbrock solver which is third-order accurate for nonlinear parabolic problems. Since Rosenbrock methods suffer from order reduction when they are applied to partial differential equations, additional order conditions have to be satisfied. Although these conditions have been known for a longer time, from the practical point of view only little has been done to construct new methods. Steinebach modified the well-known solver RODAS of Hairer and Wanner to preserve its classical order four for special problem classes including linear parabolic equations. His solver RODASP, however, drops down to order three for nonlinear parabolic problems. Our motivation here was to derive an efficient third-order Rosenbrock solver for the nonlinear situation. Such a method exists with three stages and two function evaluations only. A comparison with other third-order methods shows the substantial potential of our new method.This revised version was published online in October 2005 with corrections to the Cover Date.     

Exponential Rosenbrock integrators for option pricing

In this paper, we are concerned with the time integration of differential equations modeling option pricing. In particular, we consider the Black-Scholes equation for American options. As an alternative to existing methods, we present exponential Rosenbrock integrators. These integrators require the evaluation of the exponential and related functions of the Jacobian matrix. The resulting methods have good stability properties. They are fully explicit and do not require the numerical solution of linear systems, in contrast to standard integrators. We have implemented some numerical experiments in Matlab showing the reliability of the new method.     

Doubly quasi-consistent parallel explicit peer methods with built-in global error estimation

Recently, Kulikov presented the idea of double quasi-consistency, which facilitates global error estimation and control, considerably. More precisely, a local error control implemented in such methods plays a part of global error control at the same time. However, Kulikov studied only Nordsieck formulas and proved that there exists no doubly quasi-consistent scheme among those methods.Here, we prove that the class of doubly quasi-consistent formulas is not empty and present the first example of such sort. This scheme belongs to the family of superconvergent explicit two-step peer methods constructed by Weiner, Schmitt, Podhaisky and Jebens. We present a sample of s-stage doubly quasi-consistent parallel explicit peer methods of order s−1 when s=3. The notion of embedded formulas is utilized to evaluate efficiently the local error of the constructed doubly quasi-consistent peer method and, hence, its global error at the same time. Numerical examples of this paper confirm clearly that the usual local error control implemented in doubly quasi-consistent numerical integration techniques is capable of producing numerical solutions for user-supplied accuracy conditions in automatic mode.     

A family of explicit parallel Runge-Kutta-Nyström methods

A procedure for the construction of high-order explicit parallel Runge-Kutta-Nyström (RKN) methods for solving second-order nonstiff initial value problems (IVPs) is analyzed. The analysis reveals that starting the procedure with a reference symmetric RKN method it is possible to construct high-order RKN schemes which can be implemented in parallel on a small number of processors. These schemes are defined by means of a convex combination of k disjoint s_i-stage explicit RKN methods which are constructed by connecting s_i steps of a reference explicit symmetric method. Based on the reference second-order Störmer-Verlet methods we derive a family of high-order explicit parallel schemes which can be implemented in variable-step codes without additional cost. The numerical experiments carried out show that the new parallel schemes are more efficient than some sequential and parallel codes proposed in the scientific literature for solving second-order nonstiff IVPs.     

Phase properties of high order,almostP-stable formulae

Cash [3] and Chawla [4] derive families of two-step, symmetric,P-stable (hybrid) methods for solving periodic initial value problems numerically. Chawla demonstrates the existence of a family of fourth order methods while Cash derives both fourth order and sixth order methods. In this paper, we demonstrate that these methods, which are dependent on certain free parameters, havein phase particular solutions. We consider more general families of 2-step symmetric methods, including those derived by Cash and Chawla, and show that some members of these families have higher order phase lag and are almostP-stable. We also consider how the free parameters can be chosen so as to lead to an efficient implementation of the fourth order methods for large periodic systems.Most of this work was carried out while the author was at the Department of Computer Studies, University of Leeds, Leeds, England.     

Positively invariant cones of dynamical systems under Runge‐Kutta and Rosenbrock‐type discretization

In this paper we consider positively invariant cones of finite dimensional dynamical systems and study conditions on the time step‐size that guarantee the discrete positive invariance of these cones under Runge‐Kutta and Rosenbrock‐type methods. We conclude quite simple sufficient conditions, which involve the positivity (or absolute monotonicity) radius of the Runge‐Kutta schemes and its generalization when the Rosenbrock‐type methods are applied. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Error of rosenbrock methods for stiff problems studied via differential algebraic equations

This paper studies Rosenbrock methods when they are applied to stiff differential equations containing a small stiffness parameter. The basic ideas and techniques are the same as those developed for Runge-Kutta methods in an earlier paper of the authors. The results obtained here are essentially those obtained for Diagonally Implicit Runge-Kutta methods.     

Convergence of parallel multistep hybrid methods for singular perturbation problems

Parallel multistep hybrid methods (PHMs) can be implemented in parallel with two processors, accordingly have almost the same computational speed per integration step as BDF methods of the same order with the same stepsize. But PHMs have better stability properties than BDF methods of the same order for stiff differential equations. In the present paper, we give some results on error analysis of A(α)-stable PHMs for the initial value problems of ordinary differential equations in singular perturbation form. Our convergence results are similar to those of linear multistep methods (such as BDF methods), i.e. the convergence orders are equal to their classical convergence orders, and no order reduction occurs. Some numerical examples also confirm our results.     

Non-Unit Free Triangle Orders

A Free Triangle order is a partially ordered set in which every element can be represented by a triangle. All triangles lie between two parallel baselines, with each triangle intersecting each baseline in exactly one point. Two elements in the partially ordered set are incomparable if and only if their corresponding triangles intersect. A unit free triangle order is one with such a representation in which all triangles have the same area. In this paper, we present an example of a non-unit free triangle order.     

Parallel iterative linear solvers for multistep Runge-Kutta methods

This paper deals with solving stiff systems of differential equations by implicit Multistep Runge-Kutta (MRK) methods. For this type of methods, nonlinear systems of dimension sd arise, where s is the number of Runge-Kutta stages and d the dimension of the problem. Applying a Newton process leads to linear systems of the same dimension, which can be very expensive to solve in practice. With a parallel iterative linear system solver, especially designed for MRK methods, we approximate these linear systems by s systems of dimension d, which can be solved in parallel on a computer with s processors. In terms of Jacobian evaluations and LU-decompositions, the k-steps-stage MRK applied with this technique is on s processors equally expensive as the widely used k-step Backward Differentiation Formula on 1 processor, whereas the stability properties are better than that of BDF. A simple implementation of both methods shows that, for the same number of Newton iterations, the accuracy delivered by the new method is higher than that of BDF.     

Rosenbrock methods for Differential Algebraic Equations

Summary This paper deals with the numerical solution of Differential/Algebraic Equations (DAE) of index one. It begins with the development of a general theory on the Taylor expansion for the exact solutions of these problems, which extends the well-known theory of Butcher for first order ordinary differential equations to DAE's of index one. As an application, we obtain Butcher-type results for Rosenbrock methods applied to DAE's of index one, we characterize numerical methods as applications of certain sets of trees. We derive convergent embedded methods of order 4(3) which require 4 or 5 evaluations of the functions, 1 evaluation of the Jacobian and 1 LU factorization per step.     

An embedded 3(2) pair of nonlinear methods for solving first order initial-value ordinary differential systems

In this paper, we present two families of second-order and third-order explicit methods for numerical integration of initial-value problems of ordinary differential equations. Firstly, a family of second-order methods with two free parameters is derived by considering a suitable rational approximation to the theoretical solution of the problem at some grid points. Imposing that the principal term of the local truncation error of this family vanishes, we obtain an expression for one of the parameters in terms of the other. With this approach, a new one-parameter family of third-order methods is obtained. By selecting any 3(2) pair of second and third order methods, they can be implemented as an embedded type method, thus leading to a variable step-size formulation. We have considered one 3(2) pair of second and third order methods and made a comparison of numerical results with several ode solvers which are currently used in practice. The comparison of numerical results shows that the embedded 3(2) pair outperforms the methods considered for comparison.     

Order conditions for Rosenbrock type methods

Summary Based on the theory of Butcher series this paper developes the order conditions for Rosenbrock methods and its extensions to Runge-Kutta methods with exact Jacobian dependent coefficients. As an application a third order modified Rosenbrock method with local error estimate is constructed and tested on some examples.     

组合RK-Rosenbrock方法及其稳定性分析

１．引言 在研究和设计宇航飞行器时,常常会遇到刚性大系统,他们具有特殊结构,系统的解分量有的变化很快,而有的变化很慢。我们可将其分解成两个耦合的子系统;其中（１）式为刚性子系统,（２）式为非刚性子系统。 由于子系统（１）是刚性的,因而整个系统也是刚性的,所以需要采用适合于求解刚性方程的隐式或半隐式方法来求解。但是,在很多情况中,刚性方程组（１）仅占整个方程组的很小一部分,而且右函数相当简单,因而整个右函数计算量主要集中在非刚性方程组（２）上。另一方面,这种对整个方程组采用同一个数值积分方法来处理的…     

Qualitatively stability of nonstandard 2-stage explicit Runge–Kutta methods of order two

When one solves differential equations, modeling physical phenomena, it is of great importance to take physical constraints into account. More precisely, numerical schemes have to be designed such that discrete solutions satisfy the same constraints as exact solutions. Nonstandard finite differences (NSFDs) schemes can improve the accuracy and reduce computational costs of traditional finite difference schemes. In addition NSFDs produce numerical solutions which also exhibit essential properties of solution. In this paper, a class of nonstandard 2-stage Runge–Kutta methods of order two (we call it nonstandard RK2) is considered. The preservation of some qualitative properties by this class of methods are discussed. In order to illustrate our results, we provide some numerical examples.     

Two-step-by-two-step PIRK-type PC methods based on Gauss-Legendre collocation points

This paper concerns with parallel predictor-corrector (PC) iteration methods for solving nonstiff initial-value problems (IVPs) for systems of first-order differential equations. The predictor methods are based on Adams-type formulas. The corrector methods are constructed by using coefficients of s-stage collocation Gauss-Legendre Runge-Kutta (RK) methods based on c₁,…,c_s and the 2s-stage collocation RK methods based on c₁,…,c_s,1+c₁,…,1+c_s. At nth integration step, the stage values of the 2s-stage collocation RK methods evaluated at t_n+(1+c₁)h,…,t_n+(1+c_s)h can be used as the stage values of the collocation Gauss-Legendre RK method for (n+2)th integration step. By this way, we obtain the corrector methods in which the integration processes can be proceeded two-step-by-two-step. The resulting parallel PC iteration methods which are called two-step-by-two-step (TBT) parallel-iterated RK-type (PIRK-type) PC methods based on Gauss-Legendre collocation points (two-step-by-two-step PIRKG methods or TBTPIRKG methods) give us a faster integration process. Fixed step size applications of these TBTPIRKG methods to the three widely used test problems reveal that the new parallel PC iteration methods are much more efficient when compared with the well-known parallel-iterated RK methods (PIRK methods) and sequential codes ODEX, DOPRI5 and DOP853 available from the literature.