GitHub

OrdinaryDiffEqExtrapolation

Explicit extrapolation methods that achieve high accuracy through Richardson extrapolation of basic integration schemes. These methods provide adaptive order capabilities and natural parallelism, though they are generally outclassed by modern Runge-Kutta methods for most non-stiff problems.

Key Properties

Extrapolation methods provide:

  • Adaptive order capability allowing arbitrarily high orders
  • Natural parallelism across different substep sequences
  • High accuracy potential for very smooth problems
  • Richardson extrapolation to eliminate lower-order error terms
  • Automatic stepsize and order control
  • Theoretical appeal but often practical limitations

When to Use Extrapolation Methods

These methods are recommended for:

  • Very smooth problems where high-order accuracy is beneficial
  • Extremely low tolerance requirements where adaptive order helps
  • Parallel computing environments that can exploit the natural parallelism
  • Research applications exploring adaptive order techniques
  • Problems where other high-order methods struggle with accuracy

Important Limitations

  • Generally outclassed by modern explicit RK methods (Tsit5, Verner methods)
  • Higher computational overhead compared to optimized RK methods
  • Best suited for very smooth functions - poor performance on non-smooth problems
  • Parallel efficiency gains often don't compensate for increased work

Mathematical Background

Extrapolation methods use sequences of basic integrators (like Euler or midpoint) with different stepsizes, then apply Richardson extrapolation to achieve higher-order accuracy. The adaptive order capability comes from using longer extrapolation sequences.

Solver Selection Guide

Explicit extrapolation methods

  • AitkenNeville: Euler extrapolation using Aitken-Neville algorithm
  • ExtrapolationMidpointDeuflhard: Midpoint extrapolation with barycentric coordinates
  • ExtrapolationMidpointHairerWanner: Midpoint extrapolation following ODEX algorithm

When to consider these methods

  • Very low tolerances (< 1e-12) where adaptive order might help
  • Extremely smooth problems with analytic solutions
  • Parallel computing scenarios with many available cores
  • Comparison studies with other high-order methods

Better alternatives for most problems

  • For high accuracy: Use Verner methods (Vern7, Vern8, Vern9)
  • For general problems: Use Tsit5 or appropriate RK method
  • For stiff problems: Consider implicit extrapolation methods

Performance Notes

  • Consider stiff extrapolation methods which can perform very well for sufficiently stiff problems
  • Test against Verner methods before choosing extrapolation for high accuracy
  • Parallelism benefits are problem and hardware dependent
  • Most effective on very smooth, well-behaved problems

Installation

To be able to access the solvers in OrdinaryDiffEqExtrapolation, you must first install them use the Julia package manager:

using Pkg
Pkg.add("OrdinaryDiffEqExtrapolation")

This will only install the solvers listed at the bottom of this page. If you want to explore other solvers for your problem, you will need to install some of the other libraries listed in the navigation bar on the left.

Example usage

using OrdinaryDiffEqExtrapolation

function lorenz!(du, u, p, t)
    du[1] = 10.0 * (u[2] - u[1])
    du[2] = u[1] * (28.0 - u[3]) - u[2]
    du[3] = u[1] * u[2] - (8 / 3) * u[3]
end
u0 = [1.0; 0.0; 0.0]
tspan = (0.0, 100.0)
prob = ODEProblem(lorenz!, u0, tspan)
sol = solve(prob, ExtrapolationMidpointDeuflhard())

Full list of solvers

OrdinaryDiffEqExtrapolation.AitkenNeville — Type
AitkenNeville(;
        max_order = 10, min_order = 1, init_order = 5,
        threading = false
    ) -> AitkenNeville

Adaptive explicit Euler extrapolation using the Aitken-Neville scheme and a Romberg subdivision sequence. The method varies both its step size and extrapolation order and is intended for smooth, non-stiff problems at tight tolerances.

Keywords

  • max_order::Integer = 10: largest extrapolation order the controller may select.
  • min_order::Integer = 1: smallest extrapolation order the controller may select.
  • init_order::Integer = 5: extrapolation order used for the first step. Choose values satisfying 1 <= min_order <= init_order <= max_order.
  • threading = false: enable concurrent internal extrapolation work when true; use false for serial execution.

Returns

  • AitkenNeville: configured adaptive extrapolation algorithm for CommonSolve.solve.

Examples

using OrdinaryDiffEqExtrapolation: AitkenNeville
using CommonSolve: solve
using SciMLBase: ODEProblem

prob = ODEProblem((u, p, t) -> -u, 1.0, (0.0, 1.0))
sol = solve(prob, AitkenNeville(max_order = 8); abstol = 1.0e-10, reltol = 1.0e-8)

References

C. Elrod et al., "Parallelizing explicit and implicit extrapolation methods for ordinary differential equations," HPEC 2022, pp. 1-9.

source
OrdinaryDiffEqExtrapolation.ExtrapolationMidpointDeuflhard — Type
ExtrapolationMidpointDeuflhard(;
        min_order = 1, init_order = 5,
        max_order = 10, sequence = :harmonic, threading = true,
        sequence_factor = 2
    ) -> ExtrapolationMidpointDeuflhard

Adaptive explicit midpoint extrapolation with Deuflhard's order and step-size selection. Barycentric extrapolation combines the midpoint approximations. The independent extrapolation columns can run concurrently.

Keywords

  • min_order::Integer = 1: smallest internal extrapolation order; values below 1 are raised to 1.
  • init_order::Integer = 5: initial internal order. It is raised to at least min_order.
  • max_order::Integer = 10: largest internal order. It is raised to at least init_order.
  • sequence::Symbol = :harmonic: subdivision sequence. Supported values are :harmonic, :romberg, and :bulirsch; other values warn and use :harmonic.
  • threading = true: enable concurrent extrapolation columns when true.
  • sequence_factor::Integer = 2: even multiplier applied to the subdivision sequence. Odd values warn and are replaced by 2.

Returns

  • ExtrapolationMidpointDeuflhard: configured explicit extrapolation algorithm for CommonSolve.solve.

Examples

using OrdinaryDiffEqExtrapolation: ExtrapolationMidpointDeuflhard
using CommonSolve: solve
using SciMLBase: ODEProblem

prob = ODEProblem((u, p, t) -> -u, 1.0, (0.0, 1.0))
alg = ExtrapolationMidpointDeuflhard(sequence = :romberg, threading = false)
sol = solve(prob, alg; abstol = 1.0e-10, reltol = 1.0e-8)

References

C. Elrod et al., "Parallelizing explicit and implicit extrapolation methods for ordinary differential equations," HPEC 2022, pp. 1-9.

source
OrdinaryDiffEqExtrapolation.ExtrapolationMidpointHairerWanner — Type
ExtrapolationMidpointHairerWanner(;
        min_order = 2, init_order = 5,
        max_order = 10, sequence = :harmonic, threading = true,
        sequence_factor = 2
    ) -> ExtrapolationMidpointHairerWanner

Adaptive explicit midpoint extrapolation with the order and step-size controller from Hairer and Wanner's ODEX algorithm. Barycentric extrapolation combines the midpoint approximations, whose independent columns can run concurrently.

Keywords

  • min_order::Integer = 2: smallest internal extrapolation order; values below 2 are raised to 2.
  • init_order::Integer = 5: initial internal order. It is raised when necessary so that min_order < init_order.
  • max_order::Integer = 10: largest internal order. It is raised when necessary so that init_order < max_order.
  • sequence::Symbol = :harmonic: subdivision sequence. Supported values are :harmonic, :romberg, and :bulirsch; other values warn and use :harmonic.
  • threading = true: enable concurrent extrapolation columns when true.
  • sequence_factor::Integer = 2: even multiplier applied to the subdivision sequence. Odd values warn and are replaced by 2.

Returns

  • ExtrapolationMidpointHairerWanner: configured explicit extrapolation algorithm for CommonSolve.solve.

Examples

using OrdinaryDiffEqExtrapolation: ExtrapolationMidpointHairerWanner
using CommonSolve: solve
using SciMLBase: ODEProblem

prob = ODEProblem((u, p, t) -> -u, 1.0, (0.0, 1.0))
alg = ExtrapolationMidpointHairerWanner(threading = false)
sol = solve(prob, alg; abstol = 1.0e-10, reltol = 1.0e-8)

References

C. Elrod et al., "Parallelizing explicit and implicit extrapolation methods for ordinary differential equations," HPEC 2022, pp. 1-9.

source