Linearly budgeted dense Bartels-Stewart work with explicit controller costs

Hessenberg reduction uses at most $\max (n-2,0)$ reflector steps. For $n\ge 3$, forming one reflector costs $O(n)$ scalar operations, and applying its two-sided similarity to the remaining dense submatrix costs $O(n^2)$; summing over at most $n$ steps gives $O(n^3)$. Any full initialization zero-pattern checks also cost at most $O(n^2)$ per stage, hence at most $O(n^3)$ in total. For $n=1,2$, there are no such reflector stages and no below-subdiagonal entries.

For an active block of size $r\ge 2$, a Francis sweep has at most $\max (r-2,0)+1$ initial/chase reflectors of length two or three. Each acts on a bounded number of rows and columns across at most $n$ entries. For a processed interval $[a,b]$ of length $r$, every matrix write has a row or column in that interval. Before the chase, initialization or the preceding accepted check has established that the complementary below-subdiagonal positions are zero. The prescribed post-block check enumerates only the positions touching this interval: at most $nr$ in its rows and $nr$ in its columns, plus the $n$ row-loop visits. It is therefore equivalent to the full Hessenberg check and costs $O(nr)$, since every active interval has $r\ge 2$. The disjoint active lengths sum to at most $n$, so all these checks cost $O(n^2)$ per sweep, even if every polynomial vector is zero and all factors are identities. The explicit partition/deflation passes and direct shift-table lookups also fit within $O(n^2)$; for $n=1$ there is no active sweep. Thus a full sweep, including all non-controller status work, costs $O(n^2)$. The linear sweep budgets therefore give $O(n^3)$ matrix work for the two Schur calls. A range, breakdown, invariant, budget, missing-shift or unavailable-sign failure stops within these bounded loops and adds only its partial-output work; it cannot increase their worst-case count. The same bound covers materializing the recorded factor products: initialization contributes $O(n^3)$ and each bounded-support chase factor updates only a bounded number of dense-factor columns, at cost $O(n)$.

Each exact Schur-certificate matrix product, the transform $U^{\ast }CV$, and the final transform $UY{V}^{\ast }$ cost $O(n^3)$. The block substitution has at most $n^2$ block pairs; each pair sums at most $O(n)$ earlier blocks of bounded size and solves a system of dimension at most four, so all substitution work is $O(n^3)$.

Each sweep checks at most $O(n)$ active blocks, and initialization and final checks add at most $O(n)$ such calls. With $O(n)$ sweeps there are at most $O(n^2)$ sign/representation-controller calls. A bounded call executes at most $K$ instructions, giving $O(K{n}^2)$ work; the fixed built-in exact polynomial tree and rational/dyadic recipe are constant-size special cases. In arbitrary-terminating mode their actual total work is precisely the additional $C_{\mathrm{a}\mathrm{u}\mathrm{x}}$.

The backward-error accumulator starts with one outward Frobenius norm of the input, costing $O(n^2)$ by the declared entrywise evaluator model. Each similarity uses a fixed number of scalar upper-bound calls once its local coefficient is evaluated. The explicit real/complex coefficient formulas require $O(m)$ scalar operations on active dimension $m$: their dimension-dependent powers can be formed by repeated multiplication and a square root for a half-integer exponent. Thus the at most $n$ initialization coefficients cost $O(n^2)$ in total, while each length-two/three chase coefficient costs $O(1)$. There are $O(n^2)$ chase similarities over the linear number of sweeps. Each recorded one-entry deflation has Frobenius norm equal to the modulus of its signed stored value, evaluated from that one-entry list with $O(1)$ scalar work; at most $O(n)$ such writes occur per sweep, hence $O(n^2)$ in total. Each stage then makes a fixed number of recurrence calls. Unavailable coefficient/evaluator results only stop certificate bookkeeping. Consequently this entire ancillary accumulation costs $O(n^2)$ and fits inside the cubic matrix-work bound, including failure branches.

The reductions, sweeps, exact certificates, transforms, block sums and fixed-size solves contribute $O(n^3)$, and step 1.4 supplies the complete control contribution. Adding them gives $O(n^3+K{n}^2)$ and the fixed-$K$ cubic consequence, or $O(n^3+C_{\mathrm{a}\mathrm{u}\mathrm{x}})$ for the richer terminating route. No bound on integer bit length or bit-operation cost is used.