Finite-order Padé scaling-and-squaring exponential

Input a finite complex matrix $A\in {\mathbb{C}}^{n\times n}$, $n\ge 1$, whose stored entries are representable in the operationwise model, a Padé order $m\ge 0$, an integer scaling count $s\ge 0$, finite nonnegative integer Householder-candidate and squaring-operation budgets, finite scalar-series budgets, and an error policy that is either candidate-only or certify. The procedure never selects adaptive Higham parameters. Certification data, including contour vertices and the radius, have exact dyadic or rational encodings.

1. Interpret the stored entries of $A$ as their exact real/imaginary values and form $B=2^{-s}A$ exactly. Evaluate $P=p_m(B)$ and $Q=q_m(B)$ by exact controller matrix arithmetic: increasing-index sums/products and finite polynomial powers with their rational coefficients. Use the exact real-RAM controller declared in Finite Householder QR solve for a Padé denominator with explicit statuses; the optional rational adapter is used only when all required actual encodings are supplied. No dyadic representation is assumed for the abstract floating model.
2. Call Finite Householder QR solve for a Padé denominator with explicit statuses on $QX=P$, explicitly passing the supplied finite Householder-candidate operation budget $K_H$. Continue only if the returned record contains a complete finite stored $n\times n$ matrix, with all entries marked complete, and status verified-solution or candidate-unverified. A partial candidate or any budget, range, representation or other failure is propagated with its original status and available partial record; do not square it. Retain a complete unverified candidate only in candidate-only mode; certification mode returns denominator-unverified. A complete matrix accompanying a failure status does not authorize continuation.
3. For $j=0,\dots ,s-1$, compute the next matrix square in the operationwise model. A range failure returns range-failure with the last candidate. Retain their exact stored real values and form $D_j={\widehat{X}}_{j+1}-{\widehat{X}}_j^2$ by the exact controller's finite matrix loops. Set ${\delta }_j={\max }_i{\sum }_k(\mathrm{\mid }\mathrm{Re}(D_j{)}_{ik}\mathrm{\mid }+\mathrm{\mid }\mathrm{Im}(D_j{)}_{ik}\mathrm{\mid })$; this exact nonnegative real number bounds $\mathrm{\parallel }{D}_j{\mathrm{\parallel }}_{\mathrm{\infty },\mathbb{C}}$.
4. In candidate-only mode, return the final candidate with status unevaluated-error-bound. Certification mode has these caller preconditions, which the procedure does not itself verify: (a) a supplied polygonal Cauchy cycle $\mathrm{\Gamma }$ with dyadic vertices, trace in a disk $\mathrm{\mid }z\mathrm{\mid }\le \rho$ for dyadic $\rho >0$, $\sigma (B)\subset \{\mathrm{\mid }z\mathrm{\mid }<\rho \}$, disjointness from $\sigma (B)$, index one on $\sigma (B)$, and null-homology in that disk; (b) $d_m(\rho )>0$; (c) a supplied finite dyadic resolvent-cover input for the singleton family $\{B\}$; and (d) a finite term budget $K$. The contour-validator call Finite complex contour resolvent validator with cover and inconclusive statuses must return certified-resolvent-cover with bound $M$, or the procedure returns inconclusive-resolvent. The validator checks resolvent inequalities and segment coverage only; it does not validate the caller's topological preconditions or count enclosed eigenvalues. Here $\sigma (B)$ denotes the eigenvalue set of $B$ from Eigenvalues, eigenvectors, eigenspaces $E_{\lambda }(T)=\ker (T-\lambda I)$, and the spectrum ${\sigma }_F(T)$ of an endomorphism.
5. For $x=\rho$ and for $\alpha ={\max }_i{\sum }_j(\mathrm{\mid }\mathrm{Re}{A}_{ij}\mathrm{\mid }+\mathrm{\mid }\mathrm{Im}{A}_{ij}\mathrm{\mid })$, compute an upper bound $U(x)$ for $e^x$ as follows. If $x=0$, set $U(x)=1$. Otherwise, if $x\ge K+2$, return inconclusive-scalar-tail. If $x<K+2$, put $r=x\mathrm{/}(K+2)$, $U(x)={\sum }_{k=0}^K{x}^k\mathrm{/}k!+[x^{K+1}\mathrm{/}(K+1)!]\mathrm{/}(1-r)$. The scalar-tail inequality used by the error theorem is proved separately there; this step defines the finite expression, rather than treating a Definition sentence as its proof.
6. Write the supplied finite polygonal chain as $\mathrm{\Gamma }={\sum }_{\nu }{m}_{\nu }{\gamma }_{\nu }$, with integer coefficients. Let $\mathrm{\ell }={\sum }_{\nu }\mathrm{\mid }{m}_{\nu }\mathrm{\mid }{\sum }_{e\text{ in }{\gamma }_{\nu }}(\mathrm{\mid }\mathrm{\Delta }\mathrm{Re}e\mathrm{\mid }+\mathrm{\mid }\mathrm{\Delta }\mathrm{Im}e\mathrm{\mid })$; then $\mathrm{\ell }$ is an exact rational upper bound for the coefficient-weighted contour length $L_{\mathrm{\Gamma }}={\sum }_{\nu }\mathrm{\mid }{m}_{\nu }\mathrm{\mid }L({\gamma }_{\nu })$ (the supplied vertices have rational/dyadic encodings). Put $ϵ={\rho }^{2m+1}U(\rho )(m!{)}^2\mathrm{/}((2m)!(2m+1)!d_m(\rho ))$. Since $\pi \mathrm{/}4={\int }_0^1(1+x^2{)}^{-1}dx$, the finite identity $1\mathrm{/}(1+x^2)={\sum }_{k=0}^7(-1{)}^k{x}^{2k}+x^{16}\mathrm{/}(1+x^2)$ on $[0,1]$ gives $\pi \mathrm{/}4>33976\mathrm{/}45045>3\mathrm{/}4$, hence $1\mathrm{/}(2\pi )<1\mathrm{/}6$. Set $E_0=\mathrm{\ell }ϵM\mathrm{/}6$.
7. For each squaring use $E_{j+1}=(2U(\alpha )+E_j)E_j+{\delta }_j$. If every computed certification check succeeded, the denominator solve returned verified-solution, and the caller preconditions hold, return the final candidate with status conditional-error-bound and bound $E_s$. Otherwise retain the candidate and return the corresponding inconclusive status.

The exact controller uses only prescribed finite field-expression trees and loops over dimensions, $m,s$ and the finite scalar-series term budget $K$; absolute values/maxima use exact comparisons. It performs no additional unprovided certification call. Count every rounded real primitive of a square in row-major/increasing inner-index order against an explicitly supplied finite squaring-operation budget, and propagate budget-exhausted before an unaffordable operation. The solve uses its separately supplied finite candidate-operation budget. Exact controller work is separate: its values need not be rational, and no bit-computability or total bit-cost bound for arbitrary real encodings is claimed. For the optional rational adapter with all values encoded, these same finite formulas use exact rational arithmetic. All loops are finite. The conditional-error-bound status is sound only under the caller preconditions in step 4 and does not mean that the procedure checked contour topology or eigenvalue count. No floating-point stability is asserted for the candidate alone.