Superconvergent explicit two-step peer methods

We consider explicit two-step peer methods for the solution of nonstiff differential systems. By an additional condition a subclass of optimally zero-stable methods is identified that is superconvergent of order p=s+1$p=s+1$, where s$s$ is the number of stages. The new condition allows us to reduce the number of coefficients in a numerical search for good methods. We present methods with 4–7 stages which are tested in FORTRAN90 and compared with DOPRI5 and DOP853. The results confirm the high potential of the new class of methods.     

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.     

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.     

Positivity for explicit two-step methods in linear multistep and one-leg form

Positivity results are derived for explicit two-step methods in linear multistep form and in one-leg form. It turns out that, using the forward Euler starting procedure, the latter form allows a slightly larger step size with respect to positivity. AMS subject classification (2000) 65L06     

Ninth-order,explicit, two-step methods for second-order inhomogeneous linear IVPs

In the present paper, the second-order linear inhomogeneous initial value problems (LI-IVP) with constant coefficients is of our interest. Two-step hybrid methods (ie, of Numerov-type) are considered for addressing this problem. Thus, a special set of order conditions is given and solved for derivation a low cost new method. Actually, we manage to save two stages per step. This is crucial as shown in various numerical tests where our new proposal outperforms standard methods in the relevant literature.     

On the stability of two new two-step explicit methods for the numerical integration of second order initial value problem on a variable mesh

We present two novel two-step explicit methods for the numerical solution of the second order initial value problem on a variable mesh. In the case of a constant mesh the method is superstable in the sense of Chawla (1985). Numerical experimentation is provided to verify the stability analysis.     

An improved two-step method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010).     

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.     

Towards explicit methods for differential algebraic equations

Explicit methods have previously been proposed for parabolic PDEs and for stiff ODEs with widely separated time constants. We discuss ways in which Differential Algebraic Equations (DAEs) might be regularized so that they can be efficiently integrated by explicit methods. The effectiveness of this approach is illustrated for some simple index three problems. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65-L80, 34-04     

Derivation of continuous explicit two-step Runge–Kutta methods of order three

We describe a construction of continuous extensions to a new representation of two-step Runge–Kutta methods for ordinary differential equations. This representation makes possible the accurate and reliable estimation of local discretization error, facilitates the efficient implementation of these methods in variable stepsize environment, and adapts readily to the numerical solution of a class of delay differential equations. A number of numerical tests carried out on the obtained methods of order 3 with quadratic interpolants show their efficiency and robust performance which allow them to compete with the state-of-the-art dde23 code from Matlab.     

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.     

On the economization of explicit Runge-Kutta methods

A modification to explicit Runge-Kutta (RK) methods is proposed. Schemes are constructed which require less derivative-evaluations to achieve a certain order than the classical RK methods do. As an example, we give a second-order method requiring one evaluation, two third-order methods using one and two evaluations, respectively and finally a fourth-order method which requires two evaluations. Numerical examples illustrate the behaviour of these schemes.     

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.     

Projected explicit lawson methods for the integration of Schrödinger equation

In this article, it is proved that explicit Lawson methods, when projected onto one of the invariants of nonlinear Schrödinger equation (norm) are also automatically projected onto another invariant (momentum) for many solutions. As this procedure is very cheap and geometric because two invariants are conserved, it offers an efficient tool to integrate some solutions of this equation till long times. On the other hand, we show a detailed study on the numerical performance of these methods against splitting ones, with fixed and variable stepsize implementation. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq31: 78–104, 2015     

Construction of highly stable parallel two-step Runge–Kutta methods for delay differential equations

It is shown that any A-stable two-step Runge–Kutta method of order and stage order for ordinary differential equations can be extended to the P-stable method of uniform order for delay differential equations.     

Global optimization of explicit strong-stability-preserving Runge-Kutta methods

Strong-stability-preserving Runge-Kutta (SSPRK) methods are a type of time discretization method that are widely used, especially for the time evolution of hyperbolic partial differential equations (PDEs). Under a suitable stepsize restriction, these methods share a desirable nonlinear stability property with the underlying PDE; e.g., positivity or stability with respect to total variation. This is of particular interest when the solution exhibits shock-like or other nonsmooth behaviour. A variety of optimality results have been proven for simple SSPRK methods. However, the scope of these results has been limited to low-order methods due to the detailed nature of the proofs. In this article, global optimization software, BARON, is applied to an appropriate mathematical formulation to obtain optimality results for general explicit SSPRK methods up to fifth-order and explicit low-storage SSPRK methods up to fourth-order. Throughout, our studies allow for the possibility of negative coefficients which correspond to downwind-biased spatial discretizations. Guarantees of optimality are obtained for a variety of third- and fourth-order schemes. Where optimality is impractical to guarantee (specifically, for fifth-order methods and certain low-storage methods), extensive numerical optimizations are carried out to derive numerically optimal schemes. As a part of these studies, several new schemes arise which have theoretically improved time-stepping restrictions over schemes appearing in the recent literature.

     

On the choice of explicit stabilizing terms in column generation

Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of columns need to be solved. Although successfully employed in many applications, these approaches suffer from well-known instability issues that somewhat limit their efficiency. Building on the theory developed for nondifferentiable optimization algorithms, a large class of stabilized column generation algorithms can be defined which avoid the instability issues by using an explicit stabilizing term in the dual; this amounts at considering a (generalized) augmented Lagrangian of the primal master problem. Since the theory allows for a great degree of flexibility in the choice and in the management of the stabilizing term, one can use piecewise-linear or quadratic functions that can be efficiently dealt with using off-the-shelf solvers. The practical effectiveness of this approach is demonstrated by extensive computational experiments on large-scale Vehicle and Crew Scheduling problems. Also, the results of a detailed computational study on the impact of the different choices in the stabilization term (shape of the function, parameters), and their relationships with the quality of the initial dual estimates, on the overall effectiveness of the approach are reported, providing practical guidelines for selecting the most appropriate variant in different situations.     

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.     

A two-step modulus-based multisplitting iteration method for the nonlinear complementarity problem

In this paper, we construct a two-step modulus-based multisplitting iteration method based on multiple splittings of the system matrix for the nonlinear complementarity problem. And we prove its convergence when the system matrix is an $H$-matrix with positive diagonal elements. Numerical experiments show that the proposed method is efficient.