Matrix exponential and phi function actions

Use the first-variable-linear standard inner product on ${\mathbb{C}}^n$ and its norm $\mathrm{\parallel }x{\mathrm{\parallel }}_2=\sqrt{{\sum }_{i<n}\mathrm{\mid }{x}_i{\mathrm{\mid }}^2}$ from The standard formulas $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$ and ${\sum }_{k<n}{x}_k\overline{y_k}$ on ${\mathbb{C}}^n$ are inner products and The norm $\parallel v\parallel =\sqrt{⟨v,v⟩}$ induced by a real or complex inner product. The matrix norm $\mathrm{\parallel }X{\mathrm{\parallel }}_2$ is the operator norm of the linear map $x\mapsto Xx$ in The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||. On ${\mathbb{C}}^0=\{0\}$ this operator norm is $0$, as specified in that definition.

For each integer $k\ge 0$, define the scalar phi function and its finite-matrix action by

${\phi }_k(z):={\sum }_{j=0}^{\mathrm{\infty }}\frac{z^j}{(j+k)!},{\phi }_k(X):={\sum }_{j=0}^{\mathrm{\infty }}\frac{X^j}{(j+k)!}\mathrm{.}$

Here $z\in \mathbb{C}$, $X\in M_n(\mathbb{C})$, $n\ge 0$, $X^0=I_n$, and factorials are the usual positive integer factorials. The scalar and matrix phi series converge absolutely ↗ establishes that both series converge absolutely for every such input, so these expressions define values on their full stated domains. By the published power-series definition The complex exponential by its power series, ${\phi }_0(z)=\exp z$; for matrices, ${\phi }_0(X)$ is the bounded-operator exponential series of The exponential series of a bounded operator.

At zero, the series gives ${\phi }_k(0)=1\mathrm{/}k!$ and ${\phi }_k(0_{n\times n})=I_n\mathrm{/}k!$ for every $n\ge 0$. For $n\ge 1$, only the $j=0$ matrix term can be nonzero. For $n=0$, The vector space $M_{m\times n}(F):=F^{m\times n}$ of $m$ by $n$ matrices over a field, with entrywise operations and Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes identify $I_0$ with the unique empty matrix $0_{0\times 0}$; every power $X^j$ and every partial sum is that matrix. Thus ${\phi }_k(0_{0\times 0})=I_0\mathrm{/}k!=0_{0\times 0}$, including $k=0$.

The recurrence is always interpreted as a series identity, including at zero; division by $z$ is not part of this definition.

Let $n\ge 1$ and $A\in M_n(\mathbb{C})$. In the standard complex inner product from The standard formulas $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$ and ${\sum }_{k<n}{x}_k\overline{y_k}$ on ${\mathbb{C}}^n$ are inner products, the adjoint matrix is the conjugate transpose $A^{\ast }$ by In orthonormal bases, the matrix of the adjoint is the conjugate transpose of the matrix. The Hermitian part is $H_A:=(A+A^{\ast })\mathrm{/}2$. It is self-adjoint in the sense of Self-adjoint and normal endomorphisms of a finite-dimensional real or complex inner product space.

Define the Euclidean logarithmic norm by ${\mu }_2(A):={\lambda }_{\max }(H_A)$, where ${\lambda }_{\max }$ denotes the largest eigenvalue of the Hermitian matrix $H_A$. The item The Euclidean logarithmic norm is a real Rayleigh-quotient maximum ↗ establishes that this eigenvalue exists, is real, and equals ${\max }_{\mathrm{\parallel }x{\mathrm{\parallel }}_2=1}\mathrm{Re}⟨Ax,x⟩$. This is a real growth bound, not a matrix norm.

Fix a finite complex matrix $M\in {\mathbb{C}}^{r\times s}$ with $r,s\ge 1$ and the Euclidean norms from The norm $\parallel v\parallel =\sqrt{⟨v,v⟩}$ induced by a real or complex inner product. A normwise certified vector arithmetic provider supplies the following outputs together with the stated bounds:

• For a real scalar $c$ and $z\in {\mathbb{C}}^s$, a scaled matvec output $\widehat{z}\in {\mathbb{C}}^r$ and an exactly represented nonnegative rational upper bound $\alpha$ satisfying $\mathrm{\parallel }\widehat{z}-cMz{\mathrm{\parallel }}_2\le \alpha$. This includes square matrix-vector products and the final Arnoldi basis projection.
• For a real scalar $c$ and vector $z\in {\mathbb{C}}^s$, a scaled-vector output $\widehat{q}\in {\mathbb{C}}^s$ and an exactly represented nonnegative rational upper bound $\xi$ satisfying $\mathrm{\parallel }\widehat{q}-cz{\mathrm{\parallel }}_2\le \xi$.
• For vectors $x,z\in {\mathbb{C}}^s$, a sum output $\widehat{s}\in {\mathbb{C}}^s$ and an exactly represented nonnegative rational upper bound $\zeta$ satisfying $\mathrm{\parallel }\widehat{s}-(x+z){\mathrm{\parallel }}_2\le \zeta$.

The bounds are part of the provider's mathematical contract and must enclose the exact norm errors for the supplied inputs. A call without a sound bound is uncertified and can only lead to an inconclusive status. This definition does not assert that a particular floating-point kernel supplies the contract.

Let $n\ge 1$, $A\in M_n(\mathbb{C})$, $T>0$, $v\in {\mathbb{C}}^n$, and $u:[-T,T]\to {\mathbb{C}}^n$ be continuously differentiable, with one-sided derivatives at the endpoints. Define the continuous defect $r(s):=Au(s)-u^{\mathrm{\prime }}(s)$. Then, for every $t\in [-T,T]$,

$e^{tA}v-u(t)=e^{tA}(v-u(0))+{\int }_0^t{e}^{(t-s)A}r(s)ds\mathrm{.}$

The vector integral is the oriented componentwise Riemann integral after identifying ${\mathbb{C}}^n$ with ${\mathbb{R}}^{2n}$. In particular, if $u(0)=v$, the initial term vanishes.

For every integer $k\ge 0$, the scalar series defining ${\phi }_k(z)$ converges absolutely for every $z\in \mathbb{C}$, and the matrix series defining ${\phi }_k(X)$ converges absolutely in operator $2$-norm for every $X\in M_n(\mathbb{C})$, $n\ge 0$. At zero, ${\phi }_k(0)=1\mathrm{/}k!$ and ${\phi }_k(0_{n\times n})=I_n\mathrm{/}k!$.

For $n\ge 1$ and $A\in M_n(\mathbb{C})$, $H_A=(A+A^{\ast })\mathrm{/}2$ is Hermitian, its eigenvalues are real, and

${\mu }_2(A)={\lambda }_{\max }(H_A)={\max }_{\mathrm{\parallel }x{\mathrm{\parallel }}_2=1}\mathrm{Re}⟨Ax,x⟩\mathrm{.}$

Inputs: $A\in M_n(\mathbb{C})$ with $n\ge 1$, a vector $v\in {\mathbb{C}}^n$, an exactly represented finite time $t\in \mathbb{R}$, positive rational tolerance $\epsilon$, integer budgets $s_{\max }\ge 1$ and $p_{\max }\ge 0$, rational upper bounds ${\rho }_A\ge \mathrm{\parallel }A{\mathrm{\parallel }}_2$, ${\rho }_t\ge \mathrm{\mid }t\mathrm{\mid }$, and ${\rho }_v\ge \mathrm{\parallel }v{\mathrm{\parallel }}_2$, and a provider satisfying Normwise certified matrix-vector and vector-step arithmetic.

For $s\ge 1$ define the rational $R_s:={\rho }_t{\rho }_A\mathrm{/}s$, which upper-bounds $\mathrm{\mid }t\mathrm{\mid }\mathrm{\parallel }A{\mathrm{\parallel }}_2\mathrm{/}s$. For rational $0\le R\le 1$ and integer $p\ge 0$, define

$Q_p(R):=\frac{R^{p+1}}{(p+1)!(1-R\mathrm{/}(p+2))}\mathrm{.}$

Outputs: a vector candidate when returned, an extended nonnegative rational error bound in ${\mathbb{Q}}_{\ge 0}\cup \{+\mathrm{\infty }\}$ ($+\mathrm{\infty }$ means no finite certificate was established), the number of calls to $A$, and one status: success, inconclusive-tail-budget, inconclusive-roundoff, or invalid-input.

Procedure:

1. Reject invalid dimensions, nonpositive tolerance, negative bounds, or invalid budgets by returning no candidate, bound $+\mathrm{\infty }$, zero calls to $A$, and invalid-input. If $v=0$, $t=0$, or ${\rho }_A=0$, return $v$, bound $0$, zero calls to $A$, and status success. In the last case $\mathrm{\parallel }A{\mathrm{\parallel }}_2=0$ forces $A=0$.
2. Among pairs $1\le s\le s_{\max }$ and $0\le p\le p_{\max }$ with $R_s\le 1$, select one minimizing $sp$ subject to $s{3}^{s-1}{Q}_p(R_s){\rho }_v\le \epsilon \mathrm{/}2$. Break ties by smaller $s$, then smaller $p$. If no pair exists, return the zero vector candidate, bound $+\mathrm{\infty }$, and inconclusive-tail-budget.
3. Set $\delta :=t\mathrm{/}s$ and $w_0:=v$. For each substep $\mathrm{\ell }=1,\dots ,s$, initialize $z_0:=w_{\mathrm{\ell }-1}$ and $a_0:=w_{\mathrm{\ell }-1}$. For $j=1,\dots ,p$, call the certified provider with coefficient $c=\delta \mathrm{/}j$ and vector $z_{j-1}$ to obtain $z_j$ and a bound ${\alpha }_{\mathrm{\ell }j}$ for $\mathrm{\parallel }{z}_j-(\delta \mathrm{/}j)A{z}_{j-1}{\mathrm{\parallel }}_2$. Add $z_j$ to the partial sum through the provider, obtaining $a_j$ and a bound ${\zeta }_{\mathrm{\ell }j}$ for $\mathrm{\parallel }{a}_j-(a_{j-1}+z_j){\mathrm{\parallel }}_2$. Set $d_{\mathrm{\ell }0}:=0$ and compute $d_{\mathrm{\ell }j}:=(R_s\mathrm{/}j)d_{\mathrm{\ell },j-1}+{\alpha }_{\mathrm{\ell }j}$. Set $w_{\mathrm{\ell }}:=a_p$ and ${ϵ}_{\mathrm{\ell }}:={\sum }_{j=1}^p(d_{\mathrm{\ell }j}+{\zeta }_{\mathrm{\ell }j})$; for $p=0$, set $w_{\mathrm{\ell }}:=w_{\mathrm{\ell }-1}$ and ${ϵ}_{\mathrm{\ell }}:=0$.
4. If any provider result lacks a sound bound, return the current candidate, bound $+\mathrm{\infty }$, and inconclusive-roundoff. Otherwise compute $B:=s{3}^{s-1}{Q}_p(R_s){\rho }_v+{\sum }_{\mathrm{\ell }=1}^s{3}^{s-\mathrm{\ell }}{ϵ}_{\mathrm{\ell }}$. Return $w_s$, bound $B$, and success if $B\le \epsilon$; otherwise return the same candidate and bound with inconclusive-roundoff.

The pair search is finite. The recurrence makes exactly $sp$ calls to $A$ when it reaches step 4; the error-bound provider performs no additional $A$ calls. An implementation may return an inconclusive status whenever an outward scalar comparison or a local error certificate cannot be established.

There are at most $s_{\max }(p_{\max }+1)$ pairs in the search, and for every admissible $R\in [0,1]$ and $p\ge 0$ the denominator $1-R\mathrm{/}(p+2)$ is at least $1\mathrm{/}2$, so each $Q_p(R)$ is defined. Every matrix-vector and partial-sum loop has a finite bound. The zero branches are exact: $v=0$ gives the zero action, $t=0$ gives $e^{0A}v=v$, and ${\rho }_A=0$ forces $A=0$. A failed local certificate stops with inconclusive-roundoff; failure to find a pair within the declared budgets returns inconclusive-tail-budget. Neither status asserts an error guarantee.

The separate error/work theorem on this page proves the reported bound under the stated rational input bounds and successful local provider certificates. Finite budgets need not return success; no convergence claim beyond this conditional finite certificate is made. The count $sp$ is the exact matrix-vector call count for a completed recurrence, not a claim about wall-clock cost.

For every integer $k\ge 0$, scalar $z\in \mathbb{C}$, and square matrix $X\in M_n(\mathbb{C})$ with $n\ge 0$, the series-defined functions of The phi-function family by everywhere-convergent series satisfy

${\phi }_k(z)=\frac{1}{k!}+z{\phi }_{k+1}(z),{\phi }_k(X)=\frac{1}{k!}{I}_n+X{\phi }_{k+1}(X)\mathrm{.}$

For $k\ge 1$ and $w\in {\mathbb{C}}^n$, let $J_k\in M_k(\mathbb{C})$ have ones on the superdiagonal and zeros elsewhere, and let $e_1,e_k\in {\mathbb{C}}^k$ be the first and last coordinate vectors. Define $B_k(X,w):=\left[\begin{array}{cc}X& w{e}_1^{\ast }\\ 0& J_k\end{array}\right]$. Then the first $n$ entries of $e^{B_k(X,w)}\left[\begin{array}{c}0\\ e_k\end{array}\right]$ equal ${\phi }_k(X)w$. The identity is valid at $X=0$ and requires no division by $X$ or by a scalar argument.

For $A\in M_n(\mathbb{C})$, $n\ge 1$, and $\tau \ge 0$,

$\mathrm{\parallel }{e}^{\tau A}{\mathrm{\parallel }}_2\le e^{\tau {\mu }_2(A)}\mathrm{.}$

Consequently, for $t\le 0$, $\mathrm{\parallel }{e}^{tA}{\mathrm{\parallel }}_2\le e^{\mathrm{\mid }t\mathrm{\mid }{\mu }_2(-A)}$. No normality, spectral stability, or sign assumption on ${\mu }_2(A)$ is required.

Let $A\in M_n(\mathbb{C})$, $n\ge 1$, $v\in {\mathbb{C}}^n$, $t\in \mathbb{R}$, and choose $s\ge 1$, $p\ge 0$, and rational $R\in [0,1]$ with $\mathrm{\mid }t\mathrm{\mid }\mathrm{\parallel }A{\mathrm{\parallel }}_2\mathrm{/}s\le R$. Put $\delta =t\mathrm{/}s$, $P:={\sum }_{j=0}^p(\delta A{)}^j\mathrm{/}j!$, and

$Q_p(R):=\frac{R^{p+1}}{(p+1)!(1-R\mathrm{/}(p+2))}\mathrm{.}$

Suppose each computed substep ${\widehat{w}}_{\mathrm{\ell }}$ has local term and summation certificates ${\alpha }_{\mathrm{\ell }j},{\zeta }_{\mathrm{\ell }j}\ge 0$ as in Finite scaled Taylor action for the matrix exponential, and define $d_{\mathrm{\ell }0}:=0$, $d_{\mathrm{\ell }j}:=(R\mathrm{/}j)d_{\mathrm{\ell },j-1}+{\alpha }_{\mathrm{\ell }j}$, and ${ϵ}_{\mathrm{\ell }}:={\sum }_{j=1}^p(d_{\mathrm{\ell }j}+{\zeta }_{\mathrm{\ell }j})$ (empty sums are zero). Then

$\mathrm{\parallel }{e}^{tA}v-{\widehat{w}}_s{\mathrm{\parallel }}_2\le s{3}^{s-1}{Q}_p(R)\mathrm{\parallel }v{\mathrm{\parallel }}_2+{\sum }_{\mathrm{\ell }=1}^s{3}^{s-\mathrm{\ell }}{ϵ}_{\mathrm{\ell }}\mathrm{.}$

If the algorithm has rational upper bound ${\rho }_v\ge \mathrm{\parallel }v{\mathrm{\parallel }}_2$ and returns success, its reported certificate is valid and at most the requested tolerance. A completed recurrence uses exactly $sp$ calls to $A$. A return before the recurrence makes zero such calls; an early stop during it makes at most $sp$ calls.

The certificate is for the specified finite matrix, time, budgets, norm bounds, and local arithmetic certificates. It asserts no mesh-uniform estimate from finite-dimensional exactness and returns an inconclusive status if any bound cannot be certified.

Inputs: $A\in M_n(\mathbb{C})$ with $n\ge 1$, $v\in {\mathbb{C}}^n$, time $t\in \mathbb{R}$, integer $k\ge 0$, Krylov budget $1\le m\le n$, nonnegative threshold $\tau$, an exact-arithmetic Arnoldi run or a finite-precision Arnoldi backend, and a reduced-action configuration. In finite precision, the backend returns a length $j$ with $1\le j\le m$, $\beta >0$ for $v\mathrm{\ne }0$, $V_j\in {\mathbb{C}}^{n\times j}$, $H_j\in M_j(\mathbb{C})$, and a computed subdiagonal; it may supply the relation certificate in Step 2 and an exact happy-breakdown certificate verifying the full Arnoldi recurrence from $v$ through $j$ steps with zero terminal residual. The reduced-action configuration supplies, for each Taylor call, an exactly represented call time, a rational upper bound on its absolute value, rational operator-norm and input-vector norm upper bounds, a positive rational tolerance, finite scaling/order budgets, and a provider satisfying Normwise certified matrix-vector and vector-step arithmetic for Taylor calls, scalar scaling, and final projection. Missing or invalid bounds produce an inconclusive status.

Outputs: a vector candidate when data are available, reduced-coefficient error bound ${ϵ}_{\mathrm{r}\mathrm{e}\mathrm{d}}\in {\mathbb{R}}_{\ge 0}\cup \{+\mathrm{\infty }\}$, final-projection error bound ${\eta }_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}\in {\mathbb{Q}}_{\ge 0}\cup \{+\mathrm{\infty }\}$, Arnoldi data, any relation-error certificates, arnoldi_status (zero-start, happy-breakdown, projected, numerical-breakdown, inconclusive-arnoldi, or invalid-input), relation_status (exact, certified, inconclusive, or not-run), reduced_action_status (success, inconclusive, or not-run), and projection_status (exact, certified, inconclusive, or not-run). An invalid input may return no candidate.