Computed Schur decompositions and nonnormal spectra

Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$, let $n\ge 0$ and $A\in {\mathbb{F}}^{n\times n}$, and let $Q^{\ast }$ denote transpose over $\mathbb{R}$ and conjugate transpose over $\mathbb{C}$. A complex Schur pair for $A$ is a pair $(Q,T)$ with $Q^{\ast }Q=I$ and $A=QT{Q}^{\ast }$, where $T$ is upper triangular.

For real $A$, a real Schur pair is a pair $(Q,T)$ with $Q^{T}Q=I$ and $A=QT{Q}^T$, where $T$ is block upper triangular and every diagonal block is either a real $1\times 1$ block or a real $2\times 2$ block with negative characteristic-polynomial discriminant. Such a $2\times 2$ block has one nonreal conjugate eigenvalue pair. The definition does not assert that a finite shift strategy reaches such a pair.

For $B=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in {\mathbb{R}}^{2\times 2}$, its characteristic-polynomial discriminant means the exact real number $\mathrm{\Delta }(B)=(a+d{)}^2-4(ad-bc)$. “Negative discriminant” means the exact comparison $\mathrm{\Delta }(B)<0$.

For a real matrix $B=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$, define its characteristic-polynomial discriminant by $\mathrm{\Delta }(B)=(a+d{)}^2-4(ad-bc)$. Define $\mathrm{discSign}(B)$ to be $-1$, $0$, or $1$ according as the exact real number $\mathrm{\Delta }(B)$ is negative, zero, or positive. This is an exact mathematical predicate on the stored real entries, not an operation in the operationwise floating-point model. A computed procedure may report a sign only when its control predicate establishes this exact value; otherwise it reports undecided.

For a complex matrix $A\in {\mathbb{C}}^{n\times n}$ with $n\ge 1$ and $ϵ>0$, its closed $ϵ$-pseudospectrum is

${\mathrm{\Lambda }}_{ϵ}(A):=\{z\in \mathbb{C}:{\sigma }_{\min }(zI-A)\le ϵ\},$

where ${\sigma }_{\min }$ is the smallest singular value from The singular values of a linear map as the eigenvalues of the positive square root of T^*T. This is the unstructured complex perturbation convention in the spectral norm The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||. In particular, real $A$ is regarded as a complex matrix and admissible perturbations may be complex. The non-strict inequality fixes the boundary: points with ${\sigma }_{\min }(zI-A)=ϵ$ are included.

Let $A\in {\mathbb{C}}^{n\times n}$, let $U_0$ be unitary, and set $H_0=U_0^{\ast }A{U}_0$. For $j=1,\dots ,m$, suppose

$H_j=P_j^{\ast }(H_{j-1}+E_j+D_j)P_j,$

where each $P_j$ is unitary, $E_j$ is a local arithmetic perturbation, and $D_j$ is a local deflation perturbation. Then for $U_m=U_0{P}_1\cdots P_m$ there is a matrix $\mathrm{\Delta }$ such that

$H_m=U_m^{\ast }(A+\mathrm{\Delta })U_m,\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_F\le {\sum }_{j=1}^m(\mathrm{\parallel }{E}_j{\mathrm{\parallel }}_F+\mathrm{\parallel }{D}_j{\mathrm{\parallel }}_F)\mathrm{.}$

The assertion also holds over $\mathbb{R}$ with orthogonal factors.

If $n\ge 1$, $X\in {\mathbb{C}}^{n\times n}$, and $\mathrm{\parallel }X{\mathrm{\parallel }}_2<1$, then $I+X$ is invertible.

Let $n\ge 1$, let $H\in {\mathbb{C}}^{n\times n}$ be upper Hessenberg with every first-subdiagonal entry nonzero. Suppose $Q,V$ are unitary, $Q{e}_1=V{e}_1$, and both $Q^{\ast }HQ$ and $V^{\ast }HV$ are unreduced upper Hessenberg. Then $V^{\ast }Q$ is diagonal unitary with first diagonal entry $1$. Thus the two unitary transformations differ only by column phases. Over $\mathbb{R}$ the phases are signs.

Let $n\ge 1$, let $r\in \{1,2\}$, and require $n\ge 2$ when $r=2$. Let $H_0\in {\mathbb{F}}^{n\times n}$ be upper Hessenberg, and let $P_0$ be a Householder reflector supported on the first $\min (r+1,n)$ coordinates. Set $H_1=P_0^{\ast }{H}_0{P}_0$. For $j=1,\dots ,J:=\max (n-2,0)$, put $I_j=\{j+1,\dots ,\min (j+r+1,n)\}$. Let $P_j$ be either the identity on $I_j$ or a Householder reflector supported on $I_j$, in either case required to map the active vector $(H_j{)}_{I_j,j}$ to a multiple of the first coordinate vector, and set $H_{j+1}=P_j^{\ast }{H}_j{P}_j$. Then $H_{J+1}$ is upper Hessenberg.

If, in addition, $x\mathrm{\ne }0$, $P_{0}x=\alpha e_1$ with $\alpha \mathrm{\ne }0$, and $Q=P_0{P}_1\cdots P_J$, then $Q{e}_1=x\mathrm{/}\alpha$. Thus the exact chase preserves the initial direction while restoring the Hessenberg zero pattern.

For a stored complex column $x\in {\mathbb{C}}^m$, $m\ge 1$, and block $B\in {\mathbb{C}}^{m\times q}$, $q\ge 0$, call the Householder branch of Scaled real and complex Householder and Givens update arithmetic on $[xB]$. This is the canonical scaled real-component norm and separately scaled phase-modulus realization, with fixed sequential dots, real-coefficient multiplication, complex product and subtraction order. It includes the exact target-column overwrite. Return its $(v,\widehat{\tau },\widehat{\alpha },\widehat{x},\widehat{B})$ on success; a zero column returns identity, zero column and copied $B$. Report an invalid/nonpositive stored-vector norm as breakdown; every other invalid/out-of-range operation returns range-failure with its operation index and partial values.

The exact representative is $P(v)=I-2v{v}^{\ast }\mathrm{/}(v^{\ast }v)$ for nonzero stored $v$. Store this product representation rather than identifying the rounded rank-one action with an exactly unitary dense matrix. For polynomial-vector initialization, form the reflector from that external vector and use its separate-block application on the entire active row panel; do not overwrite an unrelated matrix column. The proof-backed target and separate-block coefficients are supplied by Scaled complex Householder and Givens steps have explicit local backward errors.

For every admitted finite input of Scaled complex Householder reflector step with explicit range status, the wrapper terminates with its specified success, identity, breakdown or range-failure return. On a zero input column it uses the identity and copies the separate block exactly, with zero target and separate-block errors and without evaluating $P(0)$. On a successful nonzero input it has $v\mathrm{\ne }0$, and $P(v)=I-2v{v}^{\ast }\mathrm{/}(v^{\ast }v)$ is unitary. Under the hypotheses of Scaled complex Householder and Givens steps have explicit local backward errors, the corresponding target-overwrite or separate-block error bounds apply to the actual application. No unconditional range success is asserted.

Let $B=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in {\mathbb{R}}^{2\times 2}$, set $s=\mathrm{tr}B=a+d$, $t=\det B=ad-bc$, and define $p(z)=z^2-sz+t$. Then $p(z)=\det (zI-B)$ and $p(B)=0$. If $s^2-4t<0$, the roots are a nonreal conjugate pair $\mu ,\bar{\mu }$, and for every real square matrix $H$ of positive dimension,

$p(H)=H^2-sH+tI=(H-\mu I)(H-\bar{\mu }I)$

is real. This supplies the exact polynomial used by a real double-shift step; it asserts no convergence of the iteration.

Let $A\in {\mathbb{C}}^{n\times n}$ with $n\ge 1$ and $ϵ>0$. With the closed convention of Closed epsilon-pseudospectrum in the spectral norm, the following sets are equal:

${\mathrm{\Lambda }}_{ϵ}(A)=\{z\in \mathbb{C}:\mathrm{\parallel }(zI-A{)}^{-1}{\mathrm{\parallel }}_2\ge {ϵ}^{-1}\}={\bigcup }_{\mathrm{\parallel }E{\mathrm{\parallel }}_2\le ϵ}\sigma (A+E)\mathrm{.}$

where the resolvent norm is defined to be $+\mathrm{\infty }$ when $zI-A$ is singular. Equivalently, $z\in {\mathrm{\Lambda }}_{ϵ}(A)$ exactly when ${\sigma }_{\min }(zI-A)\le ϵ$. The non-strict inequalities include the boundary.

Let $n\ge 1$, let $A=VD{V}^{-1}\in {\mathbb{C}}^{n\times n}$ be diagonalizable, where $D=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)$, and let $E\in {\mathbb{C}}^{n\times n}$. Every $\mu \in \sigma (A+E)$ satisfies

$\mathrm{dist}(\mu ,\sigma (A))\le {\kappa }_2(V)\mathrm{\parallel }E{\mathrm{\parallel }}_2,{\kappa }_2(V)=\mathrm{\parallel }V{\mathrm{\parallel }}_2\mathrm{\parallel }{V}^{-1}{\mathrm{\parallel }}_2\mathrm{.}$

No estimate independent of $V$ is asserted for a nonnormal diagonalization.

Input an exact upper-Hessenberg matrix $H\in {\mathbb{F}}^{n\times n}$, with $\mathbb{F}=\mathbb{C}$ or $\mathbb{R}$ and $n\ge 1$, and exactly one shift descriptor:

1. Complex single shift: $\mathbb{F}=\mathbb{C}$ and $\mu \in \mathbb{C}$. Set $p(z)=z-\mu$ and $r=1$.
2. Real double shift: $\mathbb{F}=\mathbb{R}$, $n\ge 2$, and $p(z)=z^2-sz+t$ with $s,t\in \mathbb{R}$. In the ordinary Francis branch, $s$ and $t$ are the trace and determinant of the trailing $2\times 2$ block; a declared exceptional shift may supply another real pair. Set $r=2$.

Form $x=p(H)e_1$. For a Hessenberg $H$, $x$ is supported in its first $r+1$ entries; compute only those entries. If $x=0$, return $H_{+}=H$, $Q=I$, and status zero-shift-vector. Otherwise choose a Householder reflector $P_0$ on the first $\min (r+1,n)$ coordinates with $P_{0}x=\alpha e_1$, embed it in ${\mathbb{F}}^{n\times n}$, and set $H_1=P_0^{\ast }H{P}_0$, $Q=P_0$.

For $j=1,\dots ,\max (n-2,0)$, in increasing order, let $I_j=\{j+1,\dots ,\min (j+r+1,n)\}$. Thus $I_j$ has at most three indices in a real double shift and at most two in a complex single shift. Extract $y=(H_j{)}_{I_j,j}$. If $y=0$, use the identity on $I_j$; otherwise choose a Householder reflector $P_j$ on $I_j$ sending $y$ to a multiple of its first coordinate vector. Embed $P_j$ in the identity, update $H_{j+1}=P_j^{\ast }{H}_j{P}_j$, and append it to $Q$ on the right. After the finite chase, check the exact matrix zero pattern and the first-column condition. Return completed only if the output is upper Hessenberg and $Q{e}_1$ is proportional to $p(H)e_1$; otherwise return bulge-chase-invariant-failure with the partial similarity factors. The procedure makes no convergence claim.

For every valid input of Exact finite Francis single- or double-shift Hessenberg QR step, and every allowed choice of its reflectors, the procedure terminates. If $x=p(H)e_1=0$, it returns $H_{+}=H$, $Q=I$ and zero-shift-vector. Otherwise it returns completed, with $H_{+}=Q^{\ast }HQ$ upper Hessenberg, $Q$ unitary, and $Q{e}_1=x\mathrm{/}\alpha$, where $P_{0}x=\alpha e_1$ and $\alpha \mathrm{\ne }0$. The bulge-chase-invariant-failure branch is unreachable for valid exact inputs. These claims include real exceptional quadratic descriptors and make no convergence assertion.

Let $n\ge 2$, let $H\in {\mathbb{R}}^{n\times n}$ be unreduced upper Hessenberg, and let $p(z)=z^2-sz+t$ be real with $p(H)$ nonsingular and $p(H)e_1\mathrm{\ne }0$. Assume the exact double-shift bulge chase from Exact finite Francis single- or double-shift Hessenberg QR step and the two successive shifted QR steps for the roots of $p$ both finish unreduced. Let $Q_b$ be the bulge-chase factor, and let $p(H)=Q_e{R}_e$ be a QR factorization with positive diagonal in $R_e$. Then $Q_b=Q_{e}D$ for a diagonal sign matrix $D$. Its first sign records the possible difference between the bulge reflector's normalization and the positive-diagonal QR normalization, and

$Q_b^{T}H{Q}_b=D^T(Q_e^{T}H{Q}_e)D\mathrm{.}$

Thus the real Francis step agrees with the real-normalized explicit two-shift QR similarity up to diagonal signs; arbitrary complex QR normalizations introduce diagonal unitary phases, which reduce to signs when both accumulated factors are real. No statement is made for a deflated or singular-shift branch.

Input a real or complex square matrix $A\in {\mathbb{F}}^{n\times n}$ with $n\ge 1$, a finite nonnegative deflation tolerance $\tau$, a nonnegative integer sweep budget $N$, a positive integer stagnation period $h$, a finite family of exceptional-shift tables $T_{a,b}$ indexed by original contiguous index intervals $[a,b]\subseteq [1,n]$ with $a<b$, optional exact rational/dyadic encodings of its stored real values, optionally a terminating exact evaluator of Exact sign predicate for a real 2x2 characteristic discriminant, and optionally a terminating outward evaluator for nonnegative expressions and Frobenius norms. The outward evaluator's upadd, upmul, and upsqrt calls return finite nonnegative represented upper bounds for the exact sum, product, and square root, while upnormF(X) returns a finite represented upper bound for $\mathrm{\parallel }X{\mathrm{\parallel }}_F$; any call may instead return unavailable. In the declared scalar-cost model, each upadd, upmul, and upsqrt call has unit cost and upnormF(X) makes one pass over the entries of $X$ with a fixed number of such calls per real component. The evaluator acts only on certificate bookkeeping. A formation breakdown is propagated with the operation index and partial factors. Every scalar operation in the main procedure is evaluated in the operationwise model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add. Any invalid, overflow, or underflow operation in the main procedure returns range-failure with the operation index and partial factors.

Each complex table entry is a finite represented scalar $\mu \in \mathbb{C}$; each real table entry is a pair of finite represented real coefficients $(s,t)$ for $z^2-sz+t$. Each table is an ordered finite list, possibly empty; an omitted interval has the empty list. These descriptors use the field of $A$. Tables support direct indexed lookup by interval and cursor; unused entries are not scanned. All interval-state updates use a single ordered pass over the current partition. Counters and table indices are exact integers. Maintain state $(c_{a,b},q_{a,b})$, initially $(0,0)$, for each current maximal diagonal interval separated by exact zero subdiagonals: $c$ counts completed ordinary block sweeps since the last reset and $q$ counts exceptional descriptors already consumed. After a split, discard the parent state and initialize every new child interval to $(0,0)$, using its own table. An unchanged interval retains its state. Completed one-by-one blocks, and real two-by-two blocks with verified negative discriminant, require no shift.

Start with $H=A$ and the empty factor product $Q=I$. Set the completed global sweep count to $k=0$ after initialization. Before attempting any sweep, and after every completed sweep, perform steps 2 and 5, in that order. If neither returns, snapshot the remaining active intervals in increasing left endpoint, and perform steps 3 and 4 once for each snapshotted interval in that order. No deflation scan or repartition occurs during this pass. After all its intervals finish, increment $k$ by one and repeat the scan and stopping test. All intervals in a pass use their current diagonal block when reached; previously applied similarities on disjoint blocks do not reschedule a block.

Before every real or complex formation in steps 1 and 4, test the target vector componentwise for exact zero, including an external initial polynomial vector. If it is zero, mark the stage identity, copy all affected matrix entries unchanged, skip formation and both left and right updates, append the embedded identity $P_j=I$ to the product representation, and record $E_j=0$ and arithmetic coefficient ${\alpha }_j={\bar{\alpha }}_j=0$. Do not evaluate $P(v)$ or a stored-vector norm in this branch. For a matrix target its column is already zero, so its target zero writes change nothing; for an external vector no matrix column is overwritten. Continue with the invariant checks, sweep counters and stopping tests specified below. Record and process every deflation write separately exactly as specified below; this branch does not discard a deflation perturbation. These identity instructions take precedence over the formation/update instructions in steps 1 and 4.

For each nonidentity stored reflector with active indices $S=(s_1,\dots ,s_m)$, nonzero vector $v\in {\mathbb{F}}^m$, and real computed coefficient $\widehat{\tau }$, the real or complex formation routine first performs the stated finite left application. Then perform the right application in this fixed order: for each matrix row $i=1,\dots ,n$, compute $d_i=\mathrm{fl}({\sum }_{a=1}^m{H}_{i,s_a}^L{v}_a)$ by left-to-right rounded products and additions; for $a=1,\dots ,m$, compute $c_a=\mathrm{fl}(\widehat{\tau }\overline{v_a})$, $g_{ia}=\mathrm{fl}(d_i{c}_a)$, and $H_{i,s_a}^R=\mathrm{fl}(H_{i,s_a}^L-g_{ia})$. Each complex product uses the six real operations of the arithmetic model. The exact factor appended to $Q$ is $P(v)=I-2v{v}^{\ast }\mathrm{/}(v^{\ast }v)$; the computed right update uses $\widehat{\tau }$ as displayed and is not asserted equal to multiplication by $P(v)$. For a matrix-target column, the formation routine's explicit zero writes are retained. In the initial polynomial-vector step there is no matrix-target column: use the entire active row panel for the left update and then apply the right update to the active columns. Record deflation writes separately, including a pure deflation with no following reflector as an identity-transform stage; a local error certificate must account for all other rounding and target-column writes.

1. Reduce $A$ to upper Hessenberg form with Householder similarities. For $k=1,\dots ,\max (n-2,0)$ in increasing order, use active indices $S=\{k+1,\dots ,n\}$, target $x=H_{S,k}$, and trailing left panel $B=H_{S,\{k+1,\dots ,n\}}$ with columns in increasing order. In the real branch use Scaled Householder reflector formation and application for the finite left application and overwrite; in the complex branch use Scaled complex Householder reflector step with explicit range status. Complete each similarity by the right application above on columns $S$. After the entire initialization loop, including when it is empty, check the resulting matrix's exact upper-Hessenberg zero pattern; on failure return bulge-chase-invariant-failure with the partial factors. Store the exact unitary reflector factors as a product representation $Q_0$.
2. In increasing global row index $i=2,\dots ,n$, test each nonzero first-subdiagonal entry by $\mathrm{\mid }{h}_{i,i-1}\mathrm{\mid }\le \tau (\mathrm{\mid }{h}_{i-1,i-1}\mathrm{\mid }+\mathrm{\mid }{h}_{i,i}\mathrm{\mid })\mathrm{.}$ For a complex entry $z=a+ib$, evaluate $\mathrm{\mid }z\mathrm{\mid }$ by $s=\max (\mathrm{\mid }a\mathrm{\mid },\mathrm{\mid }b\mathrm{\mid })$ and $s\sqrt{(a\mathrm{/}s{)}^2+(b\mathrm{/}s{)}^2}$ when $z\mathrm{\ne }0$, with divisions, squares, sum, square root and final scaling rounded in the stated order; use $\mathrm{\mid }0\mathrm{\mid }=0$. Return range-failure if this evaluation fails. Compute the diagonal-magnitude sum first, then multiply by $\tau$ in the operationwise model; compare the resulting finite values exactly. When the test holds, set that entry to zero and record its original value as a deflation perturbation. After the scan, form the maximal intervals separated by exact zero subdiagonals and update interval states by the rule above. The equality case deflates. Do not use the Hermitian-tridiagonal Wilkinson shift rule for a general Hessenberg matrix.
3. For the current snapshotted interval $[a,b]$, let $L=H_{a:b,a:b}$ and $\mathrm{\ell }=b-a+1$. If $c_{a,b}=h$, read entry $q_{a,b}+1$ of $T_{a,b}$. If absent, return stagnation-exhausted before this block's chase. Otherwise consume it by incrementing $q_{a,b}$ once and use its complex scalar shift or real coefficient pair. After this exceptional block sweep completes, set $c_{a,b}=0$. If $c_{a,b}<h$, use the ordinary shift: in the complex branch $\mu =L_{\mathrm{\ell },\mathrm{\ell }}$; in the real branch, for the trailing block $\left(\begin{array}{cc}{a}^{\mathrm{\prime }}& b^{\mathrm{\prime }}\\ c^{\mathrm{\prime }}& d^{\mathrm{\prime }}\end{array}\right)$, compute $s=\mathrm{fl}(a^{\mathrm{\prime }}+d^{\mathrm{\prime }})$ then $t=\mathrm{fl}(\mathrm{fl}(a^{\mathrm{\prime }}{d}^{\mathrm{\prime }})-\mathrm{fl}(b^{\mathrm{\prime }}{c}^{\mathrm{\prime }}))$ in that order. Return range-failure on a failed operation. After this ordinary block sweep completes, increment $c_{a,b}$ by one. A split at the next scan resets each new child as specified above; unchanged intervals retain these updated states.
4. On the diagonal block $L$ selected in step 3, apply the index pattern of Exact finite Francis single- or double-shift Hessenberg QR step, with its dimension $\mathrm{\ell }$ and local indices $1,\dots ,\mathrm{\ell }$. In the vector formulas in this step, $H$ means that current diagonal block. Translate every local index $i$ to global index $a+i-1$; embed each factor in the full $n\times n$ identity. The left panel extends through global column $n$, and the right application runs through all global rows, so upper off-diagonal blocks are updated as well. For the initial single-shift vector compute $x_1=\mathrm{fl}(h_{11}-\mu )$ and $x_i=h_{i1}$ for $i>1$. For the initial real double-shift vector, compute $u=H{e}_1$, then $w=Hu$ by left-to-right rounded matrix-vector products, then $x=\mathrm{fl}(\mathrm{fl}(w-su)+t{e}_1)$ componentwise. Compute only the first $r+1$ components from the Hessenberg support pattern; on range failure return the operation index and partial factors. For a chase at local column $j$, use the globally translated active indices $S=I_j$, the corresponding global target column $a+j-1$, and the trailing left panel through global columns $a+j,\dots ,n$ in increasing order. Call the real or complex formation routine, write the target tail zeros exactly, complete the two-sided update by the right-kernel order above on columns $S$, and append the exact reflector representation to $Q$. In the initial polynomial-vector step there is no matrix-target column; use the full active row panel for the left update and then apply the right update to its active columns. After the block chase, perform the following exact upper-Hessenberg zero-pattern check, including when all its stages were identities. For $i=1,\dots ,n$ in increasing order, if $a\le i\le b$, test $h_{ij}=0$ for $j=1,\dots ,i-2$ in increasing order; otherwise test $h_{ij}=0$ for $j=a,\dots ,\min (b,i-2)$ in increasing order. Skip every empty index range. On the first nonzero tested entry return bulge-chase-invariant-failure with the partial matrix and factors. These are precisely the below-first-subdiagonal positions whose row or column belongs to $[a,b]$. Enumerate only these ranges; do not scan all $n^2$ positions and filter them. The unchanged complementary positions retain the zero values established by initialization or the previous accepted check. Deflation writes affect only the first subdiagonal and do not change those positions. Use Left and right scaled Householder errors give a concrete similarity bound to store the proved two-sided coefficient ${\alpha }_{m_j}=a_{m_j}+b_{m_j}+a_{m_j}{b}_{m_j}$, with $a$ the target-overwrite coefficient or separate-block coefficient as actually used and $b$ the right separate-block coefficient. This gives $\mathrm{\parallel }{E}_j{\mathrm{\parallel }}_F\le {\alpha }_{m_j}\mathrm{\parallel }{\widehat{H}}_{j-1}{\mathrm{\parallel }}_F$ when its $m_{j}u<1$ and range hypotheses hold. Apply the same certificate to every Hessenberg-initialization similarity. If any step lacks that certificate, retain the residual diagnostic and set the backward-error-certificate status to inconclusive.
5. Inspect maximal intervals in increasing left endpoint. A size-one interval is completed. A complex interval of size at least two, or a real interval of size at least three, is active. For each real size-two interval determine its exact discriminant sign as below: a negative sign completes that interval, while zero or a positive sign leaves it active. Stop with Schur-computed when all intervals are completed. Use the supplied evaluator, or the finite integer recipe in Rational or dyadic stored real blocks have a finite exact discriminant-sign evaluator when exact rational/dyadic encodings are available, for each real block's $\mathrm{discSign}$ as defined in Exact sign predicate for a real 2x2 characteristic discriminant. If no exact sign is available, return schur-type-undecided and do not claim Schur-computed. If any active interval remains and $k=N$, return budget-exhausted; in particular, with $N=0$ return Schur-computed only when the initialized matrix already has the target block structure. Return the partial matrix and factors on every failure or nonconvergence status.