Budgeted ordered Hermitian eigenvalue bisection by verified inertia

Input $n\ge 1$, a nonempty family of Hermitian $n\times n$ matrices enclosed by conjugate-symmetric interval rectangles, tolerance $\epsilon >0$, a total query budget $B\in {\mathbb{N}}_0$, and a fixed ordering, block plan and threshold $\theta \in (0,1]$ for the interval inertia certifier. Interpret all interval endpoints and shifts exactly.

1. Outward-compute $M\ge {\sup }_A\mathrm{\parallel }A{\mathrm{\parallel }}_F$ by bounding each entry modulus and summing their squares. If a finite bound cannot be obtained, return inconclusive with no eigenvalue intervals. Otherwise initialize, for each increasing index $k=1,\dots ,n$, the bracket $I_k=[-M,M]$ and successful-query count $s_k=0$. The Frobenius eigenvalue bound guarantees that these brackets contain every eigenvalue of every family member.

2. Repeat while fewer than $B$ total queries have been used and there is an index whose bracket width exceeds $\epsilon$ and which has not been marked blocked. Choose the least such index $k$. Query its exact midpoint $\tau$. Run Outward interval block LDL inertia certifier with pivot-inconclusive status on the shifted family $\{A-\tau I:A\in \mathcal{A}\}$ with the fixed plan. If the result is pivot-inconclusive, or its certified inertia has nonzero zero-count, mark this index blocked and leave $I_k$ unchanged. Otherwise set $\nu =n_{-}$, the certified number of negative eigenvalues. If $\nu \ge k$, replace the upper endpoint of $I_k$ by $\tau$; if $\nu <k$, replace the lower endpoint by $\tau$. Increase $s_k$ by one. A certified update halves the bracket width. Stop when the query budget is used or no such index exists.

3. Return every current bracket with status enclosed when its width is at most $\epsilon$, inconclusive if its index was blocked, or budget-exhausted if the total budget ended first. A zero-width initial bracket is already complete. Neither blocked pivots nor exhausted budget alter an existing bracket.

The algorithm does not perturb a shift to force an LDL pivot and does not infer singularity from a failed factorization. It returns uniform outer intervals for a family; it does not identify eigenvalue branches across parameter values.