Multistep Multistage (MSRK) Methods
This page contains information about MSRK methods.
Overview
Consider methods of the form:
$$
\begin{align}
y_1^n & = u^n \\
y_i^n & = \sum_{l=1}^{k} d_{il} u^{n-k+l} + \Delta{t}\sum_{l=1}^{k-1} \hat{a}_{il} F(u^{n-k+l}) + \Delta{t}\sum_{j=1}^{i-1} a_{ij} F(y_j^n) \; \; \; \; 2 \leq i \leq s \\
u^{n+1} & = \sum_{l=1}^{k} \theta_l u^{n-k+l} + \Delta{t}\sum_{l=1}^{k-1} \hat{b}_{l} F(u^{n-k+l}) + \Delta{t}\sum_{j=1}^s b_j F(y_j^n).
\end{align}
$$
where $u^{n-k+l}$ are the previous step values and $y_i^n$ are the intermediate stage
values of the approximation.
Optimal methods were found.
Effective SSP Coefficients
s = number of stages
k = number of steps
Data Format
Each of these coefficient files contains the following variables:
- A
- Matrix containing the values of $a_{ij}$
- Ahat
- Matrix containing the values of $\hat{a}_{ij}$
- B
- $b_j$
- Bhat
- $\hat{b}_l$
- D
- $d_{il}$
- theta
- $\theta_{l}$
In addition, these files retain information from the numerical optimization
procedure that determined the above values.
Order Conditions
The following table contains the conditions for the first, second, third, and fourth order methods.
| $$\boldsymbol{p}$$ |
Conditions |
| 1 |
$$\begin{align*}
b^T e = 1 + \theta^T l.
\end{align*}$$
|
| 2 |
$$\begin{align*}
b^T c = \frac{1 + \theta^T l^2}{2}.
\end{align*}$$
|
| 3 |
$$\begin{align*}
b^T c^2 & = \frac{1 + \theta^T l^3}{3}, &
b^T \boldsymbol{\tau}_2 & = 0.
\end{align*}$$
|
| 4 |
$$\begin{align*}
b^T c^3 & = \frac{1 + \theta^T l^4}{4}, &
b^T C \boldsymbol{\tau}_2 & = 0, \\
b^T A \boldsymbol{\tau}_2 & = 0, &
b^T \boldsymbol{\tau}_3 & = 0.
\end{align*}$$ |
Where:
$$\begin{align}
l & = (k-1, k-2, \dots, 1, 0)^T \\
(k!) \boldsymbol{\tau}_k & = c^k - D (-l)^k - k A c^{k-1} \\
c & = Ae - Dl
\end{align}$$
Note: Vector exponentiation is interpreted as element-wise exponentiation.
For orders of $p$ up to 11, the following script contains the necessary conditions: oc_ksrk.m
Second Order
The coefficients of the optimal second order methods have a clear structure.
These methods all have a matrix D with the first $(k-1)$ columns all zeros, and
the final column is all ones and the matrixes $\hat{A}$ and $\hat{B}$ are all
zeros. The $A$ matrix is an $s \times s $ matrix with zeros on the diagonal and
above (as these are explicit methods) and the value $ \alpha (s,k,\beta) =
\frac{(k-1)(1-\beta s)+1}{\beta s(s-1)} $ filling all the locations below the
diagonal. The matrix $B$ is a column vector of length $s$ with the values
\[\beta= \frac{kQ}{s(k-1)\left(2(s-1)+Q \right)} \] where $Q =
(k-2)s+\sqrt{(k-2)^2s^2+4s(s-1)(k-1)}$ at each element. Finally, the vector
$\theta$ is of length $k$ and has the value $ \theta (s,k,\beta) = \frac{k -
\beta s}{k-1} $ as its last element, the value $1-\theta (s,k,\beta)$ for the
first element, and zero everywhere else.
$$
\begin{array}{|c|c|c|c|c|} \hline
s \backslash k &2&3&4&5\\ \hline
2 & {\bf 0.70711} & {\bf 0.80902} & {\bf 0.86038} & {\bf 0.89039}\\ \hline
3 & {\bf 0.81650} & {\bf 0.87915} & {\bf 0.91068} & {\bf 0.92934}\\ \hline
4 & {\bf 0.86603} & {\bf 0.91144} & {\bf 0.93426} & {\bf 0.94782}\\ \hline
5 & {\bf 0.89443} & {\bf 0.93007} & {\bf 0.94797} & {\bf 0.95863}\\ \hline
6 & {\bf 0.91287} & {\bf 0.94222} & {\bf 0.95694} & {\bf 0.96573}\\ \hline
7 & {\bf 0.92582} & {\bf 0.95076} & {\bf 0.96327} & {\bf 0.97074}\\ \hline
8 & {\bf 0.93541} & {\bf 0.95711} & {\bf 0.96798} & {\bf 0.97448}\\ \hline
\end{array}
$$
SSP Coefficients for second order methods.
Third Order
$$
\begin{array}{|l|l|l|l|l|} \hline
s\backslash k &2&3&4&5\\\hline
2 & {\bf 0.36603} & {\bf 0.55643} & {\bf 0.57475} & 0.57475\\ \hline
3 & {\bf 0.55019} & {\bf 0.57834} & {\bf 0.57834} & 0.57834\\ \hline
4 & {\bf 0.57567} & {\bf 0.57567} & {\bf 0.57567} & 0.57567\\ \hline
5&0.59758&0.59758&0.59758&0.59758\\ \hline
6&0.62946&0.62946&0.62946&0.62946\\ \hline
7&0.64051&0.64051&0.64051&0.64051\\ \hline
8&0.65284&0.65284&0.65284&0.65284\\ \hline
9&0.67220&0.67220&0.67220&0.67220\\ \hline
10&0.68274&0.68274&0.68274&0.68274\\ \hline
\end{array}
$$
SSP Coefficients for third order methods
Fourth Order
$$\begin{array}{|l|l|l|l|l|} \hline
s\backslash k &2&3&4&5\\\hline
2 & {\bf -- } & {\bf 0.24767} & {\bf 0.34085} & 0.39640\\\hline
3 & {\bf 0.28628} & {\bf 0.38794} & {\bf 0.45515} & 0.48741\\ \hline
4 & {\bf 0.39816} & {\bf 0.46087} & {\bf 0.48318} & 0.49478\\ \hline
5&0.47209&0.50419&0.50905&0.51221\\ \hline
6&0.50932&0.51214&0.51425&0.51550\\ \hline
7&0.53436&0.53552&0.53610&0.53646\\ \hline
8&0.56151&0.56250&0.56317&0.56362\\ \hline
9&0.58561&0.58690&0.58871&0.58927\\ \hline
10&0.61039&0.61415&0.61486&0.61532\\ \hline
\end{array}
$$
SSP Coefficients for fourth order methods
Fifth Order
$$
\begin{array}{|l|l|l|l|l|} \hline
s\backslash k &2&3&4&5\\\hline
2&--&--&0.18556&0.26143\\\hline
3&--&0.21267&0.33364&0.38735\\\hline
4&0.21354&0.34158&0.38436&0.39067\\\hline
5&0.32962&0.38524&0.40054&0.40461\\\hline
6&0.38489&0.40386&0.40456&0.40456\\\hline
7&0.41826&0.42619&0.42619&0.42619\\\hline
8&0.44743&0.44743&0.44743&0.44743\\\hline
9&0.43794&0.43806&0.43806&0.43806\\\hline
10&0.42544&0.43056&0.43098&0.43098\\\hline
\end{array}
$$
SSP Coefficients for fifth order methods
Sixth Order
$$
\begin{array}{|l|l|l|l|l|}
\hline
s\backslash k &2&3&4&5\\\hline
2&--&--&--&0.10451\\\hline
3&--&0.00971&0.11192&0.21889\\\hline
4&--&0.17924&0.27118&0.31639\\\hline
5&--&0.27216&0.32746&0.34142\\\hline
6&0.09928&0.32302&0.33623&0.34453\\\hline
7&0.18171&0.34129&0.34899&0.35226\\\hline
8&0.24230&0.33951&0.34470&0.34680\\\hline
9&0.28696&0.34937&0.34977&0.35033\\\hline
10&0.31992&0.35422&0.35643&0.35665\\\hline
\end{array}
$$
SSP Coefficients for sixth order methods
Seventh Order
$$
\begin{array}{|l|l|l|l|l|}
\hline
s\backslash k &2&3&4&5\\\hline
2&--&--&--&--\\\hline
3&--&--&--&0.12735\\\hline
4&--&--&0.04584&0.22049\\\hline
5&--&0.06611&0.23887&0.28137\\\hline
6&--&0.15811&0.28980&0.30063\\\hline
7&--&0.24269&0.28562&0.29235\\\hline
8&--&0.26988&0.28517&0.28715\\\hline
9&0.12444&0.29046&0.29616&0.29759\\\hline
10&0.17857&0.29522&0.30876&0.30886\\\hline
\end{array}
$$
SSP Coefficients for seventh order methods
Eighth Order
$$
\begin{array}{|l|l|l|l|l|}
\hline
s\backslash k &2&3&4&5\\\hline
2&--&--&--&--\\\hline
3&--&--&--&--\\\hline
4&--&--&--&--\\\hline
5&--&--&0.04781&0.10007\\\hline
6&--&--&0.07991&0.22574\\\hline
7&--&--&0.14818&0.22229\\\hline
8&--&0.09992&0.16323&0.19538\\\hline
9&--&0.14948&0.21012&0.23826\\\hline
10&--&0.20012&0.21517&0.24719\\\hline
\end{array}
$$
SSP Coefficients for eighth order methods
Ninth Order
$$
\begin{array}{|l|l|l|l|l|}
\hline
s\backslash k &3&4&5\\\hline
8&--&0.1276&--\\\hline
9&--&0.1766&0.1883\\\hline
10&0.0802&--&--\\\hline
\end{array}
$$
SSP Coefficients for ninth order methods
Tenth Order
$$
\begin{array}{|l|l|l|l|l|}
\hline
s\backslash k &3&6\\\hline
8&--&0.0839 \\\hline
20&0.0917&--\\\hline
\end{array}
$$
SSP Coefficients for tenth order methods
Paper Scripts
Paper scripts may be found here. MSRK methods
are supported in the SSP_Tools package and may be tested.
Optimization Scripts
The most up to date versions of the optimization scripts may be obtained at David Ketcheson's
github repository.
The following deprecated MATLAB scripts were used to generate the methods in the MSRK paper.
- nlc_tsrk.m
- Nonlinear constraints
- oc_ksrk.m
- Order conditions
- opt_tsrk.m
- Main optimization routine
- packing.m
- Packing the coefficients into one long vector for optimization
- tsrk_am_obj.m
- Defining the function to be optimized
- unpackexplicitT2.m
- Unpacking the long optimization vector into the different method coefficients