General explicit linear multistep ODE integrator \( \begin{align} v^{n+1} = \sum_{j=0}^{s-1} a_j v^{n-j} + \Delta t\left(\sum_{j=0}^{s-1}b_j \hat f\left(t^{n}-j\Delta t, v^{n-j}\right)\right) \end{align} \).
More...
template<class ContainerType>
struct dg::ExplicitMultistep< ContainerType >
General explicit linear multistep ODE integrator \( \begin{align} v^{n+1} = \sum_{j=0}^{s-1} a_j v^{n-j} + \Delta t\left(\sum_{j=0}^{s-1}b_j \hat f\left(t^{n}-j\Delta t, v^{n-j}\right)\right) \end{align} \).
which discretizes
\[ \frac{\partial v}{\partial t} = \hat f(t,v) \]
where \( f \) contains the equations. The coefficients for an order 3 "eBDF" scheme are given as an example:
\[ a_0 = \frac{18}{11}\ a_1 = -\frac{9}{11}\ a_2 = \frac{2}{11} \\ b_0 = \frac{18}{11}\ b_1 = -\frac{18}{11}\ b_2 = \frac{6}{11} \]
You can use your own coefficients defined as a dg::MultistepTableau or use one of the predefined coefficients in
We follow the naming convention as NAME-S-Q
- NAME is the author or name of the method
- S is the number of steps in the method
- Q is the global order of the method
| Name | Identifier | Description |
| AB-X-X | dg::AB_X_X | The family of schemes described in Linear multistep methods as Adams-Bashforth
\[ u^{n+1} = u^n + \Delta t\sum_{j=0}^{s-1} b_j f\left(t^n - j \Delta t, u^{n-j}\right) \]
- Note
- Possible stages are X: 1, 2,..., 5, the order of the method is the same as its stages
-
The Adams-Bashforth schemes implemented here need less storage but may have a smaller region of absolute stability than for example an extrapolated BDF method of the same order.
|
| eBDF-X-X | dg::eBDF_X_X | The family of schemes described in Hundsdorfer, W., Ruuth, S. J., & Spiteri, R. J. (2003). Monotonicity-preserving linear multistep methods. SIAM Journal on Numerical Analysis, 41(2), 605-623 as extrapolated BDF where it is found to be TVB (total variation bound). The schemes also appear as Minimal Projecting scheme described in Alfeld, P., Math. Comput. 33.148 1195-1212 (1979)
- Note
- Possible stages are X: 1 (C=1), 2 (C=0.63), 3 (C=0.39), 4 (C=0.22), 5 (C=0.09), 6 with the order the same as the number of stages
|
| TVB-X-X | dg::TVB_X_X | The family of schemes described in S.J. Ruuth and W. Hundsdorfer, High-order linear multistep methods with general monotonicity and boundedness properties, Journal of Computational Physics, Volume 209, Issue 1, 2005 as Total variation Bound. These schemes have larger allowable step sizes than the eBDF family,
- Note
- Possible values for X are 1 (C=1), 2 (C=0.5), 3 (C=0.54), 4 (C=0.46), 5 (C=0.38) 6 (C=0.33). We highlight that TVB-3-3 has 38% larger allowable stepsize than eBDF-3-3 and TVB-4-4 has 109% larger stepsize than eBDF-4-4 (to ensure the TVB property, not stability).
|
| SSP-X-Y | dg::SSP_X_Y | The family of schemes described in Gottlieb, S. On high order strong stability preserving runge-kutta and multi step time discretizations. J Sci Comput 25, 105–128 (2005) as Strong Stability preserving. We implement the lowest order schemes for each stage and disregard the remaining schemes in the paper since their CFL conditions are worse than the TVB scheme of the same order. - Note
- Possible values for X-Y : 1-1 (C=1), 2-2 (C=0.5), 3-2 (C=0.5), 4-2 (C=0.66), 5-3 (C=0.5), 6-3 (C=0.567).
-
These schemes are noteworthy because the coefficients b_i are all positive except for the 2-2 method and the "4-2" and "6-3" methods allow slightly larger allowable stepsize but increased storage requirements than TVB of same order (2 and 3).
|
- Note
- Total variation bound (TVB) means \( || v^n|| \leq M ||v^0||\) where the norm signifies the total variation semi-norm. Total variation diminishing (TVD) means M=1, and strong stability preserving (SSP) is the same as TVD, TVB schemes converge to the correct entropy solutions of hyperbolic conservation laws
-
the CFL coefficient C is given relative to the forward Euler method: \( \Delta t < C \Delta t_{FE}\).
- Attention
- The coefficient C is the one that ensures the TVD property of the scheme and is not directly related to the stability region of the scheme
- Note
- Uses only
blas1::axpby routines to integrate one step.
-
The difference between a multistep and a single step method like RungeKutta is that the multistep only takes one right-hand-side evaluation per step. This is advantageous if the right hand side is expensive to evaluate. Even though Runge Kutta methods can have a larger absolute timestep, if the effective timestep per rhs evaluation is compared, multistep methods generally win.
-
a disadvantage of multistep is that timestep adaption is not easily done.
- Template Parameters
-
| ContainerType | Any class for which a specialization of TensorTraits exists and which fulfills the requirements of the there defined data and execution policies derived from AnyVectorTag and AnyPolicyTag. Among others
dg::HVec (serial), dg::DVec (cuda / omp), dg::MHVec (mpi + serial) or dg::MDVec (mpi + cuda / omp) std::vector<dg::DVec> (vector of shared device vectors), std::array<double, 4> (array of 4 doubles) or std::map < std::string, dg::DVec> ( a map of named vectors) double (scalar) and other primitive types ...
If there are several ContainerTypes in the argument list, then TensorTraits must exist for all of them |
- See also
- See The dg dispatch system for a detailed explanation of our type dispatch system
1.9.3