Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms

Inputs are finite CARE or DARE data from Standard CARE and DARE data, equations, and conventions, finite Schur or QZ sweep budgets, an adjacent-swap budget $K$, a scalar/evaluator work budget $W$, a positive local separation threshold $\eta$, and the exact arithmetic controller or bounded outward evaluator for Finite-budget stable block reordering for Schur and QZ forms. The budget $W$ also charges every graph-product enclosure and local acceptance comparison. The graph stage also takes finite dyadic proposals $R_g,\widehat{Y}$ for a point inverse and solution matrix, together with outward enclosures of the exact product-factor entries and the certificate data required by the applicable local residual-ball theorem. If a proposal, enclosure, or certificate is unavailable, the corresponding graph or acceptance result is inconclusive. For CARE form $H=\left[\begin{array}{cc}A& -G\\ -Q& -A^{\ast }\end{array}\right]$; for DARE form $N=\left[\begin{array}{cc}A& 0\\ -Q& I\end{array}\right]$ and $M=\left[\begin{array}{cc}I& G\\ 0& A^{\ast }\end{array}\right]$. The procedure never forms $A^{-1}$ and does not require a separately supplied ordered basis.

Each local residual-ball packet contains its proposed radius, residual and inverse-norm bounds, norm bounds, and the required Lyapunov or Stein witness matrices with exact factorization witnesses for positive-definite and positive-semidefinite inequalities. Check all supplied matrix equalities exactly and all scalar bounds with the finite outward evaluator. A missing witness or unresolved comparison returns inconclusive; failure of a sufficient residual-ball test alone does not reject a candidate.

1. For CARE, run Finite-budget computed Francis Schur reduction with explicit statuses on $H$. For DARE, run Finite-budget QZ iteration with homogeneous status and residual output on $(N,M)$. Propagate any budget, range, invariant-pattern, or pencil-regularity failure as an explicit inconclusive status. The returned residuals and factor backward-error certificates are those specified by the corresponding supplier items; they are not interpreted as structure-preserving perturbations.
2. On a successful reduction, invoke Finite-budget stable block reordering for Schur and QZ forms with the CARE strict-left-half-plane selector or DARE strict-unit-disk selector and required selected dimension $n$. Propagate every non-ordered result as its explicit status, including boundary-spectrum, separation-inconclusive, swap-separation-inconclusive, arithmetic-inconclusive, range-failure, swap-budget-exhausted, and work-budget-exhausted. The returned exact product factors, together with Finite-budget stable block reordering has exact adjacent-swap correctness and status, certify ordering of the represented computed form and transport the original unstructured reduction residual. For CARE take the first $n$ columns of the updated Schur factor; for DARE take the first $n$ columns of the updated right QZ factor, never the left factor. If the relevant exact factor or residual certificate is unavailable, keep the corresponding diagnostic inconclusive.
3. Write the ordered exact product basis as $U=\left[\begin{array}{c}{U}_1\\ U_2\end{array}\right]$ and view the supplied $n\times n$ matrix $\widehat{Y}$ by columns ${\widehat{y}}_j$. Enclose the entries of $A_g=U_1^{\ast }$ and $B_g=U_2^{\ast }$ by finite outward rectangles. Using the supplied dyadic proposals, outward-evaluate $I-R_g{A}_g$ once and let $q$ be an upper bound for its Frobenius norm; the same enclosure applies to every matrix in the product of entry rectangles. If $q\ge 1$ or the enclosure is unavailable, return graph-block-inconclusive. For each column $b_j$ of $B_g$, outward-evaluate the full uniform residual enclosure $R_g(b_j-A_g{\widehat{y}}_j)$ over the rectangles and choose a common finite upper bound $r$ for its Euclidean norm. If any enclosure fails, return graph-block-inconclusive. Apply A uniform approximate inverse and residual enclose every linear solution to each column: the exact system $A_{g}Y=B_g$ has a unique solution and each column is within $r\mathrm{/}(1-q)$ of the corresponding column of $\widehat{Y}$. Moreover $A_g$ and hence $U_1$ are invertible, and $\mathrm{\parallel }{U}_1^{-1}{\mathrm{\parallel }}_2\le \mathrm{\parallel }{R}_g{\mathrm{\parallel }}_F\mathrm{/}(1-q)$ by the Neumann bound and submultiplicativity. Return this bound as the graph-block certificate; no explicit inverse is formed.
4. Set $X_0={\widehat{Y}}^{\ast }$ and $\widehat{X}=(X_0+X_0^{\ast })\mathrm{/}2$. Compute outward enclosures for the CARE or DARE residual, the Hermitian symmetry defect, and, for DARE, $R+B^{\ast }\widehat{X}B$. Validate the supplied certificate packet against the hypotheses of A CARE residual and Lyapunov margin certify a unique stabilizing root in a matrix ball or A DARE residual, Stein inverse bound, and Lyapunov margin certify a stabilizing root, respectively. If the theorem certifies a unique stabilizing root in the stated ball, return the candidate, residual data, graph-block bound, stability witness and certified root ball. A direct exact witness that the candidate fails a required positivity or stability condition returns candidate-rejected; failure of a sufficient theorem test or unavailable data returns inconclusive. No residual by itself certifies the stabilizing branch or a nearby positive $Q,R$.

This is the finite candidate-extraction stage for the ordered Schur/QZ solvers. Its ordering prerequisite is the finite adjacent-block routine and correctness theorem cited above; a successful order applies to the represented computed form, with the separately stated diagnostics still required for Riccati acceptance.