Multistep schemes

The multistep classes compute the solution at the new step from the solutions at $N_s$ previous steps. They extend integrator_multistep_object (the multistep Runge-Kutta SSP class extends integrator_multistage_multistep_object) and store the previous steps in their members previous(1:steps), with times t(1:steps) and time steps Dt(1:steps). The first $N_s$ steps must be provided by the caller (start-up), then integrate(U, Dt, t) shifts them by itself if autoupdate is .true. (the default); t is the time of the last stored step. See the quick start for a complete start-up loop.

Below, $U^{n+s}$ denotes the solution at the step $n+s$ and $R^{n+s}=R(t^{n+s},U^{n+s})$. The value of $\mathrm{\Delta }t$ is always provided by the caller; all the schemes but the variable step size LMM-SSP require a constant $\mathrm{\Delta }t$.

Adams-Bashforth

Class adams_bashforth (integrator_adams_bashforth), explicit, schemes adams_bashforth_1 ... adams_bashforth_16, of order $N_s$ equal to the number of steps [7, 12]:

$$U^{n+N_s}=U^{n+N_s-1}+\mathrm{\Delta }t\sum _{s=1}^{N_s}{b}_s{R}^{n+s-1}$$

adams_bashforth_1 is the forward Euler scheme. The first coefficients are:

Scheme	$b_1$	$b_2$	$b_3$	$b_4$
adams_bashforth_1	$1$
adams_bashforth_2	$-\frac{1}{2}$	$\frac{3}{2}$
adams_bashforth_3	$\frac{5}{12}$	$-\frac{16}{12}$	$\frac{23}{12}$
adams_bashforth_4	$-\frac{9}{24}$	$\frac{37}{24}$	$-\frac{59}{24}$	$\frac{55}{24}$

Adams-Moulton

Class adams_moulton (integrator_adams_moulton), implicit, schemes adams_moulton_0 ... adams_moulton_15, of order $N_s+1$ [7, 12]:

$$U^{n+N_s}=U^{n+N_s-1}+\mathrm{\Delta }t[\sum _{s=0}^{N_s-1}{b}_s{R}^{n+s}+b_{N_s}R(t^{n+N_s},U^{n+N_s})]$$

The implicit equation is solved by fixed point iterations, their number given by the iterations argument (default 1): each iteration evaluates the residual at the last iterate of $U^{n+N_s}$, starting from the value of U passed to integrate. adams_moulton_0 is the implicit backward Euler scheme, 1st order, $U^{n+1}=U^n+\mathrm{\Delta }tR(t^{n+1},U^{n+1})$, with $U^n$ stored in the single register of the previous steps; at least one fixed point iteration is always performed.

Scheme	$b_0$	$b_1$	$b_2$	$b_3$
adams_moulton_0	$1$
adams_moulton_1	$\frac{1}{2}$	$\frac{1}{2}$
adams_moulton_2	$-\frac{1}{12}$	$\frac{8}{12}$	$\frac{5}{12}$
adams_moulton_3	$\frac{1}{24}$	$-\frac{5}{24}$	$\frac{19}{24}$	$\frac{9}{24}$

Fixed point iterations converge only if $\mathrm{\Delta }t$ is small with respect to the Lipschitz constant of $R$: on stiff problems they impose a step restriction comparable to the one of an explicit scheme.

Adams-Bashforth-Moulton

Class adams_bashforth_moulton (integrator_adams_bashforth_moulton), predictor-corrector, schemes adams_bashforth_moulton_1 ... adams_bashforth_moulton_16. The scheme of number $N$ predicts with the Adams-Bashforth scheme of $N$ steps and corrects with the Adams-Moulton scheme of $N-1$ steps, both of order $N$:

$$\begin{array}{rl}{U}^{n+N,p}& =U^{n+N-1}+\mathrm{\Delta }t\sum _{s=1}^N{b}_s^p{R}^{n+s-1}\\ U^{n+N}& =U^{n+N-1}+\mathrm{\Delta }t[\sum _{s=0}^{N-2}{b}_s^c{R}^{n+s+1}+b_{N-1}^{c}R(t^{n+N},U^{n+N,p})]\end{array}$$

adams_bashforth_moulton_1 is AB(1)-AM(0), forward Euler predictor and backward Euler corrector, 1st order. The iterations argument (default 1) sets the corrector iterations.

Backward Differentiation Formula

Class back_df (integrator_back_df), implicit, schemes back_df_1 ... back_df_6, of order $N_s$:

$$U^{n+N_s}+\sum _{s=1}^{N_s}{\alpha }_s{U}^{n+N_s-s}=\mathrm{\Delta }t\beta R(t^{n+N_s},U^{n+N_s})$$

solved by fixed point iterations (iterations, default 1). back_df_1 is the backward Euler scheme.

Steps	$\beta$	${\alpha }_1$	${\alpha }_2$	${\alpha }_3$	${\alpha }_4$	${\alpha }_5$	${\alpha }_6$
1	$1$	$-1$
2	$\frac{2}{3}$	$-\frac{4}{3}$	$\frac{1}{3}$
3	$\frac{6}{11}$	$-\frac{18}{11}$	$\frac{9}{11}$	$-\frac{2}{11}$
4	$\frac{12}{25}$	$-\frac{48}{25}$	$\frac{36}{25}$	$-\frac{16}{25}$	$\frac{3}{25}$
5	$\frac{60}{137}$	$-\frac{300}{137}$	$\frac{300}{137}$	$-\frac{200}{137}$	$\frac{75}{137}$	$-\frac{12}{137}$
6	$\frac{60}{147}$	$-\frac{360}{147}$	$\frac{450}{147}$	$-\frac{400}{147}$	$\frac{225}{147}$	$-\frac{72}{147}$	$\frac{10}{147}$

The BDF schemes are designed for stiff problems, but their stability advantage requires a Newton-like solver of the implicit equation: with fixed point iterations the step is limited as for the Adams-Moulton schemes.

Leapfrog

Class leapfrog (integrator_leapfrog), explicit, 2 steps [4]:

$$U^{n+2}=U^n+2\mathrm{\Delta }t{R}^{n+1}$$

The scheme leapfrog is 2nd order accurate, but it is unstable on dissipative problems (its spurious computational mode is amplified): use it for oscillatory, non dissipative problems.

The scheme leapfrog_raw applies the Robert-Asselin-Williams (RAW) filter [5, 6, 20, 21] after each step:

$$\begin{array}{rl}\mathrm{\Delta }& =\frac{\nu }{2}(U^n-2U^{n+1}+U^{n+2})\\ U^{n+1}& \leftarrow U^{n+1}+\alpha \mathrm{\Delta }\\ U^{n+2}& \leftarrow U^{n+2}+(\alpha -1)\mathrm{\Delta }\end{array}$$

with $\nu \in (0,1]$ and $\alpha \in (0.5,1]$, defaults $\nu =0.01$ and $\alpha =0.53$, set by the nu and alpha arguments. For $\alpha =1$ the filter reverts to the classic Robert-Asselin filter.

Order of accuracy

With a fixed filter coefficient $\nu$, leapfrog_raw is formally 1st order accurate, as the tests suite measures. The "3rd order accuracy" of Williams (2011) refers to the accuracy of the amplitude of the oscillations, not to the order of the global error.

Linear multistep SSP

Class lmm_ssp (integrator_lmm_ssp), explicit, Strong Stability Preserving [16]:

$$U^{n+N_s}=\sum _{s=1}^{N_s}[a_s{U}^{n+s-1}+\mathrm{\Delta }t{b}_s{R}^{n+s-1}]$$

Scheme	Order	Non-zero coefficients
lmm_ssp_steps_3_order_2	2	$a_1=\frac{1}{4}$, $a_3=\frac{3}{4}$, $b_3=\frac{3}{2}$
lmm_ssp_steps_4_order_3	3	$a_1=\frac{11}{27}$, $a_4=\frac{16}{27}$, $b_1=\frac{12}{27}$, $b_4=\frac{16}{9}$
lmm_ssp_steps_5_order_3	3	$a_1=\frac{7}{32}$, $a_5=\frac{25}{32}$, $b_1=\frac{5}{16}$, $b_5=\frac{25}{16}$

Linear multistep SSP with variable step size

Class lmm_ssp_vss (integrator_lmm_ssp_vss), explicit, SSP, the time step can change from step to step [17]. With

$${\omega }_i=\frac{\mathrm{\Delta }{t}^{n+i}}{\mathrm{\Delta }{t}^{n+N_s}},{\mathrm{\Omega }}_s=\sum _{i=1}^s{\omega }_i,1\le s\le N_s$$

the 2nd order formula is

$$U^{n+N_s}=\frac{1}{{\mathrm{\Omega }}_{N_s-1}^2}{U}^n+\frac{{\mathrm{\Omega }}_{N_s-1}^2-1}{{\mathrm{\Omega }}_{N_s-1}^2}{U}^{n+N_s-1}+\frac{{\mathrm{\Omega }}_{N_s-1}+1}{{\mathrm{\Omega }}_{N_s-1}}\mathrm{\Delta }{t}^{n+N_s}R\left(U^{n+N_s-1}\right)$$

and the 3rd order one is

$$\begin{array}{rl}{U}^{n+N_s}=& \frac{3{\mathrm{\Omega }}_{N_s-1}+2}{{\mathrm{\Omega }}_{N_s-1}^3}{U}^n+\frac{({\mathrm{\Omega }}_{N_s-1}+1{)}^2({\mathrm{\Omega }}_{N_s-1}-2)}{{\mathrm{\Omega }}_{N_s-1}^3}{U}^{n+N_s-1}\\ & +\frac{{\mathrm{\Omega }}_{N_s-1}+1}{{\mathrm{\Omega }}_{N_s-1}^2}\mathrm{\Delta }{t}^{n+N_s}R(U^n)+\frac{({\mathrm{\Omega }}_{N_s-1}+1{)}^2}{{\mathrm{\Omega }}_{N_s-1}^2}\mathrm{\Delta }{t}^{n+N_s}R\left(U^{n+N_s-1}\right)\end{array}$$

Scheme	Order
lmm_ssp_vss_steps_2_order_2	2
lmm_ssp_vss_steps_3_order_2	2
lmm_ssp_vss_steps_3_order_3	3
lmm_ssp_vss_steps_4_order_3	3
lmm_ssp_vss_steps_5_order_3	3

Multistep Runge-Kutta SSP

Class ms_runge_kutta_ssp (integrator_ms_runge_kutta_ssp), explicit, multistep-multistage, SSP [18]. With $k$ steps and $s$ stages:

$$\begin{array}{rl}{y}_1^n& =u^n\\ y_i^n& =\sum _{l=1}^k{d}_{il}{u}^{n-k+l}+\mathrm{\Delta }t\sum _{l=1}^{k-1}{\hat{a}}_{il}R(u^{n-k+l})+\mathrm{\Delta }t\sum _{j=1}^{i-1}{a}_{ij}R(y_j^n),2\le i\le s\\ u^{n+1}& =\sum _{l=1}^k{\theta }_l{u}^{n-k+l}+\mathrm{\Delta }t\sum _{l=1}^{k-1}{\hat{b}}_{l}R(u^{n-k+l})+\mathrm{\Delta }t\sum _{j=1}^s{b}_{j}R(y_j^n)\end{array}$$

Scheme	Steps	Stages	Order
ms_runge_kutta_ssp_steps_2_stages_2_order_3	2	2	3
ms_runge_kutta_ssp_steps_3_stages_2_order_3	3	2	3
ms_runge_kutta_ssp_steps_4_stages_5_order_8	4	5	8

The coefficients are in the source, foodie_integrator_ms_runge_kutta_ssp.F90. The 8th order of the last scheme is verified by the polynomial exactness test and observed on the Riccati problem, but it is beyond the orders the convergence test can assert in double precision (see Testing).

The references are numbered as in the bibliography of the catalogue.