Non-satisfiability of a positivity condition for commutator-free exponential integrators of order higher than four

Abstract

We consider commutator-free exponential integrators as put forward in Alverman and Fehske (J Comput Phys 230:5930–5956, 2011). For parabolic problems, it is important for the well-definedness that such an integrator satisfies a positivity condition such that essentially it only proceeds forward in time. We prove that this requirement implies maximal convergence order of four for real coefficients, which has been conjectured earlier by other authors.

Appendices

Proof of the order conditions (7)–(10)

For the global error to have order $p=5$ it is required that the local error have convergence order $p+1=6$. If, without restriction of generality, we consider only the first integration step for the special problem (5), this condition for the local error is written as

$$\begin{aligned} \mathrm {e}^{\tau b_J A_0+\tau ^2 y_J A_1}\cdots \mathrm {e}^{\tau b_1 A_0+\tau ^2 y_1 A_1}u_0 = u(\tau ) +O(\tau ^6). \end{aligned}$$

(18)

A Taylor expansion of the left-hand side leads to (let ${\mathbf {k}}=(k_1,\ldots ,k_m), \ |{\mathbf {k}}| =\sum _{l=1}^m k_l$)

$$\begin{aligned}&\mathrm {e}^{\tau b_J A_0+\tau ^2 y_J A_1}\cdots \mathrm {e}^{\tau b_1 A_0+\tau ^2 y_1 A_1}u_0 = c^{(J)}_\emptyset u_0\\&\quad +\, \sum _{\begin{array}{c} {\mathbf {k}}=(k_1,\ldots k_m)\\ m\ge {1}, k_l\in \{0,1\}, {|{\mathbf {k}}|+m}\le 5 \end{array}} \tau ^{{|{\mathbf {k}}|+m}} c^{(J)}_{k_1\dots k_m}A_{k_1}\cdots A_{k_m}u_0 + O(\tau ^6). \end{aligned}$$

Here for $J=1$ we have [note that already a subset of coefficients suffices to derive the order conditions (7)–(10)],

$$\begin{aligned}&c^{(1)}_\emptyset =1,\quad c^{(1)}_{0}=b_1,\quad c^{(1)}_{1}=y_1,\quad c^{(1)}_{01}=\frac{1}{2}b_1y_1,\quad c^{(1)}_{11}=\frac{1}{2}y_1^2,\\&c^{(1)}_{001}=\frac{1}{6}b_1^2y_1,\quad c^{(1)}_{011}=\frac{1}{6}b_1y_1^2, \quad c^{(1)}_{0001}=\frac{1}{24}b_1^3y_1, \end{aligned}$$

and for $J\ge 2$ the coefficients can be computed recursively,

$$\begin{aligned}&c^{(J)}_\emptyset =c^{(J-1)}_\emptyset ,\quad c^{(J)}_{0}=c^{(J-1)}_{0}+ b_Jc^{(J-1)}_\emptyset ,\quad c^{(J)}_{1}=c^{(J-1)}_{1}+ y_Jc^{(J-1)}_\emptyset ,\\&c^{(J)}_{01}=c^{(J-1)}_{01}+b_Jc^{(J-1)}_{1} +\frac{1}{2}b_Jy_Jc^{(J-1)}_\emptyset ,\\&c^{(J)}_{11}=c^{(J-1)}_{11}+y_Jc^{(J-1)}_{1} +\frac{1}{2}y_J^2c^{(J-1)}_\emptyset ,\\&c^{(J)}_{001}=c^{(J-1)}_{001}+b_Jc^{(J-1)}_{01} +\frac{1}{2}b_J^2c^{(J-1)}_{1}+\frac{1}{6}b_J^2y_Jc^{(J-1)}_\emptyset ,\\&c^{(J)}_{011}=c^{(J-1)}_{011}+b_Jc^{(J-1)}_{11} +\frac{1}{2}b_Jy_Jc^{(J-1)}_{1}+\frac{1}{6}b_Jy_J^2c^{(J-1)}_\emptyset ,\\&c^{(J)}_{0001}=c^{(J-1)}_{0001}+b_Jc^{(J-1)}_{001} +\frac{1}{2}b_J^2c^{(J-1)}_{01}+\frac{1}{6}b_J^3c^{(J-1)}_{1} +\frac{1}{24}b_J^3y_Jc^{(J-1)}_\emptyset . \end{aligned}$$

An inductive argument involving straightforward but laborious calculations gives

$$\begin{aligned}&c^{(J)}_\emptyset =1,\quad c^{(J)}_{0}= \sum _{j=1}^Jb_j,\quad c^{(J)}_{1} = \sum _{j=1}^Jy_j, \nonumber \\&c^{(J)}_{01} = c^{(J)}_{0}c^{(J)}_{1}-\sum _{j=1}^J{\widehat{b}}_jy_j, \quad c^{(J)}_{11} = \frac{1}{2}(c^{(J)}_{1})^2,\nonumber \\&c^{(J)}_{001}=c^{(J)}_{0}c^{(J)}_{01}-\frac{1}{2}(c^{(J)}_{0})^2c^{(J)}_{1} -\frac{1}{2}\sum _{j=1}^J\left( {\widehat{b}}_{j}^2+\frac{1}{12}b_{j}^2\right) y_{j}, \nonumber \\&c^{(J)}_{011} =\frac{1}{2}\sum _{j=1}^{J}\left( {\widehat{y}}_{j}^2+\frac{1}{12}y_{j}^2\right) b_{j},\nonumber \\&c^{(J)}_{0001} = c^{(J)}_{0}c^{(J)}_{001}- \frac{1}{2}(c^{(J)}_{0})^2c^{(J)}_{01} +\frac{1}{6}(c^{(J)}_{0})^3c^{(J)}_{1}-\frac{1}{6}\sum _{j=1}^{J}\left( {\widehat{b}}_{j}^3+\frac{1}{4}{\widehat{b}}_{j}b_{j}^2\right) y_{j}.\qquad \quad \end{aligned}$$

(19)

Repeated differentiation of the differential equation (5) yields

$$\begin{aligned}&u(0)=u_0, \quad u'(0) = A_0u_0, \quad u''(0) = (A_1+A_0^2)u_0,\\&u'''(0) = (A_0A_1+2A_1A_0+A_0^3)u_0,\\&u^{(4)}(0) = (3A_1^2+A_0^2A_1+2A_0A_1A_0+A_1A_0^2+A_0^4)u_0,\\&u^{(5)}(0) = (3A_0A_1^2+4A_1A_0A_1+8A_1^2A_0+A_0^3A_1\\&\qquad \qquad \quad +\,2A_0^2A_1A_0+3A_0A_1A_0^2 +4A_1A_0^3+A_0^5)u_0. \end{aligned}$$

Thus for the Taylor expansion of the right-hand side of (18) we obtain

$$\begin{aligned} u(\tau )= & {} \sum _{q=0}^5\frac{\tau ^q}{q!}u^{(q)}(0) + O(\tau ^6) = s_{\emptyset }u_0\\&+\sum _{\begin{array}{c} {{\mathbf {k}}=}(k_1,\ldots k_m)\\ m\ge {1}, k_l\in \{0,1\}, {|{\mathbf {k}}|+m} \le 5 \end{array}} \tau ^{{|{\mathbf {k}}|+m}} {s}_{k_1\dots k_m}A_{k_1}\cdots A_{k_m}u_0 + O(\tau ^6) \end{aligned}$$

with coefficients [only those corresponding to the subset of coefficients as in (19)]

$$\begin{aligned}&s_{\emptyset }=\frac{1}{0!}=1,\quad s_0=\frac{1}{1!}=1,\quad s_1=\frac{1}{2!}=\frac{1}{2}, \quad s_{01}=\frac{1}{3!}=\frac{1}{6},\quad s_{11}=\frac{3}{4!}=\frac{1}{8},\nonumber \\&s_{001}=\frac{1}{4!}=\frac{1}{24},\quad s_{011}=\frac{3}{5!}=\frac{1}{40}, \quad s_{0001}=\frac{1}{5!}=\frac{1}{120}. \end{aligned}$$

(20)

Equating corresponding coefficients in (19) and (20) leads to the order conditions (7)–(10).

A geometric lemma

Lemma 1

Let $\{a_1,\ldots ,a_m\}$ be a linearly independent set of vectors in ${\mathbb {R}}^n$ and $S\in {\mathbb {R}}^{n\times n}$ symmetric positive definite. Further let $c=(\gamma _1,\ldots ,\gamma _m)^T\in {\mathbb {R}}^m$ and $\delta \in {\mathbb {R}}$. Then the intersection ${\mathcal {I}}$ of the m hyperplanes in ${\mathbb {R}}^n$ given by the equations $a_1^Tx=\gamma _1,\ldots ,a_m^Tx=\gamma _m$ intersects the hyper-ellipsoid ${\mathcal {Q}}$ given by the equation $x^TSx=\delta$ if and only if it holds

$$\begin{aligned} c^T\varGamma ^{-1}c \le \delta , \end{aligned}$$

(21)

where $\varGamma = (a_i^TS^{-1}a_j)_{i,j=1}^m$ denotes the Gram matrix of the vectors $a_1,\ldots ,a_m$ with respect to the scalar product $x^TS^{-1}y$.

Proof

First we consider the special case $S=I_n$ (identity matrix), where ${\mathcal {Q}}$ is a hyper-sphere. In this case ${\mathcal {I}}$ intersects ${\mathcal {Q}}$ if and only if the point $x_*\in {\mathcal {I}}$ of minimal norm satisfies

$$\begin{aligned} \Vert x_*\Vert ^2=x_*^Tx_* \le \delta . \end{aligned}$$

(22)

It is easy to see that this point $x_*$ lies in the linear subspace of ${\mathbb {R}}^n$ spanned by $a_1, \ldots a_m$ (the normal vectors to the given hyperplanes), i.e., there exists $b=(\beta _1,\ldots ,\beta _m)^T\in {\mathbb {R}}^m$ such that

$$\begin{aligned} x_* = \beta _1a_1+\dots +\beta _ma_m = Ab, \end{aligned}$$

where $A=[a_1\ \cdots \ a_m]\in {\mathbb {R}}^{n\times m}$. Because $x_*\in {\mathcal {I}}$ it holds

$$\begin{aligned} \varGamma b = A^TAb = A^Tx_*=c, \end{aligned}$$

and thus

$$\begin{aligned} x_*^Tx_* = b^TA^TAb = b^T\varGamma b = c^T\varGamma ^{-1}c, \end{aligned}$$

which shows that (22) is equivalent to (21). This completes the proof for the special case $S=I_n$.

For the general case, the symmetric positive definite matrix S can be written as

$$\begin{aligned} S=X\varLambda X^T \end{aligned}$$

with $\varLambda =\mathrm {diag}(\lambda _1,\ldots ,\lambda _n)$, where $\lambda _j>0$ are the eigenvalues of S, and X orthogonal. We define ${\widetilde{a}}_j=\varLambda ^{-1/2}X^Ta_j$, $j=1,\ldots ,m$. Then under the transformation of variables $\widetilde{x}=\varLambda ^{1/2}X^Tx$, the equation ${\widetilde{a}}_j^T{\widetilde{x}}=\gamma _j$ is equivalent to $a_j^Tx=\gamma _j$ and ${\widetilde{x}}^T{\widetilde{x}}=\delta$ is equivalent to $x^TSx=\delta$. For these transformed equations the special case from above is applicable. Using ${\widetilde{A}} = [{\widetilde{a}}_1\ \cdots \ {\widetilde{a}}_m] = \varLambda ^{-1/2}X^TA$ with $A=[a_1\ \cdots \ a_m]$ it follows that for the transformed equations the corresponding Gram matrix satisfies ${\widetilde{\varGamma }}={\widetilde{A}}^T{\widetilde{A}}=A^TX\varLambda ^{-1}X^TA=A^TS^{-1}A = \varGamma$ as claimed. $\square$

Maple code for checking (16)=(17)

Here, the Maple identifiers s, s1, bb, dd, eSe, eSd, dSd correspond to $\sigma$, ${\widetilde{\sigma }}$, $b_{J+1}$, $d_{J+1}$, $e^TS^{-1}e$, $e^TS^{-1}d$, $d^TS^{-1}d$, respectively.