Finite-budget QZ iteration with homogeneous status and residual output

Input a regular pencil $(A,B)$ with $A,B\in {\mathbb{C}}^{n\times n}$, $n\ge 1$, a nonnegative integer sweep budget $N$, and a finite stored real tolerance $\tau \ge 0$. Real input data are embedded in $\mathbb{C}$. Scalar updates of the stored matrices use the operationwise model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add. Use zero-based matrix indices throughout. Each active block $[a:b]$ includes both endpoints; its relative coordinate $0$ is global index $a$. Use the canonical stored Givens generator and application order of Scaled real and complex Householder and Givens update arithmetic, with the common-pair orientations and explicit coefficients $v,h,\eta$ of Common computed Givens actions certify both pencil matrices and factor residuals. Generate each rotation ONCE and apply its same stored coefficients to BOTH matrices. Retain the exact normalized unitary representatives as product records, never as purported stored dense unitary matrices. Left rotations annihilate a column's second entry; right rotations annihilating a row's first entry use the coordinate reversal/adjoint construction of that lemma. After each genuine matrix target application write only its intended target to exact zero and include that write in the local coefficient $\eta$. An external-vector application has coefficient $v$ and no matrix-target overwrite. Local roundoff certification requires $0<u<1$; otherwise retain diagnostics with certificate-inconclusive. Record each elementary rotation separately. If the source cannot produce its admissible factor, return range-failure or certificate-inconclusive with diagnostics.

1. Execute the finite index loops of Givens reduction of a matrix pair to Hessenberg-triangular form with these COMPUTED common rotations: triangularize $B$ with left targets $B_{i,j}$; then reduce $A$ with left targets $A_{i,j}$ followed by right targets $B_{i,i-1}$. Every application updates both whole arrays. The exact initializer and Givens reduction terminates with a unitary-equivalent Hessenberg-triangular pair supply the index schedule and support induction, not exact rounded reconstruction. Retain each local factor and residual defined against its exact representative. Include structural target writes in that local arithmetic residual. Record all OTHER explicit zero writes separately: their post-action perturbations are pulled back by the local factor adjoints before entering the pre-action $D_j^A,D_j^B$ ledger. A pure tolerance write is an identity-factor stage. Never count a structural write twice.

Initialize the sweep counter to zero. Process active blocks in increasing first index, splitting them at exact zero subdiagonals of $H$. In each deflation pass execute step 2, then repeat step 3 for the smallest available non-isolated zero diagonal of $T$ until none remains or a status exits. Then run step 5; if it returns a status, stop. Otherwise, if the sweep counter equals $N$, return budget-exhausted. If not, increment the counter, execute step 4 on all remaining active blocks, and repeat the deflation pass. In particular $N=0$ permits initialization/deflation but no step-4 sweep.

2. On each active block $H_{a:b,a:b},T_{a:b,a:b}$, apply the following deflation tests before a sweep. For $i=a,\dots ,b-1$, set $H_{i+1,i}$ to zero when $\mathrm{\mid }{H}_{i+1,i}\mathrm{\mid }\le \tau (\mathrm{\mid }{H}_{i,i}\mathrm{\mid }+\mathrm{\mid }{H}_{i+1,i+1}\mathrm{\mid }),$ and record the negative of its old value at that position in $D^A$, with all other entries zero. For $k=a,\dots ,b$, set $T_{k,k}$ to zero when $\mathrm{\mid }{T}_{k,k}\mathrm{\mid }\le \tau (\mathrm{\mid }{T}_{k-1,k}\mathrm{\mid }+\mathrm{\mid }{T}_{k,k+1}\mathrm{\mid }),$ using zero for a missing boundary term outside the active block, and record the negative of the old value at that position in $D^B$, with all other entries zero. Treat each write as a separate identity-factor stage, so the new matrix is the old matrix plus its recorded perturbation. Evaluate each displayed modulus by the canonical rounded scaled two-component norm; evaluate its additions and tolerance product with the declared rounded real operations, then compare the stored finite values exactly. Excluded operations return range-failure. The tests mean these rounded comparisons, not an assertion about exact moduli at the threshold. Save the actual old entries, so their deflation perturbations remain exact regardless of the test. A one-by-one diagonal pair at $k$ is isolated when $H_{k,k-1}=0$ and $H_{k+1,k}=0$, omitting a boundary entry when $k=a$ or $k=b$. If it has $T_{k,k}=0$ and $H_{k,k}\mathrm{\ne }0$, report an infinite candidate for the computed pencil and deflate it from the active block. If the isolated diagonal pair is $(0,0)$, return singular-pencil-suspected without assigning an eigenvalue.

3. To move a non-isolated zero $T_{k,k}$ to the top of its active block, for $j=k-1,k-2,\dots ,a$ generate a right factor from the row pair $(T_{j,j},T_{j,j+1})$ and apply it to columns $j,j+1$, setting $T_{j,j}$ to zero. Then, when $j+2\le b$, generate a left factor from $(H_{j+1,j},H_{j+2,j})$ and apply it to rows $j+1,j+2$, setting the resulting bulge $H_{j+2,j}$ to zero. Finally, when $a<b$, generate a left factor from $(H_{a,a},H_{a+1,a})$ and apply it to rows $a,a+1$, setting $H_{a+1,a}$ to zero. Record all rounded update residuals and target writes. If this isolates $(H_{a,a},T_{a,a})=(h,0)$ with $h\mathrm{\ne }0$, report the infinite candidate and remove the first row/column from the active block. If the isolated pair is $(0,0)$, return singular-pencil-suspected; if isolation fails, return certificate-inconclusive. Each successful isolation removes one index, so at most $n$ such removals occur.

4. For each remaining active block with more than one row in the current sweep, choose the homogeneous shift $[\alpha :\beta ]=[H_{b,b}:T_{b,b}]$ if this pair is nonzero and $T_{b,b}\mathrm{\ne }0$; if $T_{b,b}=0$, use $[0:1]$. Write $\widehat{H}=H_{a:b,a:b}$ and $\widehat{T}=T_{a:b,a:b}$, with relative indices $0,\dots ,b-a$, and form $x=(\beta \widehat{H}-\alpha \widehat{T})e_0\mathrm{.}$ Compute $x_0,x_1$ using the declared rounded complex products/subtractions and generate a left factor from $(x_0,x_1)$. Apply it to relative rows $0,1$ of both matrices without a matrix-target overwrite. Its rounding changes the selected factor, not its application certificate. Generate a right factor from the row pair $({\widehat{T}}_{1,0},{\widehat{T}}_{1,1})$ and apply it to relative columns $0,1$, setting ${\widehat{T}}_{1,0}$ to zero. For relative $j=1,\dots ,b-a-1$, generate a left factor from $({\widehat{H}}_{j,j-1},{\widehat{H}}_{j+1,j-1})$ and apply it to rows $j,j+1$, setting the current Hessenberg bulge ${\widehat{H}}_{j+1,j-1}$ to zero; then generate a right factor from $({\widehat{T}}_{j+1,j},{\widehat{T}}_{j+1,j+1})$ and apply it to columns $j,j+1$, setting ${\widehat{T}}_{j+1,j}$ to zero. Update and retain the products $Q,Z$; record every local residual including its structural target write. Apply the embedded transformations to the entire pair, retaining the transformed off-block data. All divisions by a generalized eigenvalue ratio are avoided.

5. After each infinite isolation and before every successful return, scan all isolated diagonal pairs. Any $(0,0)$ pair returns singular-pencil-suspected without an eigenvalue. Stop with qz-computed only when $H$ is upper triangular and every diagonal pair is nonzero. Otherwise stop after $N$ sweeps with budget-exhausted. Range failures return range-failure with partial factors; unavailable local certificates return certificate-inconclusive. Neither a rounded diagnostic nor a tolerance-induced infinite candidate asserts an exact infinite eigenvalue of the original pencil.

For local-accumulation bounds use ${\mathrm{\ell }}_j=\eta$ for matrix-target actions and ${\mathrm{\ell }}_j=v$ for external-vector/raw actions, plus the separately saved actual tolerance perturbations. For an independent residual certificate execute the factor-action/column procedure of Common computed Givens actions certify both pencil matrices and factor residuals: use stored raw kernels without zero overwrites, propagate their $v$ allowances, use Rounded matrix products give certified linear and normal-equation residual allowances only on STORED matvec inputs, and include the final subtraction allowance. Exact normalized factor entries are not silently treated as stored inputs. Evaluate each certificate using the finite exact real-controller expression trees/loops in the local lemma and component absolute sums as norm upper bounds. Controller operations are separate from rounded update arithmetic; for rational/binary stored data and rational $u$ this is exact rational computation. No opaque certification oracle is used. Failure of this residual route's dimension/range hypotheses makes that route inconclusive and does not invalidate a valid independent local-accumulation bound. Always retain available diagnostics.

The output is $(Q,S,T,Z,\text{status})$, where $S$ is the current $H$ and $T$ is the current second matrix, the exact factor products when available, the raw residuals $R_A=Q^{\ast }AZ-S$ and $R_B=Q^{\ast }BZ-T$, and the recorded local arithmetic and deflation perturbations. The procedure asserts no unconditional convergence or small-roundoff bound.