Shift-invert and harmonic Ritz extraction with solve and pencil status

Let $A\in {\mathbb{C}}^{n\times n}$, $n\ge 1$, choose a shift $\sigma \in \mathbb{C}$, and put $M=A-\sigma I$. This procedure returns candidate values and their residual data; it asserts no convergence or forward-error bound. Its branch statuses are available, arnoldi-breakdown, linear-solve-unavailable, zero-transformed-Ritz-value, infinite-harmonic-value, projected-pencil-unresolved, qz-budget-exhausted, and qz-certificate-inconclusive.

Shift-invert branch. This branch requires $M$ to be invertible, equivalently that $\sigma$ is not an eigenvalue of $A$ by For a finite-dimensional space, $\lambda$ is an eigenvalue of $T$ if and only if $T-\lambda I$ is not invertible. Its inputs also include a nonzero starting vector $v$, an integer Arnoldi dimension $1\le m\le n$, a residual tolerance $\tau \ge 0$, and a solve routine. Normalize $v_1=v\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2$. For $j=1,\dots ,m$, request either the exact solution $y_j=M^{-1}{v}_j$ or a computed vector $y_j$ together with its actual equation residual $s_j=M{y}_j-v_j$. If a requested solve is unavailable, return linear-solve-unavailable with the residuals already recorded. Set $w=y_j$. For $i=1,\dots ,j$, compute $h_{ij}=⟨w,v_i⟩$ and replace $w\leftarrow w-h_{ij}{v}_i$. Repeat this pass once, adding each second-pass coefficient to the corresponding $h_{ij}$. Set $h_{j+1,j}=\mathrm{\parallel }w{\mathrm{\parallel }}_2$. If this norm is zero, set the current dimension to $k=j$ and stop with status arnoldi-breakdown; otherwise set $v_{j+1}=w\mathrm{/}{h}_{j+1,j}$. After $m$ columns, set $k=m$ and stop with status available. When every solve is exact, this is Arnoldi applied to $M^{-1}$. When any solve is inexact, the projected matrix is only the one produced from the computed vectors; the procedure makes no exact-Arnoldi or convergence claim for that branch.

Compute the Ritz pairs $(\theta ,z)$ of the current $k\times k$ matrix $H$ as in Ritz values and Ritz vectors extracted from the Arnoldi Hessenberg reduction, normalize $z$ to unit norm, and lift $u=V_{k}z$. For each $\theta \mathrm{\ne }0$, report the transformed candidate $\lambda =\sigma +1\mathrm{/}\theta$, the lifted vector $u$, and the directly computed original residual $r_A=Au-\lambda u$. Mark this candidate accepted exactly when $\mathrm{\parallel }{r}_A{\mathrm{\parallel }}_2\le \tau$. If $\theta =0$, assign no finite inverse map and mark that candidate zero-transformed-Ritz-value. To record the solve-error transfer for a candidate with $\theta \mathrm{\ne }0$, request one additional solve $My=u$; if it is available, store $s_0=My-u$ and $r_T=y-\theta u$ alongside the directly computed residual $r_A$. If this additional solve is unavailable, return linear-solve-unavailable with the candidate and accumulated ledger.

Harmonic Ritz branch. This branch takes a full-column-rank trial basis $U\in {\mathbb{C}}^{n\times k}$, $k\ge 1$; it does not require $M$ to be invertible. Form $W=MU$ and $G=W^{\ast }W=U^{\ast }{M}^{\ast }MU,C=W^{\ast }U=U^{\ast }{M}^{\ast }U\mathrm{.}$ Compute an exact column-pivoted QR of $W$ as in Full, reduced, and column-pivoted computational QR factorisations and let $r_W$ be its exact rank. If $r_W<k$, choose $z\mathrm{\ne }0$ with $Wz=0$. Then $z^{\ast }G=(Wz{)}^{\ast }W=0$ and $z^{\ast }C=(Wz{)}^{\ast }U=0$. Thus the nonzero row $z^{\ast }$ annihilates $G-\eta C$ for every $\eta$; if this matrix were invertible, right multiplication by its inverse would force $z^{\ast }=0$, a contradiction. Hence $G-\eta C$ is singular for every $\eta$; return projected-pencil-unresolved. If $W$ has full column rank, then $z^{\ast }Gz=\mathrm{\parallel }Wz{\mathrm{\parallel }}_2^2>0$ for every $z\mathrm{\ne }0$. Thus $G$ is positive definite and the pencil $G-\eta C$ is regular in the convention of Regular matrix pencils and homogeneous generalized eigenvalues, since $\det (G-0C)=\det G\mathrm{\ne }0$.

Supply a finite QZ sweep budget $N\ge 0$ and tolerance ${\tau }_{QZ}\ge 0$, and run Finite-budget QZ iteration with homogeneous status and residual output on $(G,C)$. Compute $G,C$ exactly in the mathematical procedure; a finite implementation must include their formation errors in the perturbation ledger or return qz-certificate-inconclusive. On qz-computed, require its exact-factor and local-update certificates; if either is unavailable, return qz-certificate-inconclusive. With these certificates, Every finite-budget QZ run returns a status and records unitary transforms and explicit deflations then records equivalence to a perturbed projected pencil. For each diagonal index $i$, set ${\alpha }_i=S_{ii}$ and ${\beta }_i=T_{ii}$. If $({\alpha }_i,{\beta }_i)=(0,0)$, return projected-pencil-unresolved; if ${\beta }_i\mathrm{\ne }0$, report the computed harmonic Ritz value ${\lambda }_i=\sigma +{\alpha }_i\mathrm{/}{\beta }_i$; if ${\beta }_i=0$, mark that candidate infinite-harmonic-value. These are values of the computed perturbed pencil, with the QZ residual and perturbation ledger retained; no exact-root, eigenvector, or forward-error claim is made. After processing all diagonal candidates, return available with the candidate list, its per-candidate marks, and the residual and perturbation ledger. Map a QZ budget-exhausted status to qz-budget-exhausted; map a QZ certificate-inconclusive or range-failure to qz-certificate-inconclusive; map singular-pencil-suspected to projected-pencil-unresolved.