Sparse symmetric-indefinite block LDL* with threshold tests and failure status

The exact-arithmetic branch is specified first; the finite-precision branch below implements the same declared pivots by certified real-component kernels. Input a Hermitian $A\in {\mathbb{C}}^{n\times n}$, an ordering $\pi =(v_0,\dots ,v_{n-1})$ and its simultaneous permutation matrix $P$ in the convention of Permutation matrices, partial pivoting, and the pivot-growth factor, an ordered partition of all permuted positions into consecutive blocks of size $1$ or $2$, and a threshold $\theta \in (0,1]$. The partition is exhaustive and disjoint; for $n=0$ it is empty and $P$ is the unique empty permutation matrix (the extension of the referenced row convention to dimension zero). Apply $P$ once and initialize the exact active matrix $S=PA{P}^{\ast }$, $L=I_n$, and the block-diagonal output array $D_{\mathrm{b}\mathrm{l}\mathrm{k}}=0$. Scalar complex absolute values mean exact complex moduli; $\mathrm{\mid }(D_r^{-1})\mathrm{\mid }$ below means entrywise absolute value, and vector inequalities are componentwise. Form the structural graph from Undirected structural graph of a Hermitian matrix, then relabel its vertex $v_i$ by ordered position $i$; use the graph and fill convention of Structural graphs and ordered symmetric elimination on this position-labeled graph. At stage $r$, let $J_r$ be the next declared block, which is the leading active block, and let $R_r$ be the remaining positions after $J_r$. Write the current active matrix as $S=\left(\begin{array}{cc}{D}_r& B_r^{\ast }\\ B_r& C_r\end{array}\right),$ with the blocks indexed by $J_r,R_r$. For a $1\times 1$ block $J_r=\{t\}$, write $D_r=[d_r]$ and require $d_r=S_{tt}\mathrm{\ne }0$ and ${\max }_{i\in R_r}\mathrm{\mid }{S}_{it}\mathrm{\mid }\le {\theta }^{-1}\mathrm{\mid }{d}_r\mathrm{\mid }\mathrm{.}$ For a $2\times 2$ block $J_r=\{s,t\}$, $D_r=S_{J_r,J_r}$ is the Hermitian principal block $D_r=\left(\begin{array}{cc}{S}_{ss}& S_{st}\\ \overline{S_{st}}& S_{tt}\end{array}\right)\mathrm{.}$ Require $\det D_r\mathrm{\ne }0$, and let $c_1={\max }_{i\in R_r}\mathrm{\mid }(B_r{)}_{i1}\mathrm{\mid }$ and $c_2={\max }_{i\in R_r}\mathrm{\mid }(B_r{)}_{i2}\mathrm{\mid }$, with an empty maximum equal to zero. Accept the pair only if $(\mathrm{\mid }(D_r^{-1}{)}_{ij}\mathrm{\mid }{)}_{i,j=1}^2\left(\begin{array}{c}{c}_1\\ c_2\end{array}\right)\le {\theta }^{-1}\left(\begin{array}{c}1\\ 1\end{array}\right)$ componentwise, where scalar absolute values are complex moduli. If a declared block fails its test, return pivot-failure$(r)$.

For each accepted block in the exact branch, compute $M_r=B_r{D}_r^{-1}$, store $D_r$ in the $J_r\times J_r$ block of $D_{\mathrm{b}\mathrm{l}\mathrm{k}}$ and $M_r$ in the $R_r\times J_r$ block of $L$, and update the active trailing matrix to $C_r-B_r{D}_r^{-1}{B}_r^{\ast }$. In the symbolic graph, let $N(J_r)$ be the union of the active graph neighbors of the vertices in $J_r$, restricted to $R_r$; remove $J_r$ and connect every pair of distinct vertices in $N(J_r)$. Retain all positions allowed by this symbolic update, including positions whose current numerical value is zero. If a block fails its test, return pivot-failure$(r)$ with no factor arrays. On completion return the stored arrays $(P,L,D_{\mathrm{b}\mathrm{l}\mathrm{k}})$, including the empty arrays in dimension zero. The exact branch makes no universal growth bound.

For the finite-precision branch, additionally supply the kernel's floating-point format with unit roundoff $0<u<1$ and a nonnegative integer certificate budget $b_r$ for each declared block. The input entries must be stored values in that format. In this branch, independently initialize the stored active matrix $S=PA{P}^{\ast }$, $\widehat{L}=I_n$, and $D_{\mathrm{b}\mathrm{l}\mathrm{k}}=0$. At each declared block call Certified real-component Hermitian one-by-one and two-by-two LDL* kernels on $(D_r,B_r,C_r)$ with threshold $\theta$, unit roundoff $u$, a fresh controller budget $b_r$, and the same symbolic block-neighbor clique. Budgets are local to their calls; unused units do not carry to another stage. On kernel success, store its returned pivot $D_r$ in the $J_r\times J_r$ block of $D_{\mathrm{b}\mathrm{l}\mathrm{k}}$, store ${\widehat{M}}_r$ in the $R_r\times J_r$ block of $\widehat{L}$, and continue on its Hermitian ${\widehat{S}}_{r+1}$. On any kernel failure, return its range-failure, pivot-failure or pivot-inconclusive status together with the outer stage index $r$; discard scratch data for that block and return no factor arrays. On completion return $(P,\widehat{L},D_{\mathrm{b}\mathrm{l}\mathrm{k}})$ together with its pivot certificates. Only certified admissible blocks are accepted; unresolved determinant or threshold tests are inconclusive. No general complex division, automatic pivot existence or universal factor-growth guarantee is assumed.

Block LDL* residual errors propagate with actual block growth ↗ proves that a successful exact-arithmetic run returns a unit lower block-triangular $L$ and block-diagonal $D_{\mathrm{b}\mathrm{l}\mathrm{k}}$ with $PA{P}^{\ast }=L{D}_{\mathrm{b}\mathrm{l}\mathrm{k}}{L}^{\ast }$, including the empty case. Its proof derives the block congruence directly from the update instructions; the identity is a correctness result, not an additional instruction.