SSPな時間積分法

# 初めに
[既に見た](https://qiita.com/ShotaDeguchi/items/639657f65ee136d17add)ように，陽的な$\text{RK}(s, p)$の中で，$p \le 4$のものに対しては，$s = p$が達成できる．一方，$s \ge p$と刻むこともできて，このとき，絶対安定領域を押し広げることができる．

特に，議論の的をmulti-stage methodに絞り，multi-step methodには触れない．さらに，高々$p \le 4$のものに限る．[Izzo&Jackiewicz2022](https://doi.org/10.1007/s41980-022-00731-x)がcomprehensiveで良い．

# MAIN
## 名前
[Gottlieb+2001](https://doi.org/10.1137/S003614450036757X)によると，先駆的なものは[Shu1988](https://doi.org/10.1137/0909073), [Shu&Osher1988](https://doi.org/10.1016/0021-9991(88)90177-5)であり，当時はTVD（Total-Variation-Diminishing）な時間離散化スキームと呼ばれていたようである．現代ではSSPな時間離散化法とかいう呼び方が浸透しているようである．所謂，TVD条件のことをStrong Stability条件と呼ぶこともあるらしい（例えば，[Durran2010](https://doi.org/10.1007/978-1-4419-6412-0)）．

## 安定性
線形な問題
```math
\begin{align}
    \frac{\partial}{\partial t} u \left( t \right)
    = A \left( u \right)
    = M u
\end{align}
```
に対する解の増幅率は，
```math
\begin{align}
    G
    = \exp \left( \tau M \right)
    = \sum_{k=0}^{\infty} \frac{(\tau M)^k}{k!}
\end{align}
```
であり，解が安定である（i.e., 発散しない）ためには，$| G | \le 1$．一方，$\text{RK}(s, p)$の中で，$s=p=K$なるもの（即ち，$K \le 4$）の増幅率は，
```math
\begin{align}
    G_{\text{RK}(s,p)}
    = \sum_{k=0}^{K} \frac{(\tau M)^k}{k!}
\end{align}
```
である．$z = \tau M$とすると，$\text{RK}(s,p)$が安定であるためには，
```math
\begin{align}
    z \in \mathbb{S}_{\text{RK}(s,p)}
    = \lbrace
        z \in \mathbb{C}
        \mid
        \lvert G_{\text{RK($s, p$)}} \left( z \right) \rvert \le 1
    \rbrace
\end{align}
```
| $p=2$ | $p=3$ | $p=4$ |
|:-:|:-:|:-:|
| ![stability_RK.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2529612/80c5ba7e-1bc7-5a52-dea6-b49489a131d3.png) | ![stability_RK.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2529612/bd89a5f5-f158-f797-2d04-92be5f846ccb.png) | ![stability_RK.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2529612/9b4c5a6c-37c2-4389-d971-d1bd5670de76.png) |

一方，非線形な問題（や硬い問題も？）
```math
\begin{align}
    \frac{\partial}{\partial t} u \left( t \right)
    = B \left( u \right)
\end{align}
```
に対しては，安定性領域を押し広げておきたい場合がある．即ち，適当な$\text{SSP-RK}(s, p)$があって，その増幅率$G_{\text{SSP-RK}(s,p)}$と安定性領域$\mathbb{S}_{\text{SSP-RK}(s,p)}$が適当に定義できて，
```math
\begin{align}
    | \mathbb{S}_{\text{SSP-RK}(s,p)} |
    \gt
    | \mathbb{S}_{\text{RK}(p,p)} |
    \quad \text{for some fixed } p
\end{align}
```
を狙う．このとき，往々にして$s \ge p$．$s = p$でこれを達成する$\text{SSP-RK}$が存在するのか気になるが，未だ知らない．

## 具体的な方法
[Durran2010](https://doi.org/10.1007/978-1-4419-6412-0)や[Gottlieb+2018](https://arxiv.org/abs/1708.02595)より．[Izzo&Jackiewicz2022](https://doi.org/10.1007/s41980-022-00731-x)も詳しい．Izzo&Jackiewicz2022に示されているButcher tableauに則る．

### 2次の方法
**SSP-RK(2, 2)**
[Shu&Osher1988](https://doi.org/10.1016/0021-9991(88)90177-5)．
```math
\begin{align}
    f_1
    &= B \left( u^{n} \right)
    \\
    f_2
    &= B \left( u^{n} + \tau f_1 \right)
    \\
    u^{n+1}
    &= u^{n}
    + \tau \left( \frac{1}{2} f_1 + \frac{1}{2} f_2 \right)
\end{align}
```
ざっと計算したところ，素朴な$\text{RK}(2, 2)$と同じだけの安定性領域だろうと思う．

**SSP-RK(3, 2)**
```math
\begin{align}
    f_1
    &= B \left( u^{n} \right)
    \\
    f_2
    &= B \left( u^{n} + \tau \frac{1}{2} f_1 \right)
    \\
    f_3
    &= B \left( u^{n} + \tau \left( \frac{1}{2} f_1 + \frac{1}{2} f_2 \right) \right)
    \\
    u^{n+1}
    &= u^{n}
    + \tau \left( \frac{1}{3} f_1 + \frac{1}{3} f_2 + \frac{1}{3} f_3 \right)
\end{align}
```
ざっと計算したところ，$\text{RK}(2, 2)$より$z^3 / 12$だけ大きい．

### 3次の方法
**SSP-RK(3, 3)**
[Shu&Osher1988](https://doi.org/10.1016/0021-9991(88)90177-5)．
```math
\begin{align}
    f_1
    &= B \left( u^{n} \right)
    \\
    f_2
    &= B \left( u^{n} + \tau f_1 \right)
    \\
    f_3
    &= B \left( u^{n} + \tau \left( \frac{1}{4} f_1 + \frac{1}{4} f_2 \right) \right)
    \\
    u^{n+1}
    &= u^{n}
    + \tau \left( \frac{1}{6} f_1 + \frac{1}{6} f_2 + \frac{2}{3} f_3 \right)
\end{align}
```

**SSP-RK(4, 3)**
[Spiteri&Ruuth2002](https://doi.org/10.1137/S0036142901389025)．
```math
\begin{align}
    f_1
    &= B \left( u^{n} \right)
    \\
    f_2
    &= B \left( u^{n} + \tau \frac{1}{2} f_1 \right)
    \\
    f_3
    &= B \left( u^{n} + \tau \left( \frac{1}{2} f_1 + \frac{1}{2} f_2 \right) \right)
    \\
    f_4
    &= B \left( u^{n} + \tau \left( \frac{1}{6} f_1 + \frac{1}{6} f_2 + \frac{1}{6} f_3 \right) \right)
    \\
    u^{n+1}
    &= u^{n}
    + \tau \left( \frac{1}{6} f_1 + \frac{1}{6} f_2 + \frac{1}{6} f_3 + \frac{1}{2} f_4 \right)
\end{align}
```
$\text{RK}(3, 3)$より$z^4 / 48$だけ大きい．

### 4次の方法
**SSP-RK(4, 4)**
存在しない（[Gottlieb&Shu1998](http://dx.doi.org/10.1090/S0025-5718-98-00913-2), [Ruuth&Spiteri2002](https://doi.org/10.1023/A:1015156832269)）．

**SSP-RK(5, 4)**
[Spiteri&Ruuth2002](https://doi.org/10.1137/S0036142901389025)．しかし，写し間違いが怖いのでやめておく．

**SSP-RK(10, 4)**
[Ketcheson2008](https://doi.org/10.1137/07070485X)．[Gottlieb+2018](https://arxiv.org/abs/1708.02595)が具体的に書き下している．[Izzo&Jackiewicz2022](https://doi.org/10.1007/s41980-022-00731-x)がButcher tableauを与えている．面倒なのでここには記さないが，計算すると，
```math
\begin{align}
    G_{\text{SSP-RK}(10,4)}
    &= \frac{1}{25} \left( 1 + 18 y + 6 y^2 \right)
    \\
    y
    &= \left( 1 + \frac{z}{6} \right)^5
\end{align}
```
であった．

## 絶対安定領域
| $p=2$ | $p=3$ | $p=4$ | $p=4$ |
|:-:|:-:|:-:|:-:|
| ![stability_SSP_RK.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2529612/a391bb94-23fc-c241-10da-e6fb5645a1c7.png) | ![stability_SSP_RK.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2529612/1dd4ca04-c4d2-a199-c1dd-283b57829fe5.png) | ![stability_SSP_RK.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2529612/5ba0d821-6613-178c-8892-c342810ab87e.png) | ![stability_SSP_RK.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2529612/60aaaafe-38af-4b02-695c-e3c324ea4067.png) |

$s \ge p$で段階的に拡大する．[Izzo&Jackiewicz2022](https://doi.org/10.1007/s41980-022-00731-x)がcomprehensiveである．

# 終わりに
精度を高めることはできなくても，大胆な歩幅を取って歩くことができるのは魅力的である．非線形な問題では（硬さなども効いてきて？）小さい刻み幅を要求される場合も予想できる．実際，[Kubatko+2014](https://doi.org/10.1007/s10915-013-9796-7), [Yeager+2021](https://doi.org/10.1007/s10915-021-01635-4)など．

なお，載せたものはほんの一部であり，沢山ある．

拾い上げ切れていない事項: [Gottlieb+2001](https://doi.org/10.1137/S003614450036757X)などを読めば分かるが，明らかに移流の解析のために用意された方法である．この文脈で，Courant数$C$が登場する．幾つかの$\text{SSP-RK}$は$C \le 1$を要求するが，幾つかは$C \le 2$まで許容する（これより大きいものもあるかもしれない）．安定性領域の拡大から直感的には認められるが，驚くべき事実である．また，SSP constantとかいう言葉も見かけた．今のところ，この2つの数字は同じものを指していると思っているが，少し自信が無い．周辺は整理し直す必要がある．