Formulation

An explicit linear multistep method

\[\begin{align*} \label{lmm} u_n = \sum_{j=0}^{k-1} \alpha_j u_{n-k+j} + \Delta t \beta_j F(u_{n-k+j})\end{align*}\]

is said to have SSP coefficient \(r>0\) if

\[\begin{align*} \label{sspc} \beta_j & \ge 0 & \alpha_j - r \beta_j & \ge 0 & \mbox{ for } 0\le j \le k-1.\end{align*}\]

The method is accurate to order \(p\) if

\[\begin{align*} \label{oc} \sum_{j=0}^{k-1} \left(j^m \alpha_j + mj^{m-1}\beta_j\right) & = k^m & \mbox{ for } 0\le m\le p.\end{align*}\]

A fundamental open question is whether SSP methods exist with arbitrarily high order. That is, given any positive integer \(p\), do there exist \(r>0,k>0\) and coefficients \(\alpha,\beta\) such that and are satisfied?

This can be written as a standard linear programming feasibility problem by introducing \(\delta_j = \alpha_j-r\beta_j\). Then the order conditions read

\[\begin{align*} \sum_{j=0}^{k-1} \left(j^m \delta_j + j^{m-1}(m+rj)\beta_j\right) & = k^m & \mbox{ for } 0\le m\le p.\end{align*}\]

This system of equations can be written as

\[\begin{align*} \left(\begin{array}{c|c|c|c|c|c|c|c} & & & & & & & \\\\ v_0 & v_1 & \cdots & v_{k-1} & w_0 & w_1 & \cdots & w_{k-1} \\\\ & & & & & & & \\\\ \end{array}\right) x & = v_k \end{align*}\]

where \(x=(\delta_0,\dots,\delta_{k-1},\beta_0,\dots,\beta_{k-1})^T\) and

\[\begin{align*} v_j & = \begin{pmatrix} 1 \\ j \\ j^2 \\ \vdots \\ j^p \end{pmatrix} & w_j & = \begin{pmatrix} r \\ 1 + rj \\ 2j + rj^2 \\ \vdots \\ pj^{p-1} + rj^p \end{pmatrix}\end{align*}\]

The problem then amounts to proving that for some \(r>0\) and sufficiently large \(k\), the vector \(v_k\) can be written as a positive linear combination of the vectors \(v_j\) and \(w_j\) for \(0\le j \le k-1\).

The Dual Problem

Farkas’ lemma says that proving feasibility of the problem above is equivalent to proving infeasibility of its dual, which is obtained by considering the transpose of the matrix above:

\[\begin{align*} v_j^T y & \ge 0 & 0 \le j \le k-1 \\ w_j^T y & \ge 0 & 0 \le j \le k-1 \\ v_k^T y & < 0.\end{align*}\]

Writing these conditions out completely:

\[\begin{align*} \sum_{m=0}^p j^m y_m & \ge 0 & 0 \le j \le k-1 \\\\ \sum_{m=0}^p j^{m-1}(m+rj) y_m & \ge 0 & 0 \le j \le k-1 \\ \sum_{m=0}^p k^m y_m & < 0.\end{align*}\]

Alternative formulation

A different (but equivalent) linear system is obtained if one uses Taylor series about \(n\Delta t\) rather than \((n-k)\Delta t\) to derive the order conditions. They then read

The method is accurate to order \(p\) if

\[\begin{align*} \sum_{j=0}^{k-1} \alpha_j & = 1 \\ \sum_{j=0}^{k-1} \left((j-k)^m \alpha_j + m(j-k)^{m-1}\beta_j\right) & = 0 & \mbox{ for } 1\le m\le p.\end{align*}\]

Introducing again \(\delta_j = \alpha_j-r\beta_j\), the order conditions read

\[\begin{align*} \sum_{j=0}^{k-1} \delta_j + r\beta_j & = 1 \\ \sum_{j=0}^{k-1} \left((j-k)^m \delta_j + (j-k)^{m-1}(m+r(j-k))\beta_j\right) & = 0 & \mbox{ for } 1\le m\le p.\end{align*}\]

Dual of the alternative formulation

\[\begin{align*} \sum_{m=0}^p (j-k)^m y_m & \ge 0 & 0 \le j \le k-1 \\ \sum_{m=0}^p (j-k)^{m-1}(m+r(j-k)) y_m & \ge 0 & 0 \le j \le k-1 \\ y_0 < 0.\end{align*}\]