Spectral Deferred Correction Methods for Ordinary Differential Equations

We introduce a new class of methods for the Cauchy problem for ordinary differential equations (ODEs). We begin by converting the original ODE into the corresponding Picard equation and apply a deferred correction procedure in the integral formulation, driven by either the explicit or the implicit Euler marching scheme. The approach results in algorithms of essentially arbitrary order accuracy for both non-stiff and stiff problems; their performance is illustrated with several numerical examples. For non-stiff problems, the stability behavior of the obtained explicit schemes is very satisfactory and algorithms with orders between 8 and 20 should be competitive with the best existing ones. In our preliminary experiments with stiff problems, a simple adaptive implementation of the method demonstrates performance comparable to that of a state-of-the-art extrapolation code (at least, at moderate to high precision).Deferred correction methods based on the Picard equation appear to be promising candidates for further investigation.     

An algorithm using the finite volume element method and its splitting extrapolation

This paper is to present a new efficient algorithm by using the finite volume element method and its splitting extrapolation. This method combines the local conservation property of the finite volume element method and the advantages of splitting extrapolation, such as a high order of accuracy, a high degree of parallelism, less computational complexity and more flexibility than a Richardson extrapolation. Because the splitting extrapolation formulas only require us to solve a set of smaller discrete subproblems on different coarser grids in parallel instead of on the globally fine grid, a large scale multidimensional problem is turned into a set of smaller discrete subproblems. Additionally, this method is efficient for solving interface problems if we regard the interfaces of the problems as the interfaces of the initial domain decomposition.     

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.     

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.     

Mesh selection for stiff two-point boundary value problems

This paper is concerned with the mesh selection algorithm of COLSYS, a well known collocation code for solving systems of boundary value problems. COLSYS was originally designed to solve non-stiff and mildly stiff problems only. In this paper we show that its performance for solving extremely stiff problems can be considerably improved by modifying its error estimation and mesh selection algorithms. Numerical examples indicate the superiority of the modified algorithm.Dedicated to John Butcher on the occasion of his sixtieth birthday     

Splitting extrapolation for solving second order elliptic systems with curved boundary in by using d-quadratic isoparametric finite element

Splitting extrapolation for solving second order elliptic systems with curved boundary in by using isoparametric d-quadratic element Q₂ is presented, which is a new technique for solving large scale scientific and engineering problems in parallel. By means of domain decomposition, a large scale multidimensional problem with curved boundary is turned into many discrete problems involving several grid parameters. The multivariate asymptotic expansions of isoparametric d-quadratic Q₂ finite element errors with respect to independent grid parameters are proved for second order elliptic systems. Therefore after solving smaller problems with similar sizes in parallel, a global fine grid approximation with higher accuracy is computed by the splitting extrapolation method.     

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.     

On the construction of restricted-denominator exponential W-methods

In this paper we consider the practical construction of exponential W-methods for the solution of large stiff nonlinear initial value problems, based on the restricted-denominator rational approach for the computation of the functions of matrices required. This approach is employed together with the Krylov subspace method based on the Arnoldi algorithm. Two integrators are constructed and tested on some classical stiff equations arising from the semidiscretization of parabolic problems.     

A new fourth‐order numerical algorithm for a class of three‐dimensional nonlinear evolution equations

In this article, a new compact alternating direction implicit finite difference scheme is derived for solving a class of 3‐D nonlinear evolution equations. By the discrete energy method, it is shown that the new difference scheme has good stability and can attain second‐order accuracy in time and fourth‐order accuracy in space with respect to the discrete H¹ ‐norm. A Richardson extrapolation algorithm is applied to achieve fourth‐order accuracy in temporal dimension. Numerical experiments illustrate the accuracy and efficiency of the extrapolation algorithm. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

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.     

Variational methods of constructing monotone approximations for atmospheric chemistry models

A new method of constructing efficient monotone numerical schemes for solving direct, adjoint, and inverse atmospheric chemistry problems is presented. It is a synthesis of variational principles combined with splitting and decomposition methods and a constructive implementation of Euler integrating multipliers (EIM) bymeans of a local adjoint problem technique. To increase the efficiency of calculations, a method of decomposing the multicomponent substance transformation operators in terms of the mechanisms of reactions is also proposed. With analytical EIMs, the systems of stiff ODEs are decomposed and reduced to equivalent systems of integral equations solved by noniterative multistage algorithms of a given order of accuracy. An unconventional variational method of constructing mutually consistent algorithms for direct and adjoint problems and sensitivity studies for complex models with constraints is described.     

一类A－稳定或L－稳定的经济隐式单块法

一类Ａ－稳定或Ｌ－稳定的经济隐式单块法赵双锁，张国凤（兰州大学数学系）ＡＣＬＡＳＳＯＦＡ－ＳＴＡＢＬＥＯＲＬ－ＳＴＡＢＬＥＥＣＯＮＯＭＩＣＡＬＩＭＰＬＩＣＩＴＳＩＮＧＬＥ－ＢＬＯＣＫＭＥＴＨＯＤＳ￥ＺｈａｏＳｈｕａｎｇ－ｓｕｏ；ＺｈａｎｇＧｕｏ－ｆｅ...     

On the integration of stiff systems of O.D.E.s using extended backward differentiation formulae

Summary A class of extended backward differentiation formulae suitable for the approximate numerical integration of stiff systems of first order ordinary differential equations is derived. An algorithm is described whereby the required solution is predicted using a conventional backward differentiation scheme and then corrected using an extended backward differentiation scheme of higher order. This approach allows us to developL-stable schemes of order up to 4 andL()-stable schemes of order up to 9. An algorithm based on the integration formulae derived in this paper is illustrated by some numerical examples and it is shown that it is often superior to certain existing algorithms.     

A Globally Convergent Trust-Region Method for Large-Scale Symmetric Nonlinear Systems

This study presents a novel adaptive trust-region method for solving symmetric nonlinear systems of equations. The new method uses a derivative-free quasi-Newton formula in place of the exact Jacobian. The global convergence and local quadratic convergence of the new method are established without the nondegeneracy assumption of the exact Jacobian. Using the compact limited memory BFGS, we adapt a version of the new method for solving large-scale problems and develop the dogleg scheme for solving the associated trust-region subproblems. The sufficient decrease condition for the adapted dogleg scheme is established. While the efficiency of the present trust-region approach can be improved by using adaptive radius techniques, utilizing the compact limited memory BFGS adjusts this approach to handle large-scale symmetric nonlinear systems of equations. Preliminary numerical results for both medium- and large-scale problems are reported.     

A second‐order partitioned method with different subdomain time steps for the evolutionary Stokes‐Darcy system

A second‐order decoupled algorithm for the nonstationary Stokes‐Darcy system, which allows different time steps in two subregions, is proposed and analyzed in this paper. The algorithm, which is a combination of the second‐order backward differentiation formula and second‐order extrapolation method, uncouples the problem into two decoupled problems per time step. We prove the unconditional stability and long‐time stability of the decoupled scheme with different time steps and derive error estimates of this decoupled algorithm using finite element spatial discretization. Numerical experiments are provided to illustrate the accuracy, effectiveness, and stability of the decoupled algorithm and show its advantages of increasing accuracy and efficiency.     

Numerical algorithm for solving multi-pantograph delay equations on the half-line using Jacobi rational functions with convergence analysis

A new spectral Jacobi rational-Gauss collocation (JRC) method is proposed for solving the multi-pantograph delay differential equations on the half-line. The method is based on Jacobi rational functions and Gauss quadrature integration formula. The main idea for obtaining a semi-analytical solution for these equations is essentially developed by reducing the pantograph equations with their initial conditions to systems of algebraic equations in the unknown expansion coefficients. The convergence analysis of the method is analyzed. The method possesses the spectral accuracy. Numerical results indicating the high accuracy and effectiveness of this algorithm are presented. Indeed, the present method is compared favorably with other methods.     

Adaptive partitioning techniques for ordinary differential equations

Many stiff systems of ordinary differential equations (ODEs) modeling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.This paper presents an adaptive partitioning algorithm based on a classical graph algorithm and techniques for the efficient evaluation of the error introduced by the partitioning.The power of the adaptive partitioning algorithm is demonstrated by a real world example, a variable step-size integration algorithm which solves a system of ODEs originating from chemical reaction kinetics. The computational savings are substantial. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65Y05     

Methods for parallel integration of stiff systems of odes

This paper presents a class of parallel numerical integration methods for stiff systems of ordinary differential equations which can be partitioned into loosely coupled sub-systems. The formulas are called decoupled backward differentiation formulas, and they are derived from the classical formulas by restricting the implicit part to the diagnonal sub-system. With one or several sub-systems allocated to each processor, information only has to be exchanged after completion of a step but not during the solution of the nonlinear algebraic equations.The main emphasis is on the formula of order 1, the decoupled implicit Euler formula. It is proved that this formula even for a wide range of multirate formulations has an asymptotic global error expansion permitting extrapolation. Besides, sufficient conditions for absolute stability are presented.     

广义sine-Gordon方程高精度隐式紧致差分方法

本文研究一类二维非线性的广义sine-Gordon(简称SG)方程的有限差分格式.首先构造三层时间的紧致交替方向隐式差分格式,并用能量分析法证明格式具有二阶时间精度和四阶空间精度.然后应用改进的Richardson外推算法将时间精度提高到四阶.最后,数值算例证实改进后的算法在空间和时间上均达到四阶精度.     

A combined mixed finite element ADI scheme for solving Richards' equation with mixed derivatives on irregular grids

We propose and analyze an efficient numerical method for solving semilinear parabolic problems with mixed derivative terms on non-rectangular domains. The spatial semidiscretization process is based on an expanded mixed finite element scheme which, combined with suitable quadrature rules, is converted into a cell-centered finite difference scheme. This choice preserves the asymptotic accuracy and local conservation of mass of the method, while substantially reducing the computational cost of the totally discrete scheme. To obtain it, an alternating direction implicit scheme is used for the integration in time. The resulting numerical algorithm involves sets of uncoupled tridiagonal systems which can be solved in parallel. We set out some theoretical results of unconditional convergence (of second order in space and first order in time) for our method. Finally, a numerical experiment is shown in order to illustrate the theoretical results.