Finite scaled Taylor action for the matrix exponential

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.