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.     

Relative Convergence Estimates for the Spectral Asymptotic in the Large Coupling Limit

We prove optimal convergence estimates for eigenvalues and eigenvectors of a class of singular/stiff perturbed problems. Our profs are constructive in nature and use (elementary) techniques which are of current interest in computational Linear Algebra to obtain estimates even for eigenvalues which are in gaps of the essential spectrum. Further, we also identify a class of “regular” stiff perturbations with (provably) good asymptotic properties. The Arch Model from the theory of elasticity is presented as a prototype for this class of perturbations. We also show that we are able to study model problems which do not satisfy this regularity assumption by presenting a study of a Schroedinger operator with singular obstacle potential.     

Heterogeneous multiscale methods for stiff ordinary differential equations

The heterogeneous multiscale methods (HMM) is a general framework for the numerical approximation of multiscale problems. It is here developed for ordinary differential equations containing different time scales. Stability and convergence results for the proposed HMM methods are presented together with numerical tests. The analysis covers some existing methods and the new algorithms that are based on higher-order estimates of the effective force by kernels satisfying certain moment conditions and regularity properties. These new methods have superior computational complexity compared to traditional methods for stiff problems with oscillatory solutions.

     

Convergence of linear multistep and one-leg methods for stiff nonlinear initial value problems

To prove convergence of numerical methods for stiff initial value problems, stability is needed but also estimates for the local errors which are not affected by stiffness. In this paper global error bounds are derived for one-leg and linear multistep methods applied to classes of arbitrarily stiff, nonlinear initial value problems. It will be shown that under suitable stability assumptions the multistep methods are convergent for stiff problems with the same order of convergence as for nonstiff problems, provided that the stepsize variation is sufficiently regular.     

Global error estimation and control in linearly-implicit parallel two-step peer W-methods

The class of linearly-implicit parallel two-step peer W-methods has been designed recently for efficient numerical solutions of stiff ordinary differential equations. Those schemes allow for parallelism across the method, that is an important feature for implementation on modern computational devices. Most importantly, all stage values of those methods possess the same properties in terms of stability and accuracy of numerical integration. This property results in the fact that no order reduction occurs when they are applied to very stiff problems. In this paper, we develop parallel local and global error estimation schemes that allow the numerical solution to be computed for a user-supplied accuracy requirement in automatic mode. An algorithm of such global error control and other technical particulars are also discussed here. Numerical examples confirm efficiency of the presented error estimation and stepsize control algorithm on a number of test problems with known exact solutions, including nonstiff, stiff, very stiff and large-scale differential equations. A comparison with the well-known stiff solver RODAS is also shown.     

Global error estimation and control in linearly-implicit parallel two-step peer W-methods

The class of linearly-implicit parallel two-step peer W-methods has been designed recently for efficient numerical solutions of stiff ordinary differential equations. Those schemes allow for parallelism across the method, that is an important feature for implementation on modern computational devices. Most importantly, all stage values of those methods possess the same properties in terms of stability and accuracy of numerical integration. This property results in the fact that no order reduction occurs when they are applied to very stiff problems. In this paper, we develop parallel local and global error estimation schemes that allow the numerical solution to be computed for a user-supplied accuracy requirement in automatic mode. An algorithm of such global error control and other technical particulars are also discussed here. Numerical examples confirm efficiency of the presented error estimation and stepsize control algorithm on a number of test problems with known exact solutions, including nonstiff, stiff, very stiff and large-scale differential equations. A comparison with the well-known stiff solver RODAS is also shown.     

Development and Application of an Exponential Method for Integrating Stiff Systems Based on the Classical Runge–Kutta Method

We study numerical methods for solving stiff systems of ordinary differential equations. We propose an exponential computational algorithm which is constructed by using an exponential change of variables based on the classical Runge–Kutta method of the fourth order. Nonlinear problems are used to prove and demonstrate the fourth order of convergence of the new method.     

A roe-type Riemann solver for hyperbolic systems with relaxation based on time-dependent wave decomposition

Summary. The paper is devoted to the construction of a higher order Roe-type numerical scheme for the solution of hyperbolic systems with relaxation source terms. It is important for applications that the numerical scheme handles both stiff and non stiff source terms with the same accuracy and computational cost and that the relaxation variables are computed accurately in the stiff case. The method is based on the solution of a Riemann problem for a linear system with constant coefficients: a study of the behavior of the solutions of both the nonlinear and linearized problems as the relaxation time tends to zero enables to choose a convenient linearization such that the numerical scheme is consistent with both the hyperbolic system when the source terms are absent and the correct relaxation system when the relaxation time tends to zero. The method is applied to the study of the propagation of sound waves in a two-phase medium. The comparison between our numerical scheme, usual fractional step methods, and numerical simulation of the relaxation system shows the necessity of using the solutions of a fully coupled hyperbolic system with relaxation terms as the basis of a numerical scheme to obtain accurate solutions regardless of the stiffness. Received October 7, 1994 / Revised version received September 27, 1995     

Schur积多步方法

1.引 言考虑常微方程组其中,y,f∈Rm,Rm表示m维实空间, y0∈Rm为初值. 本文将显式线性多步方法与隐式Euler方法结合起来,构造了如下一类Schur积多步方法.     

Positivity-Preserving Local Discontinuous Galerkin Method for Pattern Formation Dynamical Model in Polymerizing Actin Flocks

In this paper, we apply local discontinuous Galerkin (LDG) methods for pattern formation dynamical model in polymerizing actin flocks. There are two main difficulties in designing effective numerical solvers. First of all, the density function is non-negative, and zero is an unstable equilibrium solution. Therefore, negative density values may yield blow-up solutions. To obtain positive numerical approximations, we apply the positivity-preserving (PP) techniques. Secondly, the model may contain stiff source. The most commonly used time integration for the PP technique is the strong-stability-preserving Runge-Kutta method. However, for problems with stiff source, such time discretizations may require strictly limited time step sizes, leading to large computational cost. Moreover, the stiff source any trigger spurious filament polarization, leading to wrong numerical approximations on coarse meshes. In this paper, we combine the PP LDG methods with the semi-implicit Runge-Kutta methods. Numerical experiments demonstrate that the proposed method can yield accurate numerical approximations with relatively large time steps.     

On the implementation of ESIRK methods for stiff IVPs

The effective order singly-implicit methods (ESIRK) are designed for solving stiff IVPs. These generalizations of SIRK methods are shown to have some computational advantages over the classical SIRK methods by moving the abscissae inside the integration interval [6]. In this paper, we consider some of the important computational aspects associated with these methods. We show that the ESIRK methods can be implemented efficiently by the comparsion with the standard stiff solvers RADAU5 and LSODE.     

Exponential integrators for linear inhomogeneous problems

We consider the mildly stiff and stiff inhomogeneous linear initial value Problems sharing constant coefficients. Exponential Runge–Kutta methods are considered to tackle this problem. For this type of problem, we were able to save a function evaluation (stage) per step compared to the best available methods. This is important, as seen in various computational experiments where our current approach outperforms older ones.     

CONVERGENCE OF PARALLEL DIAGONAL ITERATION OF RUNGE-KUTTA METHODS FOR DELAY DIFFERENTIAL EQUATIONS

Implicit Runge-Kutta method is highly accurate and stable for stiff initial value prob-lem.But the iteration technique used to solve implicit Runge-Kutta method requires lotsof computational efforts.In this paper,we extend the Parallel Diagonal Iterated Runge-Kutta(PDIRK)methods to delay differential equations(DDEs).We give the convergenceregion of PDIRK methods,and analyze the speed of convergence in three parts for theP-stability region of the Runge-Kutta corrector method.Finally,we analysis the speed-upfactor through a numerical experiment.The results show that the PDIRK methods toDDEs are efficient.     

刚性多滞量积分微分方程的Runge—Kutta方法

本文研究了求解刚性多滞量积分微分方程的Runge-Kutta方法的非线性稳定性和计算有效性.经典Runge—Kutta方法连同复合求积公式和Pouzet求积公式被改造用于求解一类刚性多滞量Volterra型积分微分方程.其分析导出了:在适当条件下,扩展的Runge-Kutta方法是渐近稳定和整体稳定的.此外,数值试验表明所给出的方法是高度有效的.     

分子动力学模拟中非成键相互作用计算的误差估计

高效的非成键相互作用计算对于分子动力学模拟具有核心意义.本文在一个统一的框架下,综述短程相互作用的截断方法、长程静电相互作用的光滑粒子网格Ewald方法和交错网格Ewald方法的误差估计.与传统的误差估计假设体系均匀且无相关性不同,本文介绍的误差估计可以推广到非均匀和有相关性的体系.本文通过具体例子讨论非均匀性和相关性对误差的本质性影响,以及可能的修正方式,并说明误差估计对于提高非成键相互作用的计算精度和速度有重要作用.本文还展示一个针对光滑粒子网格Ewald方法的实用参数优化方法,使得在保证精度的同时选取计算效率近似最优的参数组合成为可能,改善了传统上参数全凭经验选取的局面.     

Particle Approximations of the Score and Observed Information Matrix for Parameter Estimation in State–Space Models With Linear Computational Cost

Poyiadjis, Doucet, and Singh showed how particle methods can be used to estimate both the score and the observed information matrix for state–space models. These methods either suffer from a computational cost that is quadratic in the number of particles, or produce estimates whose variance increases quadratically with the amount of data. This article introduces an alternative approach for estimating these terms at a computational cost that is linear in the number of particles. The method is derived using a combination of kernel density estimation, to avoid the particle degeneracy that causes the quadratically increasing variance, and Rao–Blackwellization. Crucially, we show the method is robust to the choice of bandwidth within the kernel density estimation, as it has good asymptotic properties regardless of this choice. Our estimates of the score and observed information matrix can be used within both online and batch procedures for estimating parameters for state–space models. Empirical results show improved parameter estimates compared to existing methods at a significantly reduced computational cost. Supplementary materials including code are available.     

Partitioned adaptive Runge-Kutta methods and their stability

Summary This paper deals with the solution of partitioned systems of nonlinear stiff differential equations. Given a differential system, the user may specify some equations to be stiff and others to be nonstiff. For the numerical solution of such a system partitioned adaptive Runge-Kutta methods are studied. Nonstiff equations are integrated by an explicit Runge-Kutta method while an adaptive Runge-Kutta method is used for the stiff part of the system.The paper discusses numerical stability and contractivity as well as the implementation and usage of such compound methods. Test results for three partitioned stiff initial value problems for different tolerances are presented.     

Comparison of efficiency among different techniques to avoid order reduction with Strang splitting

In this article, we offer a comparison in terms of computational efficiency between two techniques to avoid order reduction when using Strang method to integrate nonlinear initial boundary value problems with time‐dependent boundary conditions. We see that it is important to consider an exponential method for the integration of the linear nonhomogeneous and stiff part in the technique by Einkemmer et al. so that the latter is comparable in efficiency with that suggested by Alonso et al. Some other advantages of the technique suggested by Alonso et al. are stated in the conclusions.     

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.     

Finite volume schemes for nonhomogeneous scalar conservation laws: error estimate

Summary. In this paper, we study finite volume schemes for the nonhomogeneous scalar conservation law with initial condition . The source term may be either stiff or nonstiff. In both cases, we prove error estimates between the approximate solution given by a finite volume scheme (the scheme is totally explicit in the nonstiff case, semi-implicit in the stiff case) and the entropy solution. The order of these estimates is in space-time -norm (h denotes the size of the mesh). Furthermore, the error estimate does not depend on the stiffness of the source term in the stiff case. Received October 21, 1999 / Published online February 5, 2001