Twostep-by-twostep continuous PIRKN-type PC methods for nonstiff IVPs

In this paper, we start with the consideration of direct collocation-based Runge-Kutta-Nyström (RKN) methods with continuous output formulas for solving nonstiff initial-value problems (IVPs) for systems of special second-order differential equations y″(t) = f(t, y(t)). At nth step, the continuous output formulas can be used for calculating the step values at (n + 2)th step and the integration processes can be proceeded twostep-by-twostep. In this case, we obtain twostep-by-twostep RKN methods with continuous output formulas (continuous TBTRKN methods). Furthermore, we consider a parallel predictor-corrector (PC) iteration scheme using the continuous TBTRKN methods as corrector methods with predictor methods defined by the continuous output formulas. The resulting twostep-by-twostep parallel-iterated RKN-type PC methods with continuous output formulas (twostep-by-twostep continuous PIRKN-type PC methods or TBTCPIRKN methods) give us a faster integration processes. Numerical comparisons based on the solution of a few widely-used test problems show that the new TBTCPIRKN methods are much more efficient than the well-known PIRKN methods, the famous nonstiff sequential ODEX2, DOP853 codes and comparable with the CPIRKN methods.     

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.     

Parallel start for explicit parallel two-step peer methods

Explicit parallel two-step peer methods use s stages with essentially identical properties. They are quite efficient in solving standard nonstiff initial value problems and may obtain a parallel speed-up near s on s processors for expensive problems. The two-step structure requires s???1 initial approximations which have been computed by one-step methods in earlier versions. We now present a self-contained starting procedure using parallel Euler steps in the initial interval. Low order error terms introduced by this step are eliminated by special coefficient sets increasing the order to s after s???2 time steps. An estimate for the initial stepsize is discussed, as well. Parallel OpenMP experiments with realistic problems demonstrate the efficiency compared to standard codes.     

On the derivation of explicit two-step peer methods

The so-called two-step peer methods for the numerical solution of Initial Value Problems (IVP) in differential systems were introduced by R. Weiner, B.A. Schmitt and coworkers as a tool to solve different types of IVPs either in sequential or parallel computers. These methods combine the advantages of Runge-Kutta (RK) and multistep methods to obtain high stage order and therefore provide in a natural way a dense output. In particular, several explicit peer methods have been proved to be competitive with standard RK methods in a wide selection of non-stiff test problems.The aim of this paper is to propose an alternative procedure to construct families of explicit two step peer methods in which the available parameters appear in a transparent way. This allows us to obtain families of fixed stepsize s stage methods with stage order 2s−1, which provide dense output without extra cost, depending on some free parameters that can be selected taking into account the stability properties and leading error terms. A study of the extension of these methods to variable stepsize is also carried out. Optimal s stage methods with s=2,3 are derived.     

On the GPGPU parallelization issues of finite element approximate inverse preconditioning

During the past decades, explicit finite element approximate inverse preconditioning methods have been extensively used for efficiently solving sparse linear systems on multiprocessor systems. The effectiveness of explicit approximate inverse preconditioning schemes relies on the use of efficient preconditioners that are close approximants to the coefficient matrix and are fast to compute in parallel. New parallel computational techniques are proposed for the parallelization of the Optimized Banded Generalized Approximate Inverse Finite Element Matrix (OBGAIFEM) algorithm, based on the concept of the “fish bone” computational approach, and for the Explicit Preconditioned Conjugate Gradient type methods on a General Purpose Graphics Processing Unit (GPGPU). The proposed parallel methods have been implemented using Compute Unified Device Architecture (CUDA) developed by NVIDIA. Finally, numerical results for the performance of the finite element explicit approximate inverse preconditioning for solving characteristic two dimensional boundary value problems on a massive multiprocessor interface on a GPU are presented. The CUDA implementation issues of the proposed methods are also discussed.     

Twostep-by-twostep PIRK-type PC methods with continuous output formulas

This paper deals with parallel predictor–corrector (PC) iteration methods based on collocation Runge–Kutta (RK) corrector methods with continuous output formulas for solving nonstiff initial-value problems (IVPs) for systems of first-order differential equations. At n$n$th step, the continuous output formulas are used not only for predicting the stage values in the PC iteration methods but also for calculating the step values at (n+2)$(n+2)$th step. In this case, the integration processes can be proceeded twostep-by-twostep. The resulting twostep-by-twostep (TBT) parallel-iterated RK-type (PIRK-type) methods with continuous output formulas (twostep-by-twostep PIRKC methods or TBTPIRKC methods) give us a faster integration process. Fixed stepsize applications of these TBTPIRKC methods to a few widely-used test problems reveal that the new PC methods are much more efficient when compared with the well-known parallel-iterated RK methods (PIRK methods), parallel-iterated RK-type PC methods with continuous output formulas (PIRKC methods) and sequential explicit RK codes DOPRI5 and DOP853 available from the literature.     

A two-step explicit P-stable method of high phase-lag order for linear periodic IVPs

In this paper, we present a nonlinear two-step explicit P-stable method of fourth algebraic order and 12th phase-lag order for solving one-dimensional second-order linear periodic initial value problems (IVPs) of ordinary differential equations. Based on a special vector arithmetic with respect to an analytic function, the method can be extended to be vector-applicable for multi-dimensional problems directly. Some numerical results are reported to illustrate the efficiency of the method.     

Explicit Runge–Kutta pairs with lower stage-order

Explicit Runge–Kutta pairs of methods of successive orders of accuracy provide effective algorithms for approximating solutions to nonstiff initial value problems. For each explicit RK method of order of accuracy p, there is a minimum number s _p of derivative evaluations required for each step propagating the numerical solution. For p ≤ 8, Butcher has established exact values of s _p , and for p > 8, his work establishes lower bounds; otherwise, upper bounds are established by various published methods. Recently, Khashin has derived some new methods numerically, and shown that the known upper bound on s ₉ for methods of order p = 9 can be reduced from 15 to 13. His results motivate this attempt to identify parametrically exact representations for coefficients of such methods. New pairs of methods of orders 5,6 and 6,7 are characterized in terms of several arbitrary parameters. This approach, modified from an earlier one, increases the known spectrum of types of RK pairs and their derivations, may lead to the derivation of new RK pairs of higher-order, and possibly to other types of explicit algorithms within the class of general linear methods.     

Stability of collocation-based Runge-Kutta-Nyström methods

We analyse the attainable order and the stability of Runge-Kutta-Nyström (RKN) methods for special second-order initial-value problems derived by collocation techniques. Like collocation methods for first-order equations the step point order ofs-stage methods can be raised to 2s for alls. The attainable stage order is one higher and equalss+1. However, the stability results derived in this paper show that we have to pay a high price for the increased stage order.These investigations were supported by the University of Amsterdam who provided the third author with a research grant for spending a total of two years in Amsterdam.     

On the GPGPU parallelization issues of finite element approximate inverse preconditioning

During the past decades, explicit finite element approximate inverse preconditioning methods have been extensively used for efficiently solving sparse linear systems on multiprocessor systems. The effectiveness of explicit approximate inverse preconditioning schemes relies on the use of efficient preconditioners that are close approximants to the coefficient matrix and are fast to compute in parallel. New parallel computational techniques are proposed for the parallelization of the Optimized Banded Generalized Approximate Inverse Finite Element Matrix (OBGAIFEM) algorithm, based on the concept of the “fish bone” computational approach, and for the Explicit Preconditioned Conjugate Gradient type methods on a General Purpose Graphics Processing Unit (GPGPU). The proposed parallel methods have been implemented using Compute Unified Device Architecture (CUDA) developed by NVIDIA. Finally, numerical results for the performance of the finite element explicit approximate inverse preconditioning for solving characteristic two dimensional boundary value problems on a massive multiprocessor interface on a GPU are presented. The CUDA implementation issues of the proposed methods are also discussed.     

A family of highly stable second derivative block methods for stiff IVPs in ODEs

This paper considers a class of highly stable block methods for numerically solving initial value problems (IVPs) in ordinary differential equations (ODEs). The boundary locus of the proposed parallel one-block, r-output point algorithms shows that the new schemes are A-stable for output points r = 2(2)8 and A(α)-stable for output points r = 10(2)20, where r is the number of processors in a particular block method in the family. Numerical results of the block methods are compared with the second derivative linear multistep method in [8].     

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 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.     

A class of explicit two-step hybrid methods for second-order IVPs

A class of explicit two-step hybrid methods for the numerical solution of second-order IVPs is presented. These methods require a reduced number of stages per step in comparison with other hybrid methods proposed in the scientific literature. New explicit hybrid methods which reach up to order five and six with only three and four stages per step, respectively, and which have optimized the error constants, are constructed. The numerical experiments carried out show the efficiency of our explicit hybrid methods when they are compared with classical Runge–Kutta–Nyström methods and other explicit hybrid codes proposed in the scientific literature.     

On the choice of correctors for semi-implicit Picard deferred correction methods

The goal of this study is to assess the implications of the choice of correctors for semi-implicit Picard integral deferred correction (SIPIDC) methods. The SIPIDC methods previously developed compute a high-order approximation by first computing a low-order provisional solution using a semi-implicit method and then using a first-order semi-implicit method to solve a series of correction equations, each of which raises the order of accuracy of the solution by one. In this study, we examine the efficiency of SIPIDC methods that instead use standard second-order semi-implicit methods to solve the correction equations. The accuracy, efficiency, and stability of the resulting methods are compared to previously developed methods, in the context of both nonstiff and stiff problems.     

On the order bound of one-point algebraic geometry codes

Let S={s_i}_i∈N⊆N be a numerical semigroup. For each i∈N, let ν(s_i) denote the number of pairs (s_i−s_j,s_j)∈S²: it is well-known that there exists an integer m such that the sequence {ν(s_i)}_i∈N is non-decreasing for i>m. The problem of finding m is solved only in special cases. By way of a suitable parameter t, we improve the known bounds for m and in several cases we determine m explicitly. In particular we give the value of m when the Cohen-Macaulay type of the semigroup is three or when the multiplicity is less than or equal to six. When S is the Weierstrass semigroup of a family {C_i}_i∈N of one-point algebraic geometry codes, these results give better estimates for the order bound on the minimum distance of the codes {C_i}.     

Shape Preserving Interpolatory Subdivision Schemes for Nonuniform Data

This article is concerned with a class of shape preserving four-point subdivision schemes which are stationary and which interpolate nonuniform univariate data {(x_i, f_i)}. These data are functional data, i.e., x_i≠x_j if i≠j. Subdivision for the strictly monotone x-values is performed by a subdivision scheme that makes the grid locally uniform. This article is concerned with constructing suitable subdivision methods for the f-data which preserve convexity; i.e., the data at the kth level, {x^(k)_i, f_i(k)} is a convex data set for all k provided the initial data are convex. First, a sufficient condition for preservation of convexity is presented. Additional conditions on the subdivision methods for convergence to a C¹ limit function are given. This leads to explicit rational convexity preserving subdivision schemes which generate continuously differentiable limit functions from initial convex data. The class of schemes is further restricted to schemes that reproduce quadratic polynomials. It is proved that these schemes are third order accurate. In addition, nonuniform linear schemes are examined which extend the well-known linear four-point scheme to the case of nonuniform data. Smoothness of the limit function generated by these linear schemes is proved by using the well-known smoothness criteria of the uniform linear four-point scheme.     

Stability of explicit ARKN methods for perturbed oscillators

The stability of explicit ARKN methods for the numerical integration of perturbed oscillators is analyzed. Stability regions for the second-order homogeneous linear test model are obtained. These stability regions represent a generalization of the stability intervals for the classical RKN methods.     

Adaptive nested implicit Runge–Kutta formulas of Gauss type

This paper deals with a special family of implicit Runge–Kutta formulas of orders 2, 4 and 6. These methods are of Gauss type; i.e., they are based on Gauss quadrature formulas of orders 2, 4 and 6, respectively. However, the methods under discussion have only explicit internal stages that lead to cheap practical implementation. Some of the stage values calculated in a step of the numerical integration are of sufficiently high accuracy that allows for dense output of the same order as the Runge–Kutta formula used. On the other hand, the methods developed are A-stable, stiffly accurate and symmetric. Moreover, they are conjugate to a symplectic method up to order 6 at least. All of these make the new methods attractive for solving nonstiff and stiff ordinary differential equations, including Hamiltonian and reversible problems. For adaptivity, different strategies of error estimation are discussed and examined numerically.     

The use of second degree normalized implicit conjugate gradient methods for solving large sparse systems of linear equations

Second degree normalized implicit conjugate gradient methods for the numerical solution of self-adjoint elliptic partial differential equations are developed. A proposal for the selection of certain values of the iteration parameters ?_i, γ_i involved in solving two and three-dimensional elliptic boundary-value problems leading to substantial savings in computational work is presented. Experimental results for model problems are given.