One-step 9-stage Hermite–Birkhoff–Taylor DAE solver of order 10

The HBT(10)9 method for ODEs is expanded into HBT(10)9DAE for solving nonstiff and moderately stiff systems of fully implicit differential algebraic equations (DAEs) of arbitrarily high fixed index. A scheme to generate first-order derivatives at off-step points is combined with Pryce scheme which generates high order derivatives at step points. The stepsize is controlled by a local error estimator. HBT(10)9DAE uses only the first four derivatives of y instead of the first 10 required by Taylor’s series method T10DAE of order 10. Dormand–Prince’s DP(8,7)13M for ODEs is extended to DP(8,7)DAE for DAEs. HBT(10)9DAE wins over DP(8,7)DAE on several test problems on the basis of CPU time as a function of relative error at the end of the interval of integration. An index-5 problem is equally well solved by HBT(10)9DAE and T10DAE. On this problem, the error in the solution by DP(8,7)DAE increases as time increases.     

One-step 5-stage Hermite-Birkhoff-Taylor ODE solver of order 12

A one-step 5-stage Hermite-Birkhoff-Taylor method, HBT(12)5, of order 12 is constructed for solving nonstiff systems of differential equations y^′=f(t,y), y(t₀)=y₀, where y∈Rⁿ. The method uses derivatives y^′ to y⁽⁹⁾ as in Taylor methods combined with a 5-stage Runge-Kutta method. Forcing an expansion of the numerical solution to agree with a Taylor expansion of the true solution to order 12 leads to Taylor- and Runge-Kutta-type order conditions which are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. HBT(12)5 has a larger interval of absolute stability than Dormand-Prince DP(8, 7)13M and Taylor method T12 of order 12. The new method has also a smaller norm of principal error term than T12. It is superior to DP(8, 7)13M and T12 on the basis the number of steps, CPU time and maximum global error on common test problems. The formulae of HBT(12)5 are listed in an appendix.     

A one-step 7-stage Hermite-Birkhoff-Taylor ODE solver of order 11

A one-step 7-stage Hermite-Birkhoff-Taylor method of order 11, denoted by HBT(11)7, is constructed for solving nonstiff first-order initial value problems y^′=f(t,y), y(t₀)=y₀. The method adds the derivatives y^′ to y⁽⁶⁾, used in Taylor methods, to a 7-stage Runge-Kutta method of order 6. Forcing an expansion of the numerical solution to agree with a Taylor expansion of the true solution to order 11 leads to Taylor- and Runge-Kutta-type order conditions. These conditions are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. The new method has a larger scaled interval of absolute stability than the Dormand-Prince DP87 and a larger unscaled interval of absolute stability than the Taylor method, T11, of order 11. HBT(11)7 is superior to DP87 and T11 in solving several problems often used to test higher-order ODE solvers on the basis of the number of steps, CPU time, and maximum global error. Numerical results show the benefit of adding high-order derivatives to Runge-Kutta methods.     

One-step 9-stage Hermite–Birkhoff–Taylor ODE solver of order 10

A one-step 9-stage Hermite–Birkhoff–Taylor method of order 10, denoted by HBT(10)9, is constructed for solving nonstiff systems of first-order differential equations of the form y′=f(x,y), y(x ₀)=y ₀. The method uses y′ and higher derivatives y ⁽²⁾ to y ⁽⁴⁾ as in Taylor methods and is combined with a 9-stage Runge–Kutta method. Forcing a Taylor expansion of the numerical solution to agree with an expansion of the true solution leads to Taylor- and Runge–Kutta-type order conditions which are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. The new method has a larger scaled interval of absolute stability than Dormand–Prince DP(8,7)13M. The stepsize is controlled by means of y ⁽²⁾ and y ⁽⁴⁾. HBT(10)9 is superior to DP(8,7)13M and Taylor method of order 10 in solving several problems often used to test high-order ODE solvers on the basis of the number of steps, CPU time, and maximum global error. These numerical results show the benefits of adding high-order derivatives to Runge–Kutta methods.     

A new class of efficient one-step contractivity preserving high-order time discretization methods of order 5 to 14

A family of one-step, explicit, contractivity preserving, multi-stage, multi-derivative, Hermite–Birkhoff–Taylor methods of order p =?5,6,…,14, that we denote by CPHBT_RK4(d,s,p), with nonnegative coefficients are constructed by casting s-stage Runge–Kutta methods of order 4 with Taylor methods of order d. The constructed CPHBT_RK4 methods are implemented using efficient variable step control and are compared to other well-known methods on a variety of initial value problems. A selected method: CP 6-stages 9-derivative HBT method of order 12, denoted by CPHBTRK412, has larger region of absolute stability than Dormand–Prince DP(8,7)13M and Taylor method T(12) of order 12. It is superior to DP(8,7)13M and T(12) methods on the basis the number of steps, CPU time, and maximum global error on several problems often used to test higher-order ODE solvers. Also, we show that the contractivity preserving property of CPHBTRK412is very efficient in suppressing the effect of the propagation of discretization errors and the new method compares positively with explicit 17 stages Runge-Kutta-Nyström pair of order 12 by Sharp et al. on a long-term integration of a standard N-body problem. The selected CPHBTRK412is listed in the Appendix.     

A three-stage, VSVO, Hermite-Birkhoff-Taylor, ODE solver

The new variable-step, variable-order, ODE solver, HBT(p) of order p, presented in this paper, combines a three-stage Runge-Kutta method of order 3 with a Taylor series method of order p-2 to solve initial value problems , where y:R→R^d and f:R×R^d→R^d. The order conditions satisfied by HBT(p) are formulated and they lead to Vandermonde-type linear algebraic systems whose solutions are the coefficients in the formulae for HBT(p). A detailed formulation of variable-step HBT(p) in both fixed-order and variable-order modes is presented. The new method and the Taylor series method have similar regions of absolute stability. To obtain high-accuracy results at high order, this method has been implemented in multiple precision.     

Variable-step variable-order 3-stage Hermite-Birkhoff-Obrechkoff DDE solver of order 4 to 14

This article presents a solver for delay differential equations (DDEs) called HBO414DDE based on a hybrid variable-step variable-order 3-stage Hermite-Birkhoff-Obrechkoff ODE solver of order 4 to 14. The current version of our method solves DDEs with state dependent, non-vanishing, small, vanishing and asymptotically vanishing delays, except neutral type and initial value DDEs. Delayed values are computed using Hermite interpolation, small delays are dealt with by extrapolation, and discontinuities are located by a bisection method. HBO414DDE was tested on several problems and results were compared with those of known solvers like SYSDEL and the recent Matlab DDE solver ddesd and statistics show that it gives, most of the time, a smaller relative error than the other solvers for the same number of function evaluations.     

Solving differential-algebraic equations by Taylor series (II): Computing the System Jacobian

The authors have developed a Taylor series method for solving numerically an initial-value problem differential-algebraic equation (DAE) that can be of high index, high order, nonlinear, and fully implicit, BIT, 45 (2005), pp. 561–592. Numerical results have shown that this method is efficient and very accurate. Moreover, it is particularly suitable for problems that are of too high an index for present DAE solvers. This paper develops an effective method for computing a DAE’s System Jacobian, which is needed in the structural analysis of the DAE and computation of Taylor coefficients. Our method involves preprocessing of the DAE and code generation employing automatic differentiation. Theory and algorithms for preprocessing and code generation are presented. An operator-overloading approach to computing the System Jacobian is also discussed. AMS subject classification (2000)  34A09, 65L80, 65L05, 41A58     

Handling kinematic loops of mobile machinery in real-time applications

This paper compares different mathematical approaches for handling kinematic loops in real-time applications by looking at the linkage arrangement of a wheel loader. All constraints must be satisfied on position level and no special integration algorithm is assumed. Classical DAE formulations and an ODE formulation based on coordinate partitioning are considered and compared together with four different explicit and linear-implicit solvers suitable for real-time applications. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Numerical Taylor expansions of invariant manifolds in large dynamical systems

Summary. In this paper we develop a numerical method for computing higher order local approximations of invariant manifolds, such as stable, unstable or center manifolds near steady states of a dynamical system. The underlying system is assumed to be large in the sense that a large sparse Jacobian at the equilibrium occurs, for which only a linear (black box) solver and a low dimensional invariant subspace is available, but for which methods like the QR–Algorithm are considered to be too expensive. Our method is based on an analysis of the multilinear Sylvester equations for the higher derivatives which can be solved under certain nonresonance conditions. These conditions are weaker than the standard gap conditions on the spectrum which guarantee the existence of the invariant manifold. The final algorithm requires the solution of several large linear systems with a bordered Jacobian. To these systems we apply a block elimination method recently developed by Govaerts and Pryce [12, 14]. Received March 12, 1996 / Revised version reveiced August 8, 1997     

Solving Differential-Algebraic Equations by Taylor Series (I): Computing Taylor Coefficients

This paper is one of a series underpinning the authors’ DAETS code for solving DAE initial value problems by Taylor series expansion. First, building on the second author’s structural analysis of DAEs (BIT, 41 (2001), pp. 364–394), it describes and justifies the method used in DAETS to compute Taylor coefficients (TCs) using automatic differentiation. The DAE may be fully implicit, nonlinear, and contain derivatives of order higher than one. Algorithmic details are given. Second, it proves that either the method succeeds in the sense of computing TCs of the local solution, or one of a number of detectable error conditions occurs. AMS subject classification (2000) 34A09, 65L80, 65L05, 41A58     

Run time estimation of the spectral radius of Jacobians

It is useful for ordinary differential equation (ODE) solvers to include an estimator of the spectral radius of the Jacobian matrix of the system of ODE's, since this determines the numerical stability of the method. Hence a knowledge of spectral radius enables the run time selection of a more efficient integrator. Some techniques for estimating spectral radius are described and compared. They include methods suitable for use with any ODE solvers, but which require additional computation. Other methods are described which are suitable with Runge-Kutta or Rosenbrock methods, and which require little extra computation.     

On variable step Hermite–Birkhoff solvers combining multistep and 4-stage DIRK methods for stiff ODEs

Variable-step (VS) 4-stage k-step Hermite–Birkhoff (HB) methods of order p = (k + 2), p = 9, 10, denoted by HB (p), are constructed as a combination of linear k-step methods of order (p ? 2) and a diagonally implicit one-step 4-stage Runge–Kutta method of order 3 (DIRK3) for solving stiff ordinary differential equations. Forcing a Taylor expansion of the numerical solution to agree with an expansion of the true solution leads to multistep and Runge–Kutta type order conditions which are reorganized into linear confluent Vandermonde-type systems. This approach allows us to develop L(a)-stable methods of order up to 11 with a > 63°. Fast algorithms are developed for solving these systems in O (p²) operations to obtain HB interpolation polynomials in terms of generalized Lagrange basis functions. The stepsizes of these methods are controlled by a local error estimator. HB(p) of order p = 9 and 10 compare favorably with existing Cash modified extended backward differentiation formulae of order 7 and 8, MEBDF(7-8) and Ebadi et al. hybrid backward differentiation formulae of order 10 and 12, HBDF(10-12) in solving problems often used to test higher order stiff ODE solvers on the basis of CPU time and error at the endpoint of the integration interval.     

Computational uncertainty and the application of a high-performance multiple precision scheme to obtaining the correct reference solution of Lorenz equations

The computational uncertainty principle (CUP) is applied to explain the experimental formulae of the critical time of decoupling for Lorenz equations (LEs). We apply the multiple precision (MP) library in obtaining the long-time solution of LEs, and based on the classic Taylor scheme, we developed a high-performance parallel Taylor solver to do the computation. The new solver is several hundreds times faster than the reported solvers developed in MATHEMATICA software, and it has the ability to yield longer solutions of LEs, up to t ∼ 10⁴ LTU (Lorenz time unit). Further, we notice that the two computation processes with different precisions or orders will produce the reliable correct reference solutions before they have a significant difference. According to this property we propose an approach for maintaining the correct numerical solution. The new solver and the solution validation approach are used to identify and correct an erroneous solution reported in a previous study.     

An efficient time-step-based self-adaptive algorithm for predictor-corrector methods of Runge-Kutta type

Finding an efficient implementation variant for the numerical solution of problems from computational science and engineering involves many implementation decisions that are strongly influenced by the specific hardware architecture. The complexity of these architectures makes it difficult to find the best implementation variant by manual tuning. For numerical solution methods from linear algebra, auto-tuning techniques based on a global search engine as they are used for ATLAS or FFTW can be used successfully. These techniques generate different implementation variants at installation time and select one of these implementation variants either at installation time or at runtime, before the computation starts. For some numerical methods, auto-tuning at installation time cannot be applied directly, since the best implementation variant may strongly depend on the specific numerical problem to be solved. An example is solution methods for initial value problems (IVPs) of ordinary differential equations (ODEs), where the coupling structure of the ODE system to be solved has a large influence on the efficient use of the memory hierarchy of the hardware architecture. In this context, it is important to use auto-tuning techniques at runtime, which is possible because of the time-stepping nature of ODE solvers.In this article, we present a sequential self-adaptive ODE solver that selects the best implementation variant from a candidate pool at runtime during the first time steps, i.e., the auto-tuning phase already contributes to the progress of the computation. The implementation variants differ in the loop structure and the data structures used to realize the numerical algorithm, a predictor-corrector (PC) iteration scheme with Runge-Kutta (RK) corrector considered here as an example. For those implementation variants in the candidate pool that use loop tiling to exploit the memory hierarchy of a given hardware platform we investigate the selection of tile sizes. The self-adaptive ODE solver combines empirical search with a model-based approach in order to reduce the search space of possible tile sizes. Runtime experiments demonstrate the efficiency of the self-adaptive solver for different IVPs across a range of problem sizes and on different hardware architectures.     

Quadratic Störmer‐type methods for the solution of the Boussinesq equation by the method of lines

We study the numerical treatment of Boussinesq PDE equation using the method of lines. For the space discretization, we choose either classical finite differences or Fourier pseudospectral methods. Both cases result in a system of second‐order ordinary differential equations (ODEs) that is quadratic. In order to take advantage of this special feature, we choose to solve the ODE system using a new type of hybrid Numerov method specially constructed for such problems. Other efficient ODE solvers taken from the literature are used to solve the system of ODEs as well. By taking all the combinations of space discretization methods and ODE solvers, we discuss the stability and accuracy features revealed from the numerical tests. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2008     

Constrained least squares methods for linear timevarying DAE systems

Summary This paper presents a family of methods for accurate solution of higher index linear variable DAE systems, . These methods use the DAE system and some of its first derivatives as constraints to a least squares problem that corresponds to a Taylor series ofy, or an approximative equality derived from a Pade' approximation of the exponential function. Accuracy results for systems transformable to standard canonical form are given. Advantages, disadvantages, stability properties and implementation of these methods are discussed and two numerical examples are given, where we compare our results with results from more traditional methods.     

Performance comparison of the NWF and DC methods for implementing High-Resolution schemes in a fully coupled incompressible flow solver

This paper reports on the use of the Normalized Weighting Factor (NWF) method and the Deferred Correction (DC) approach for the implementation of High Resolution (HR) convective schemes in an implicit, fully coupled, pressure-based flow solver. Four HR schemes are realized within the framework of the NWF and DC methods and employed to solve the following three laminar flow problems: (i) lid-driven flow in a square cavity, (ii) sudden expansion in a square cavity, and (iii) flow in a planar T-junction, over three grid systems with sizes of 10⁴, 5 × 10⁴, and 3 × 10⁵ control volumes. The merit of both approaches is demonstrated by comparing the computational costs required to solve these problems using the various HR schemes on the different grid systems. Whereas previous attempts to use the NWF method in a segregated flow solver failed to produce converged solutions, current results clearly demonstrate that both methods are suitable for utilization in a coupled flow solver. In terms of CPU efficiency, there is no global and consistent superiority of any method over another even though the DC method outperformed the NWF method in two of the three test problems solved.     

A class of split-step balanced methods for stiff stochastic differential equations

In this paper we design a class of general split-step balanced methods for solving It? stochastic differential systems with m-dimensional multiplicative noise, in which the drift or deterministic increment function can be taken from any chosen one-step ODE solver. We then give an analysis of their order of strong convergence in a general setting, but for the mean-square stability analysis, we confine our investigation to a special case in which the drift increment function of the methods is replaced by the one from the well known Rosenbrock method. The resulting class of stochastic differential equation (SDE) solvers will have more appropriate and useful mean-square stability properties for SDEs with stiffness in their drift and diffusion parts, compared to some other already reported split-step balanced methods. Finally, numerical results show the effectiveness of these methods.