Dense Riccati work counts and numerical acceptance require equation-level diagnostics

In a Householder Hessenberg reduction, there are at most $n$ reflectors. At each stage a reflector updates a trailing block with at most $n^2$ entries using matrix-vector and rank-one operations, so the initialization costs $O(n^3)$. In a Francis or QZ bulge-chasing sweep, there are $O(n)$ rotations/reflections; each is applied to $O(n)$ entries in the active matrix and accumulated factor, hence a sweep costs $O(n^2)$. The finite budgets in [F2]–[F3] therefore give $O(n^3+s{n}^2)$ core work.

Dense LU factorization of $U_1$ costs $O(n^3)$; applying its factors to $n$ right-hand sides costs $O(n^3)$. The residual product $(X{U}_1-U_2)$ is also $O(n^3)$, yielding the candidate solve count in [F1]. In the Lyapunov branch, [F4] imposes $N_A,N_B\le c_{0}n$. By step 1.1, each of its two dense Schur reductions therefore costs $O(n^3)$; exact certificate checks and factor transformations are also $O(n^3)$. Triangular substitution for $n^2$ unknown entries with $O(n)$ work per entry costs $O(n^3)$, so one solve in this cubic branch costs $O(n^3)$. The fixed controller is bounded there; arbitrary-terminating-controller work is separate.

Let $d$ be the reduction order, $b$ its diagonal block count and $I$ its initial inversion count. The reordering validation scan costs $O(d^2)$. Each local system has order at most eight, and each exact factor update touches $O(d)$ panel entries, so $k$ attempts cost $O(d^2+kd)$ by [F9]. On success, [F10] gives $k=I\le b(b-1)\mathrm{/}2\le d(d-1)\mathrm{/}2$, so the worst-case reordering core is $O(d^3)$; this success path also requires $K\ge I$ and sufficient $W$ for the entire execution through its final ordering scan. For a Riccati matrix of order $2n$, combining reduction, reordering, graph solve and dense equation residual multiplication preserves $O(n^3+s{n}^2)$ scalar-core work. Exact algebraic bit cost, evaluator implementation, dense factor-product evaluation and any additional dense residual multiplication are separate costs.

Each exact Newton-Kleinman pass has one Bartels–Stewart solve by [F5], costing $O(n^3)$ by step 2.1. Factorizing $R$ once costs $O(m^3)$. With $m$ controls, forming $B^{\ast }X$ and the gain uses $O(n^{2}m+m^{2}n)$ arithmetic including triangular solves with this pre-factored $R$; forming $K^{\ast }RK$ and $A-BK$ is bounded by the same $O(n^{2}m+n{m}^2)$ term. Summing over $J$ passes gives $O(m^3+J{n}^3+J(n^{2}m+n{m}^2))$. Each exact-arithmetic SDA recurrence step uses one dense $n\times n$ solve and a fixed number of dense products, each $O(n^3)$; [F6] therefore gives $O(N{n}^3)$ over $N$ exact steps. Finite point-certificate and residual-enclosure work is separate under [A1].

A small backward error for a computed QZ pair, as supplied by [F7], is a statement about an unstructured nearby pencil. It contains no premise that the perturbation preserves Hamiltonian or symplectic block relations, nor that it preserves positive definiteness of $Q$ or $R$. Consequently acceptance must separately compute the equation residual and symmetry defect, check $R+B^{\ast }XB\succ 0$ for DARE, and certify the closed-loop stability property in [F8]; [F1] explicitly reports these quantities. Neither ordering a computed form nor its unstructured backward error establishes a structured pencil perturbation or an equation-level stabilizing certificate.