# Multistep Multistage (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

s\k2345
2 -- -- -- 2s5k6pT2.mat
3 -- 3s3k6pT2.mat 3s4k6pT2.mat 3s5k6pT2.mat
4 -- 4s3k6pT2.mat 4s4k6pT2.mat 4s5k6pT2.mat
5 -- 5s3k6pT2.mat 5s4k6pT2.mat 5s5k6pT2.mat
6 6s2k6pT2.mat 6s3k6pT2.mat 6s4k6pT2.mat 6s5k6pT2.mat
7 7s2k6pT2.mat 7s3k6pT2.mat 7s4k6pT2.mat 7s5k6pT2.mat
8 8s2k6pT2.mat 8s3k6pT2.mat 8s4k6pT2.mat 8s5k6pT2.mat
9 9s2k6pT2.mat 9s3k6pT2.mat 9s4k6pT2.mat 9s5k6pT2.mat
10 10s2k6pT2.mat 10s3k6pT2.mat 10s4k6pT2.mat 10s5k6pT2.mat
$$\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

s\k2345
3 -- -- -- 3s5k7pT2.mat
4 -- 4s3k7pT2.mat 4s4k7pT2.mat 4s5k7pT2.mat
5 -- 5s3k7pT2.mat 5s4k7pT2.mat 5s5k7pT2.mat
6 -- 6s3k7pT2.mat 6s4k7pT2.mat 6s5k7pT2.mat
7 -- 7s3k7pT2.mat 7s4k7pT3.mat 7s5k7pT2.mat
8 8s2k7pT2.mat 8s3k7pT2.mat 8s4k7pT2.mat 8s5k7pT2.mat
9 9s2k7pT2.mat 9s3k7pT2.mat 9s4k7pT2.mat 9s5k7pT2.mat
10 10s2k7pT2.mat 10s3k7pT2.mat 10s4k7pT2.mat 10s5k7pT2.mat
$$\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

s\k2345
5 -- -- 5s4k8p.mat 5s5k8p.mat
6 -- -- 6s4k8p.mat 6s5k8p.mat
7 -- -- 7s4k8p.mat 7s5k8p.mat
8 -- 8s3k8p.mat 8s4k8p.mat 8s5k8p.mat
9 -- 9s3k8p.mat 9s4k8p.mat 9s5k8p.mat
10 -- 10s3k8p.mat 10s4k8p.mat 10s5k8p.mat
$$\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

s\k345
8 -- 8s4k8p.mat --
9 -- 9s4k8p.mat 9s5k8p.mat
10 10s3k9p.mat -- --
$$\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

s\k36
8 -- 8s6k10p.mat
20 20s3k10p.mat --
$$\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