High-order convergent deferred correction schemes based on parameterized Runge–Kutta–Nyström methods for second-order boundary value problems

Iterated deferred correction is a widely used approach to the numerical solution of first-order systems of nonlinear two-point boundary value problems. Normally, the orders of accuracy of the various methods used in a deferred correction scheme differ by 2 and, as a direct result, each time deferred correction is used the order of the overall scheme is increased by a maximum of 2. In [16], however, it has been shown that there exist schemes based on parameterized Runge–Kutta methods, which allow a higher increase of the overall order. A first example of such a high-order convergent scheme which allows an increase of 4 orders per deferred correction was based on two mono-implicit Runge–Kutta methods. In the present paper, we will investigate the possibility for high-order convergence of schemes for the numerical solution of second-order nonlinear two-point boundary value problems not containing the first derivative. Two examples of such high-order convergent schemes, based on parameterized Runge–Kutta-Nyström methods of orders 4 and 8, are analysed and discussed.     

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.     

Numerically stable,scalable formulas for parallel and online computation of higher-order multivariate central moments with arbitrary weights

Formulas for incremental or parallel computation of second order central moments have long been known, and recent extensions of these formulas to univariate and multivariate moments of arbitrary order have been developed. Such formulas are of key importance in scenarios where incremental results are required and in parallel and distributed systems where communication costs are high. We survey these recent results, and improve them with arbitrary-order, numerically stable one-pass formulas which we further extend with weighted and compound variants. We also develop a generalized correction factor for standard two-pass algorithms that enables the maintenance of accuracy over nearly the full representable range of the input, avoiding the need for extended-precision arithmetic. We then empirically examine algorithm correctness for pairwise update formulas up to order four as well as condition number and relative error bounds for eight different central moment formulas, each up to degree six, to address the trade-offs between numerical accuracy and speed of the various algorithms. Finally, we demonstrate the use of the most elaborate among the above mentioned formulas, with the utilization of the compound moments for a practical large-scale scientific application.     

Deferred corrections using uncentered end formulas

Summary The trapezoidal rule with deferred corrections using uncentered end formulas is shown to converge. While the proof technique is more specialized than the standard asymptotic expansion approach, it has some advantages. In addition to providing a more complete theoretical justification for current implementations of deferred corrections with the trapezoidal rule, the approach given here will hopefully apply for several other discretization methods.     

Numerical analysis of a second order algorithm for simplified magnetohydrodynamic flows

In this paper, we construct a second order algorithm based on the spectral deferred correction method for the time-dependent magnetohydrodynamics flows at a low magnetic Reynolds number. We present a complete theoretical analysis to prove that this algorithm is unconditionally stable, consistent and second order accuracy. Finally, two numerical examples are given to illustrate the convergence and effectiveness of our algorithm.     

Mono-implicit Runge–Kutta formulae for the numerical solution of second order nonlinear two-point boundary value problems

Mono-implicit Runge–Kutta (MIRK) formulae are widely used for the numerical solution of first order systems of nonlinear two-point boundary value problems. In order to avoid costly matrix multiplications, MIRK formulae are usually implemented in a deferred correction framework and this is the basis of the well known boundary value code TWPBVP. However, many two-point boundary value problems occur naturally as second (or higher) order equations or systems and for such problems there are significant savings in computational effort to be made if the MIRK methods are tailored for these higher order forms. In this paper, we describe MIRK algorithms for second order equations and report numerical results that illustrate the substantial savings that are possible particularly for second order systems of equations where the first derivative is absent.     

Deferred Correction Methods for Initial Value Problems

In this paper we derive high order implicit difference methods for large systems of ODE. The methods are based on the deferred correction principle, yielding accuracy of order p by applying the trapezoidal rule p/2 times in each timestep. Numerical experiments demonstrate the efficiency of the method.This revised version was published online in October 2005 with corrections to the Cover Date.     

On quasi-Newton and pseudo-Newton algorithms

This paper surveys some of the existing approaches to quasi-Newton methods and introduces a new way for constructing inverse Hessian approximations for such algorithms. This new approach is based on restricting Newton's method to subspaces over which the inverse Hessian is assumed to be known, while expanding this subspace using gradient information. It is shown that this approach can lead to some well-known formulas for updating the inverse Hessian approximation. Deriving such updates through this approach provides new understanding of these formulas and their relation to the pseudo-Newton-Raphson algorithm.     

Stabilized semi‐implicit spectral deferred correction methods for Allen–Cahn and Cahn–Hilliard equations

Stabilized semi‐implicit spectral deferred correction methods are constructed for the time discretization of Allen–Cahn and Cahn–Hilliard equations. These methods are unconditionally stable, lead to simple linear system to solve at each iteration, and can achieve high‐order time accuracy with a few iterations in each time step. Ample numerical results are presented to demonstrate the effectiveness of the stabilized semi‐implicit spectral deferred correction methods for solving the Allen–Cahn and Cahn–Hilliard equations. Copyright © 2013 John Wiley & Sons, Ltd.     

Multipliers‐free dual‐primal domain decomposition methods for nonsymmetric matrices and their numerical testing

The most commonly used nonoverlapping domain decomposition algorithms, such as the FETI‐DP and BDDC, require the introduction of discontinuous vector spaces. Most of the works on such methods are based on approaches that originated in Lagrange multipliers formulations. Using a theory of partial differential equations formulated in discontinuous piecewise‐defined functions, introduced and developed by Herrera and his collaborators through a long time span, recently the authors have developed an approach to domain decomposition methods in which general problems with prescribed jumps are treated at the discrete level. This yields an elegant and general direct framework that permits analyzing the problems in greater detail. The algorithms derived using it have properties similar to those of well‐established methods such as FETI‐DP, but, in our experience, they are easier to implement. Also, they yield explicit matrix formulas that unify the different methods. Furthermore, this multipliers‐free framework has permitted us to extend such formulas to make them applicable to nonsymmetric matrices. The extension of the unifying matrix formulas to nonsymmetric matrices is the subject matter of the present article. A conspicuous result is that in numerical experiments in 2D and 3D, the MF‐DP algorithms for nonsymmetric matrices exhibit an efficiency of the same order as state‐of‐the‐art algorithms for symmetric matrices, such as BDDC, FETI‐DP, and MF‐DP.© 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1262‐1289, 2011     

AnO(h 6) quintic spline collocation method for fourth order two-point boundary value problems

AnO(h ⁶) collocation method based on quintic splines is developed and analyzed for general fourth-order linear two-point boundary value problems. The method determines a quintic spline approximation to the solution by forcing it to satisfy a high order perturbation of the original boundary value problem at the nodal points of the spline. A variation of this method is formulated as a deferred correction method. The error analysis of the new method and its numerical behavior is presented.This research was supported by AFOSR grant 84-0385.     

Decomposition method for solving multi-species reactive transport problems coupled with first-order kinetics applicable to a chain with identical reaction rates

A new method for decomposing of multiple solute transport equations, coupled by first-order reactions, is developed. The approach is based on the semigroup theory and reduces the multi-species problem to single-species equations with various initial and boundary conditions. Analytical formulas are derived for all reactants. This new method overcomes some of the limitations that were implicit in previously published algorithms. More exactly, the derivation of closed formulas for a reaction chain with identical reaction rates is possible. The proposed approach is flexible for solving one-, two- or three-dimensional advection-dispersion systems. The methodology is demonstrated on the reductive biodegradation of chlorinated solvents, such as tetrachloroethene (PCE) and trichloroethene (TCE).     

A fractional partial differential equation based multiscale denoising model for texture image

Traditional integer‐order partial differential equation based image denoising approach can easily lead edge and complex texture detail blur, thus its denoising effect for texture image is always not well. To solve the problem, we propose to implement a fractional partial differential equation (FPDE) based denoising model for texture image by applying a novel mathematical method—fractional calculus to image processing from the view of system evolution. Previous studies show that fractional calculus has some unique properties that it can nonlinearly enhance complex texture detail in digital image processing, which is obvious different with integer‐order differential calculus. The goal of the modeling is to overcome the problems of the existed denoising approaches by utilizing the aforementioned properties of fractional differential calculus. Using classic definition and property of fractional differential calculus, we extend integer‐order steepest descent approach to fractional field to implement fractional steepest descent approach. Then, based on the earlier fractional formulas, a FPDE based multiscale denoising model for texture image is proposed and further analyze optimal parameters value for FPDE based denoising model. The experimental results prove that the ability for preserving high‐frequency edge and complex texture information of the proposed fractional denoising model are obviously superior to traditional integral based algorithms, as for texture detail rich images. Copyright © 2013 John Wiley & Sons, Ltd.     

An algorithm for the computation of consistent initial values for differential–algebraic equations

We use boundary value methods to compute consistent initial values for fully implicit nonlinear differential-algebraic equations. The obtained algorithm uses variable order formulae and a deferred correction technique to evaluate the error. A rigorous theory is stated for nonlinear index 1, 2 and 3 DAEs of Hessenberg form. Numerical tests on classical index 1, 2 and 3 DAE problems are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Summatory Functions of Digital Sums Occurring in Cryptography

Morain and Olivos gave two algorithms that allow fast exponentiation in elliptic curve cryptosystems. These algorithms are based on representations of integers in certain redundant binary number systems. In this paper we consider the weight and the sum of digits function of these representations. In particular, we give formulas for their summatory functions. In the proofs we use the Mellin-Perron formula. In order to apply this formula, we have to compute the analytic continuation of a class of Dirichlet series.     

A high accuracy minimally invasive regularization technique for navier–stokes equations at high reynolds number

A method is presented, that combines the defect and deferred correction approaches to approximate solutions of Navier–Stokes equations at high Reynolds number. The method is of high accuracy in both space and time, and it allows for the usage of legacy codes a frequent requirement in the simulation of turbulent flows in complex geometries. The two‐step method is considered here; to obtain a regularization that is second order accurate in space and time, the method computes a low‐order accurate, stable, and computationally inexpensive approximation (Backward Euler with artificial viscosity) twice. The results are readily extendable to the higher order accuracy cases by adding more correction steps. Both the theoretical results and the numerical tests provided demonstrate that the computed solution is stable and the accuracy in both space and time is improved after the correction step. We also perform a qualitative test to demonstrate that the method is capable of capturing qualitative features of a turbulent flow, even on a very coarse mesh. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 814–839, 2017     

On the order of deferred correction

New deferred correction methods for the numerical solution of initial value problems in ordinary differential equations have recently been introduced by Dutt, Greengard and Rokhlin. A convergence proof is presented for these methods, based on the abstract Stetter-Lindberg-Skeel framework and Spijker-type norms. It is shown that p corrections of an order-r one-step solver yield order-r(p+1) accuracy.     

Implementation of chebyshevian linear multistep formulas

A Chebyshevian linear multistep formula is a formula fitted to a Chebyshev set of basis functions. This paper presents a unified approach for the implementation of Chebyshevian backward differentiation and Adams formulas for solving ordinary differential equations. The approach is based on generalized scaled differences, derived from generalized divided differences, and it includes the generalized Newton interpolation formula as predictor for the Chebyshevian implicit backward differentiation formula and Chebyshevian Adams-Bashforth-Moulton formulas. The local truncation errors are estimated by means of the scaled differences providing information for the control of order and steplength.     

Extrapolation with spline-collocation methods for two-point boundary-value problems I: Proposals and justifications

Asymptotic expansions for the error in some spline interpolation schemes are used to derive asymptotic expansions for the truncation errors in some spline-collocation methods for two-point boundary-value problems. This raises the possibility of using Richardson extrapolation or iterated deferred corrections to develop efficient high-order algorithms based on low-order collocation in analogy with similar codes based on low-order finite difference methods; some specific such procedures are proposed.This research was supported in part by the United States Office of Naval Research under Contract N00014-67-A-0126-0015.