LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Hermitian block LDL* kernels have explicit roundoff and actual-factor residual bounds

Statement

For a successful Certified real-component Hermitian one-by-one and two-by-two LDL* kernels, let $k \in {1, 2}$ and $t$ be its trailing dimension. Every accepted $D$ is nonsingular and satisfies the original exact componentwise threshold test. For either size put $g_{j} = (1 + 6 u) / (1 - (j - 1) u) - 1$ for $j = 1, 2$ . For $k = 1$ put $ω_{1} = u$ . For $k = 2$ put $μ = \frac{ϵ_{d}}{∣ \hat{d} ∣} < 1, ν = \sqrt{2} u (1 + μ) + μ,$ $χ = u + (1 + u) (\sqrt{2} g_{2} (1 + u) + u), ω_{2} = ν + χ (1 + ν) .$ For either size define $q_{k} = (1 + u) (1 + g_{k}) (1 + ω_{k}) - 1, e_{M} = ω_{k} ∥ B ∥_{F} ∥ D^{- 1} ∥_{2},$ $β = \sqrt{2} (u ∥ C ∥_{F} + q_{k} ∥ B ∥_{F}^{2} ∥ D^{- 1} ∥_{2}), η_{k, t} = \sqrt{2} \max {u \sqrt{t}, k q_{k}} .$ Then, writing $M = B D^{- 1}$ and $Δ = \hat{S} - (C - B D^{- 1} B^{*})$ , $∥ \hat{M} - M ∥_{F} \leq e_{M}, ∥ Δ ∥_{2} \leq β \leq η_{k, t} (∥ C ∥_{2} + ∥ B ∥_{2}^{2} ∥ D^{- 1} ∥_{2}) .$ For $t = 0$ all residuals are zero and use $e_{M} = β = η_{k, 0} = 0$ . The coefficients are explicit unit-roundoff bounds, $O (u)$ at fixed nonzero normalized determinant as $u \to 0$ ; near-singular scaled pivots have no uniform smallness guarantee.

The actual stored multipliers also have coupling residual $N = \hat{M} D - B$ . Set $\hat{T} = (\begin{array}{cc} I & 0 \\ \hat{M} & I \end{array})$ . The full reconstruction residual satisfies $F = (\begin{array}{cc} D & B^{*} \\ B & C \end{array}) - \hat{T} diag (D, \hat{S}) {\hat{T}}^{*} = (\begin{array}{cc} 0 & - N^{*} \\ - N & - Δ - (\hat{M} - M) B^{*} - \hat{M} N^{*} \end{array}),$ $∥ F ∥_{2} \leq f : = β + e_{M} ∥ B ∥_{2} + (1 + ∥ \hat{M} ∥_{2}) e_{M} ∥ D ∥_{2} .$ This additional residual is necessary for actual rounded output factors; the trailing-only residual applies to conceptual exact multipliers.

Facts & Assumptions

Given: The stated successful kernel, its finite pivot certificates and no-underflow operations; $0 < u < 1$ . For a matrix $X = (x_{i j})$ , the Frobenius norm is $∥ X ∥_{F} = (\sum_{i, j} ∣ x_{i j} ∣^{2})^{1 / 2}$ . Norms in a certificate are exact or rigorously bounded.

[F1]

Certified real-component Hermitian one-by-one and two-by-two LDL* kernels fixes real-component divisions, determinant order, threshold certificates and Hermitian storage.

[F2]

The proof, Step 2.1, of Rounded matrix products give certified linear and normal-equation residual allowances bounds a successful complex length- $j$ dot by $g_{j}$ times its absolute-product sum, including exact zeros, when $(j - 1) u < 1$ . Apply that rowwise proof to each dot here; for $j \in {1, 2}$ its condition follows from $0 < u < 1$ regardless of $t$ .

[F3]

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv|| supplies the induced Euclidean norm; Cauchy-Schwarz gives submultiplicativity and $∥ X ∥_{2} \leq ∥ X ∥_{F}$ .

Proof

1.1givenF1algebra

For two-by-two $D$ , put $E = D / s$ and $J = adj (E)$ . Each real component of $E$ has magnitude at most one. Expansion of the determinant computation multiplies each of its three quadratic terms by at most five factors $1 + δ_{i}$ , $∣ δ_{i} ∣ \leq u$ , including scaling. For $0 < u < 1$ , the coefficient deviation is at most $(1 + u)^{5} - 1$ , since the lower deviation $1 - (1 - u)^{5}$ is no greater. Also $∣ E_{11} E_{22} ∣ + (Re E_{12})^{2} + (Im E_{12})^{2} \leq 3$ . Thus $∣ \hat{d} - \det E ∣ \leq ϵ_{d}$ . Acceptance gives $\det E \neq 0$ . The entrywise scaling bound $∣ J - \hat{J} ∣ \leq u ∣ J ∣$ implies $∣ J ∣ \leq ∣ \hat{J} ∣ / (1 - u)$ and $∣ J ∣ \geq ∣ \hat{J} ∣ / (1 + u)$ . The algorithm's $U, V$ therefore bound $∣ D^{- 1} ∣$ above and below. The modulus guard follows by expanding its scaled sum, square root and rescaling, giving relative factors between $(1 - u)^{4}$ and $(1 + u)^{4}$ . The resulting maximum/product interval tests prove exact acceptance or definite threshold failure; unresolved cases are explicitly inconclusive. Scalar pivots satisfy the same scalar threshold argument.

2.1F3step 1.1algebra

Define $R = \hat{J} / (s \hat{d})$ for analysis only. Scaling gives $∥ \hat{J} - J ∥_{F} \leq u ∥ J ∥_{F} \leq \sqrt{2} u ∥ J ∥_{2}$ . The inverse formula gives $∥ D^{- 1} ∥_{2} = ∥ J ∥_{2} / (s ∣ \det E ∣)$ , and step 1.1 gives $∣ \det E ∣ / ∣ \hat{d} ∣ \leq 1 + μ$ . Subtract the two inverse expressions to obtain $∥ R - D^{- 1} ∥_{2} \leq ν ∥ D^{- 1} ∥_{2}$ and $∥ R ∥_{2} \leq (1 + ν) ∥ D^{- 1} ∥_{2}$ . This retains the actual scaled-determinant sensitivity.

3.1F1F2F3step 2.1algebra

The computed $B / s$ has Frobenius error at most $u ∥ B ∥_{F} / s$ . By [F2], its product with $\hat{J}$ adds at most $g_{2} (1 + u) ∥ B ∥_{F} ∥ \hat{J} ∥_{F} / s$ . Since $∥ \hat{J} ∥_{F} \leq \sqrt{2} ∥ \hat{J} ∥_{2}$ , the product discrepancy relative to $B \hat{J} / s$ is at most $(\sqrt{2} g_{2} (1 + u) + u) ∥ B ∥_{F} ∥ \hat{J} ∥_{2} / s$ . Final real-component division adds the factor $1 + u$ to that error and at most $u ∥ B R ∥_{F}$ . Thus $∥ \hat{M} - B R ∥_{F} \leq χ ∥ B ∥_{F} ∥ R ∥_{2}$ . Step 2.1 proves the stated $e_{M}$ and $∥ \hat{M} ∥_{F} \leq (1 + ω_{2}) ∥ B ∥_{F} ∥ D^{- 1} ∥_{2}$ . For a scalar pivot the direct real-component divisions instead give these bounds with $ω_{1} = u$ .

4.1F1F2F3step 3.1algebra

The update dot bound [F2] gives $∥ \hat{Z} - \hat{M} B^{*} ∥_{F} \leq g_{k} ∥ \hat{M} ∥_{F} ∥ B ∥_{F}$ . Replacing $\hat{M}$ by $M$ adds at most $e_{M} ∥ B ∥_{2}$ . Final subtraction adds at most $u (∥ C ∥_{F} + ∥ \hat{Z} ∥_{F})$ . Combining these with step 3.1 gives raw Schur error at most $u ∥ C ∥_{F} + q_{k} ∥ B ∥_{F}^{2} ∥ D^{- 1} ∥_{2}$ . The exact Schur complement is Hermitian. Copying one chosen computed triangle doubles at most the squared Frobenius error; projecting the diagonal to its real part decreases error. Thus $∥ Δ ∥_{2} \leq β$ . Finally $∥ C ∥_{F} \leq \sqrt{t} ∥ C ∥_{2}$ and $∥ B ∥_{F}^{2} \leq k ∥ B ∥_{2}^{2}$ , proving the stated $η_{k, t}$ bound. Empty trailing arrays have zero residual.

5.1F3step 3.1step 4.1algebra∎

Put $H = \hat{M} - M$ . Direct block multiplication gives the displayed full residual, because $N = H D$ and $\hat{M} D {\hat{M}}^{*} - M B^{*} = H B^{*} + \hat{M} N^{*}$ . The Hermitian off-diagonal matrix $(\begin{array}{cc} 0 & N^{*} \\ N & 0 \end{array})$ has norm $∥ N ∥_{2}$ : its square is block diagonal with $N^{*} N, N N^{*}$ , or equivalently use the defining singular-value maximum. Also $∥ N ∥_{2} \leq e_{M} ∥ D ∥_{2}$ . Triangle inequality and step 4.1 therefore give $∥ F ∥_{2} \leq f$ . Every coefficient is an explicit finite function under successful certification, and tends to zero linearly for a fixed nonsingular normalized pivot as $u \to 0$ .

Depends on

Used by

Block LDL* residual errors propagate with actual block growth Theorem

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jennifer Scott and Miroslav Tůma, Algorithms for Sparse Linear Systems, Chapter 7, §§7.2.4 and 7.3 (standard reference, not scraped)
Timothy A. Davis, Siva Rajamanickam, and Wissam M. Sid-Lakhdar, A survey of direct methods for sparse linear systems, §11 (standard reference, not scraped)