Pipeline-generated

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.

✓ 5 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 3 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Sparse direct elimination and ordering

1 · Prerequisites

2 · Summary

This page builds on the structural graph, ordering, filled graph, and elimination-forest interfaces owned by the sparse-matrix-models-and-kernel-costs page. It defines the Cholesky column patterns and elimination-tree reach needed locally, proves the path characterization used to confine nested-dissection fronts, and derives work and factor-storage bounds for the two- and three-dimensional nearest-neighbor grids. The stated grid bounds do not extend to arbitrary graphs.

Threshold LU and symmetric-indefinite block LDL* carry explicit pivot, fill, and failure rules. The real threshold-LU residual bound retains the actual active-matrix growth. The block LDL* result retains its general conditional local-update statement and now instantiates it with a proved complex real-component kernel, actual amplification and block inverse norms. No universal small-growth guarantee is asserted.

The Hermitian block LDL* branch includes a certified one-by-one/two-by-two real-component kernel, explicit normalized-determinant conditioning and pivot-inconclusive status, and proved local unit-roundoff bounds. Actual stored factors use the complete reconstruction residual, including multiplier coupling errors, with their actual transformation growth. The exact-multiplier conditional bound remains available separately.

3 · Logical flowchart

4 · Definitions, theorems and proofs

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableprecheck pendingOpen item page →

Threshold partial-pivot sparse LU with explicit fill and failure statuses

Definition

Input a nonsingular real matrix $A \in R^{n \times n}$ with $n \geq 1$ , an initial simultaneous row-and-column permutation matrix $P$ under the row-action convention of Permutation matrices, partial pivoting, and the pivot-growth factor, and a threshold $θ \in (0, 1]$ . Choose the exact-arithmetic branch or the finite-precision branch. In the latter, additionally supply a format from Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add; the entries of $A$ must already be stored values in that format, with no input conversion. The exact-arithmetic branch permits arbitrary real entries and evaluates every scalar operation exactly, without finite-format range restrictions. Initialize the active matrix $S^{(0)} = P A P^{T}$ by permuted copies, the accumulated row permutation $Q = I_{n}$ , the unit lower-triangular factor $L = I_{n}$ , and the upper-triangular factor $U = 0$ . Treat an unstored active entry as zero. In finite precision every real scalar operation uses the supplied model; if an exact intermediate is nonzero and subnormal, overflows, or the operation reports range failure, return range-failure with its stage. Pivot tests and tie-breaking comparisons are exact guards on current values. For $k = 0, \dots, n - 1$ , ties for a maximum are resolved by choosing the smallest current row index.

At stage $k$ , let $m_{k} = \max_{i \geq k} ∣ S_{i k}^{(k)} ∣$ . If $m_{k} = 0$ , return singular-pivot $(k)$ . If $∣ S_{k k}^{(k)} ∣ \geq θ m_{k}$ , select row $p = k$ ; otherwise select the smallest row attaining $m_{k}$ . If $p \neq k$ , swap rows $p$ and $k$ of the active matrix and the already stored entries in columns $0, \dots, k - 1$ of those rows of $L$ . Also replace $Q$ by $E_{k p} Q$ , where $E_{k p}$ is the permutation matrix swapping rows $k$ and $p$ . Do not change the previously stored rows of $U$ . If the selected pivot is zero, return singular-pivot $(k)$ .

Save the active pivot row by setting $U_{k j} = S_{k j}^{(k)}$ for every $j \geq k$ ; entries $U_{k j}$ with $j < k$ remain zero. Set $L_{i k} = S_{i k}^{(k)} / S_{k k}^{(k)}$ for every $i > k$ , interpreting a missing $S_{i k}^{(k)}$ as zero. For every $i, j > k$ , update $S_{i j}^{(k + 1)} = S_{i j}^{(k)} - L_{i k} U_{k j} .$ In a sparse representation it suffices to visit positions where $S_{i j}^{(k)} \neq 0$ or $L_{i k} U_{k j} \neq 0$ ; missing entries in this formula are zero. Allocate any position whose rounded update is nonzero; this is numerical fill. If an arithmetic operation is not representable or reports a range error, return range-failure with its stage. Any failure return is a status only and asserts no factorization. On success return $(Q, P, L, U)$ . In exact arithmetic the updates give $Q P A P^{T} = L U$ ; the procedure makes no claim of a universal fill or growth bound.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Undirected structural graph of a Hermitian matrix

Definition

Let $A \in C^{n \times n}$ satisfy $A = A^{*}$ , where $A^{*} = {\overline{A}}^{T}$ . Define a real symmetric pattern matrix $H \in {0, 1}^{n \times n}$ by $H_{i i} = 0$ and, for $i < j$ , set $H_{i j} = H_{j i} = 1$ exactly when $A_{i j} \neq 0$ ; otherwise set both entries to zero. Since $A_{j i} = \overline{A_{i j}}$ , this pattern records exactly the undirected off-diagonal support of $A$ .

Apply the graph and elimination-ordering convention of Structural graphs and ordered symmetric elimination to $H$ . Its structural graph is the Hermitian structural graph of $A$ , and its filled graphs are the symbolic pattern used for Hermitian elimination. The real matrix $H$ records only support; numerical Schur complements are formed from $A$ .

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableprecheck pendingjudge pass (gpt-6-luna)Open item page →

Recursive coordinate-separator ordering for two- and three-dimensional grids

Definition

Input an integer $k \geq 1$ and dimension $d \in {2, 3}$ . The coordinate vertices are ${0, \dots, k - 1}^{d}$ . Identify them with the zero-based matrix indices $0, \dots, k^{d} - 1$ by the lexicographic bijection $q (i_{1}, \dots, i_{d}) = \sum_{a = 1}^{d} i_{a} k^{d - a}$ . The grid graph has an edge between two coordinate vertices exactly when they differ by $1$ in one coordinate and agree in all others. Use the graph and ordering conventions of Structural graphs and ordered symmetric elimination on these indices. Thus $d = 2$ gives the five-point graph and $d = 3$ the seven-point graph.

Order a rectangular coordinate subbox recursively as follows. For each coordinate whose side length is at least $2$ , choose its lower median coordinate, namely the coordinate with $⌊ (m - 1) / 2 ⌋$ positions below it in a side of length $m$ . Let $S$ be the union of the coordinate hyperplanes at those selected medians. Delete $S$ , obtaining at most $2^{d}$ nonempty rectangular child boxes. Recursively order the child boxes in lexicographic order of their lower corners, then append the vertices of $S$ in lexicographic order. If no coordinate has side length at least $2$ , append the remaining vertex as a terminal separator. Apply this rule first to the whole grid. The resulting order is the coordinate nested-dissection ordering.

The recursion uses only the graph geometry. It makes no fill or complexity claim for arbitrary graphs.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Filled edges are witnessed by paths through earlier eliminated vertices

Statement

Use the zero-based graph and ordering of Structural graphs and ordered symmetric elimination. For distinct remaining vertices $x, y \in V_{k}$ , the pair ${x, y}$ is an edge of $G_{k}$ if and only if the original graph $G_{0}$ contains a finite walk from $x$ to $y$ all of whose internal vertices belong to ${v_{0}, \dots, v_{k - 1}}$ . A walk may repeat vertices; its internal vertices are the entries other than its two endpoints.

Facts & Assumptions

Given: A finite simple graph, an elimination ordering, and the filled graphs defined by the supplier.

[F1]

Structural graphs and ordered symmetric elimination: At step $k$ , delete $v_{k}$ , retain edges between remaining vertices, and add every pair of distinct later neighbors of $v_{k}$ .

Proof

1.1givenF1basealgebra

At $k = 0$ , a walk with no internal vertices consists of one edge, so the claimed equivalence is exactly the definition of $G_{0}$ .

1.2F1IHinductionalgebra

Suppose the equivalence holds at stage $k$ . A retained edge in $G_{k + 1}$ already has a witnessing walk whose internal vertices are among $v_{0}, \dots, v_{k - 1}$ . An edge newly added at step $k$ joins two vertices $x, y$ that are each adjacent to $v_{k}$ in $G_{k}$ . The induction hypothesis gives walks from $x$ to $v_{k}$ and from $v_{k}$ to $y$ with internal vertices among $v_{0}, \dots, v_{k - 1}$ ; concatenating them gives the required walk with the additional internal vertex $v_{k}$ . This proves the forward implication at stage $k + 1$ .

2.1F1IHstep 1.2inductionalgebra

Conversely, let a witnessing walk from $x$ to $y$ have internal vertices among $v_{0}, \dots, v_{k}$ . If it has no internal occurrence of $v_{k}$ , the induction hypothesis gives an edge in $G_{k}$ , which is retained. Otherwise take the first and last internal occurrences of $v_{k}$ . The initial subwalk from $x$ to the first occurrence and the terminal subwalk from the last occurrence to $y$ have all internal vertices among $v_{0}, \dots, v_{k - 1}$ . By induction, $x$ and $y$ are both later neighbors of $v_{k}$ in $G_{k}$ . Since $x \neq y$ , the update inserts ${x, y}$ in $G_{k + 1}$ .

3.1step 1.1step 1.2step 2.1discharge-induction∎

The base case and steps 1.2 and 2.1 prove both implications for every stage by induction on $k$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Real threshold sparse LU has a backward residual bound with actual growth

Statement

Let $A \in R^{n \times n}$ be nonsingular, $n \geq 1$ , and run Threshold partial-pivot sparse LU with explicit fill and failure statuses with $θ \in (0, 1]$ . Assume a successful run under the real operation model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add, with unit roundoff $u < 1$ and every exact intermediate either zero or normal. Let $M = \max_{i, j} ∣ a_{i j} ∣ > 0$ , let $S^{(k)}$ be the active matrix at stage $k$ including its current pivot row, and define the actual growth of this run by

ρ = \frac{\max_{k, i, j} ∣ S_{i j}^{(k)} ∣}{M} \geq 1.

For its computed factors and accumulated row permutation, there is a residual $Δ A$ such that $\hat{Q} P A P^{T} + Δ A = \hat{L} \hat{U}, \max_{i, j} ∣ Δ A_{i j} ∣ \leq \frac{8 n u}{θ} ρ M, ∥ Δ A ∥_{\infty} \leq \frac{8 n^{2} u}{θ} ρ M, ∥ X ∥_{\infty} : = \max_{i} \sum_{j} ∣ X_{i j} ∣ .$ The bound retains this run's actual growth $ρ$ and makes no uniform small-growth claim. This residual theorem is for real arithmetic; the local operation model used here does not specify a general complex division primitive.

Facts & Assumptions

Given: A successful real threshold-pivoted elimination run, the stated real relative operation model, and the no-range-failure hypothesis.

[F1]

Threshold partial-pivot sparse LU with explicit fill and failure statuses: At stage $k$ , use the diagonal only if its modulus is at least $θ$ times the active column maximum; otherwise swap a maximum-modulus row into the pivot position. The algorithm swaps previously stored entries of the same rows of $L$ and updates each active entry by one product and one subtraction.

[F2]

Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add: Each real add, subtract, multiply, or divide is one rounded operation; on a successful in-range real operation, the computed result is the exact result times $1 + δ$ with $∣ δ ∣ \leq u$ , and exact zero is returned exactly.

Proof

1.1givenF1F2algebra

The initial active matrix is $P A P^{T}$ , whose entrywise maximum is $M$ because $P$ only permutes rows and columns; hence $ρ \geq 1$ . Let $c = S_{i k}^{(k)}$ and $p = S_{k k}^{(k)}$ at a successful pivot. If the diagonal is accepted, [F1] gives $∣ c / p ∣ \leq θ^{- 1}$ . If a maximum-modulus entry is selected, $∣ c / p ∣ \leq 1 \leq θ^{- 1}$ . The rounded division therefore gives $∣ {\hat{l}}_{i k} ∣ \leq (1 + u) / θ \leq 2 / θ$ . Also every pivot-row entry and every active entry has modulus at most $ρ M$ .

2.1step 1.1F1F2algebra

For a trailing update, write $p_{i j} = fl ({\hat{l}}_{i k} {\hat{u}}_{k j})$ and $S_{i j}^{(k + 1)} = fl (S_{i j}^{(k)} - p_{i j})$ . Define $e_{i j k} = S_{i j}^{(k + 1)} - (S_{i j}^{(k)} - {\hat{l}}_{i k} {\hat{u}}_{k j})$ . By [F2], $∣ p_{i j} - {\hat{l}}_{i k} {\hat{u}}_{k j} ∣ \leq u ∣ {\hat{l}}_{i k} {\hat{u}}_{k j} ∣, ∣ S_{i j}^{(k + 1)} - (S_{i j}^{(k)} - p_{i j}) ∣ \leq u ∣ S_{i j}^{(k)} - p_{i j} ∣ .$ The triangle inequality and $∣ p_{i j} ∣ \leq (1 + u) ∣ {\hat{l}}_{i k} {\hat{u}}_{k j} ∣$ yield $∣ e_{i j k} ∣ \leq u ∣ S_{i j}^{(k)} ∣ + u (2 + u) ∣ {\hat{l}}_{i k} {\hat{u}}_{k j} ∣ \leq u ρ M (1 + \frac{(2 + u) (1 + u)}{θ}) \leq \frac{7 u ρ M}{θ},$ using $u < 1$ and $θ \leq 1$ .

2.2step 1.1F2algebra

For a computed multiplier, ${\hat{l}}_{i k} = fl (c / p)$ , so [F2] gives a division residual $e_{i k}^{d i v} : = c - {\hat{l}}_{i k} p$ with $∣ e_{i k}^{d i v} ∣ \leq u ∣ c ∣ \leq u ρ M$ .

3.1F1step 2.1step 2.2inductionalgebra

Track each active row together with its previously stored entries of $\hat{L}$ and its accumulated update residuals. Before stage $k$ , for every active row $i$ and active column $j \geq k$ , maintain $(Q_{k} P A P^{T})_{i j} = \sum_{r < k} {\hat{l}}_{i r} {\hat{u}}_{r j} + S_{i j}^{(k)} - \sum_{r < k} e_{i j r},$ where $Q_{k}$ is the row permutation accumulated so far. At $k = 0$ this is $S^{(0)} = P A P^{T}$ . Swapping two active rows also swaps their earlier $L$ entries and residual histories, so it preserves the invariant. After the pivot, ${\hat{u}}_{k j} = S_{k j}^{(k)}$ ; each lower-row update is $S_{i j}^{(k + 1)} = S_{i j}^{(k)} - {\hat{l}}_{i k} {\hat{u}}_{k j} + e_{i j k}$ , so substitution gives the same invariant at stage $k + 1$ . For the pivot column, $S_{i k}^{(k)} = {\hat{l}}_{i k} {\hat{u}}_{k k} + e_{i k}^{d i v}$ by definition of the division residual. Thus after all stages, for $i \leq j$ , $(\hat{Q} P A P^{T})_{i j} - (\hat{L} \hat{U})_{i j} = - \sum_{k < i} e_{i j k},$ and for $i > j$ , $(\hat{Q} P A P^{T})_{i j} - (\hat{L} \hat{U})_{i j} = e_{i j}^{d i v} - \sum_{k < j} e_{i j k} .$ These identities define $Δ A = \hat{L} \hat{U} - \hat{Q} P A P^{T}$ . Each entry contains at most $n$ update residuals and at most one division residual.

4.1step 2.1step 2.2step 3.1algebra

By steps 2.1–2.2, every residual entry is bounded by $n \frac{7 u ρ M}{θ} + u ρ M \leq \frac{8 n u}{θ} ρ M,$ since $n \geq 1$ and $θ \leq 1$ . Summing at most $n$ such bounds in any row gives $∥ Δ A ∥_{\infty} \leq 8 n^{2} u ρ M / θ$ .

5.1step 3.1step 4.1∎

The definition of $Δ A$ in step 3.1 gives the displayed nearby-factorization identity, and step 4.1 gives both residual bounds. The only growth quantity in the estimate is the maximum active-entry magnitude of this executed run.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Elimination-tree column patterns and reach

Definition

Let $A \in C^{n \times n}$ satisfy $A = A^{*}$ , use the Hermitian structural graph of Undirected structural graph of a Hermitian matrix, and fix an elimination ordering $π = (v_{0}, \dots, v_{n - 1})$ of its vertices. For this chosen ordering, construct the filled graphs, parent map, and elimination forest by Structural graphs and ordered symmetric elimination. All column sets, counts, ancestors, descendants, and reaches below are relative to $π$ . For each $k$ , let $N_{k} (v_{k})$ be the later-neighbor set at elimination of $v_{k}$ , and define its structural column set $C_{k} = {v_{k}} \cup N_{k} (v_{k}) .$ Its off-diagonal size is the column count $ℓ_{k} = ∣ N_{k} (v_{k}) ∣$ . An ancestor of $v_{k}$ is obtained by following one or more supplied parent edges; a descendant is the inverse relation. The reach of $v_{k}$ is the set of vertices visited by following its parent path, including $v_{k}$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Nested-dissection grid fronts are bounded by a box separator and its exterior boundary

Statement

Let $d \in {2, 3}$ and use the coordinate grid and recursive ordering of Recursive coordinate-separator ordering for two- and three-dimensional grids. For a recursion box $B$ , let $S_{B}$ be its median separator; for the terminal one-vertex box take $S_{B} = B$ . Let $\partial^{+} B$ be the set of grid vertices outside $B$ adjacent to some vertex of $B$ . If $v \in S_{B}$ , then every later filled neighbor of $v$ lies in $S_{B} \cup \partial^{+} B$ . If every side of $B$ has length at most $s$ , then

∣ {v} \cup N_{π}^{+} (v) ∣ \leq ∣ S_{B} ∣ + ∣ \partial^{+} B ∣ \leq 3 d s^{d - 1} .

Facts & Assumptions

Given: The finite nearest-neighbor grid, the recursive coordinate-separator order, and its symbolic elimination graph.

[F1]

Recursive coordinate-separator ordering for two- and three-dimensional grids: Each box orders all child boxes before its separator; the separator is the union of its selected coordinate hyperplanes, and removing it leaves the child boxes.

[F2]

Filled edges are witnessed by paths through earlier eliminated vertices: A filled edge at the elimination of $v$ is witnessed by an original grid walk whose internal vertices were eliminated before $v$ .

[F3]

Structural graphs and ordered symmetric elimination: The vertices of each filled graph are exactly those not yet eliminated, and the ordering position strictly increases from a vertex to any later neighbor.

Proof

1.1F1inductionalgebra

The root box has empty exterior boundary. If $B$ is a child of a box $C$ , every grid neighbor just outside $B$ is either in $S_{C}$ or just outside $C$ : distinct child boxes are separated by the removed coordinate hyperplanes. Thus $\partial^{+} B \subseteq S_{C} \cup \partial^{+} C$ . Induction up the finite recursion tree, using that each ancestor separator is ordered after all vertices in its child boxes by [F1], shows that every vertex of $\partial^{+} B$ is ordered after every vertex of $B$ .

2.1givenF1F2F3step 1.1algebra

Fix $v \in S_{B}$ and a later filled neighbor $w$ . If $w \in B$ , then $w$ cannot lie in a child box because every child is ordered before $S_{B}$ ; hence $w \in S_{B}$ . If $w \notin B$ , [F2] gives an original grid walk from $v$ to $w$ whose internal vertices were eliminated before $v$ . The first vertex of this walk outside $B$ lies in $\partial^{+} B$ and, by step 1.1, is ordered after $v$ . It therefore cannot be an internal vertex of the walk, so it must be its endpoint $w$ . Hence $w \in \partial^{+} B$ .

3.1step 2.1F1algebra

If the side lengths of $B$ are $m_{1}, \dots, m_{d} \leq s$ , each of its at most $d$ coordinate hyperplanes contains at most $s^{d - 1}$ vertices, so $∣ S_{B} ∣ \leq d s^{d - 1}$ . The exterior grid neighbors lie across the $2 d$ faces, each with at most $s^{d - 1}$ vertices, so $∣ \partial^{+} B ∣ \leq 2 d s^{d - 1}$ . The containment in step 2.1 therefore gives the stated column-size bound.

4.1step 2.1step 3.1∎

Steps 2.1 and 3.1 establish both the filled-neighbor containment and its numerical bound for every separator vertex, including the terminal one-vertex case.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Hermitian Schur-complement support stays inside the symmetric filled graph

Statement

Let $A \in C^{n \times n}$ be Hermitian and use the Hermitian structural graph adapter of Undirected structural graph of a Hermitian matrix. Fix an ordering and suppose each scalar pivot $p_{k} = S_{v_{k} v_{k}}^{k}$ is nonzero. Form the Hermitian Schur updates $S_{i j}^{k + 1} = S_{i j}^{k} - S_{i v_{k}}^{k} p_{k}^{- 1} S_{v_{k} j}^{k} .$ Then every $S^{k}$ is Hermitian, every nonzero off-diagonal entry of $S^{k}$ is an edge of the corresponding filled graph, and the later neighbors of every eliminated vertex form a clique in the next filled graph.

Facts & Assumptions

Given: A Hermitian matrix, an ordering, nonzero scalar pivots, and the displayed Schur update.

[F1]

Undirected structural graph of a Hermitian matrix: The undirected graph has edge ${i, j}$ exactly when the Hermitian matrix has a nonzero off-diagonal entry in that pair.

[F2]

Structural graphs and ordered symmetric elimination: At each step the graph deletes the pivot, retains all edges between remaining vertices, and adds every edge between distinct later neighbors of the pivot.

[F3]

A field has no zero divisors: $a b = 0 \Rightarrow a = 0$ or $b = 0$ : In a field, a nonzero product has every factor nonzero.

[F4]

$C = R [x] / (x^{2} + 1)$ is a field, every element is uniquely $a + b i$ , and every nonzero element has inverse $(a - b i) / (a^{2} + b^{2})$ : The complex numbers form a field containing $R$ ; for $a + b i \neq 0$ , $(a + b i)^{- 1} = (a - b i) / (a^{2} + b^{2})$ .

Proof

1.1givenF1F3F4baseIHalgebra

At stage $0$ , $S^{0} = A$ is Hermitian. If $S^{k}$ is Hermitian, then its diagonal pivot $p_{k}$ is real. Since it is nonzero, substituting $a = p_{k}, b = 0$ in [F4] gives $p_{k}^{- 1} = p_{k} / p_{k}^{2} = 1 / p_{k} \in R$ ; the denominator is nonzero by [F3]. For remaining $i, j$ , $\overline{S_{j i}^{k + 1}} = \overline{S_{j i}^{k} - S_{j v_{k}}^{k} p_{k}^{- 1} S_{v_{k} i}^{k}} = S_{i j}^{k} - S_{i v_{k}}^{k} p_{k}^{- 1} S_{v_{k} j}^{k} = S_{i j}^{k + 1} .$ Thus the update preserves Hermitian symmetry.

1.2givenF2algebra

By [F2], the graph update itself joins every pair of distinct later neighbors of $v_{k}$ . Thus each such later-neighbor set is a clique in the next filled graph.

2.1step 1.1F1F2F3F4baseIHinductionalgebra

Induct on the elimination stage for support. Initially every nonzero upper-triangular entry is an edge by [F1]. Suppose the inclusion holds at stage $k$ and $S_{i j}^{k + 1} \neq 0$ for $i < j$ . If $S_{i j}^{k} \neq 0$ , its edge is retained by [F2]. Otherwise the correction term is nonzero. Since $C$ is a field by [F4], applying [F3] to $(S_{i v_{k}}^{k} p_{k}^{- 1}) S_{v_{k} j}^{k}$ and then to $S_{i v_{k}}^{k} p_{k}^{- 1}$ shows that $S_{i v_{k}}^{k} \neq 0$ and $S_{v_{k} j}^{k} \neq 0$ . Hermitian symmetry from step 1.1 gives the undirected edges from $i$ to $v_{k}$ and from $v_{k}$ to $j$ in the active graph. Hence both vertices are later neighbors of $v_{k}$ , and [F2] inserts ${i, j}$ . This proves the support inclusion at stage $k + 1$ .

3.1step 1.1step 2.1step 1.2discharge-induction∎

The base case and step 2.1 prove the support inclusion at every stage; step 1.2 proves the clique property. The proof uses conjugate symmetry for Hermitian matrices and therefore supplies the complex-Hermitian extension beyond the real-symmetric supplier theorem.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

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

Definition

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 C^{n \times n}$ , an ordering $π = (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 $θ \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 = P A P^{*}$ , $L = I_{n}$ , and the block-diagonal output array $D_{b l k} = 0$ . Scalar complex absolute values mean exact complex moduli; $∣ (D_{r}^{- 1}) ∣$ 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 = (\begin{array}{cc} D_{r} & B_{r}^{*} \\ B_{r} & C_{r} \end{array}),$ 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_{t t} \neq 0$ and $\max_{i \in R_{r}} ∣ S_{i t} ∣ \leq θ^{- 1} ∣ d_{r} ∣ .$ For a $2 \times 2$ block $J_{r} = {s, t}$ , $D_{r} = S_{J_{r}, J_{r}}$ is the Hermitian principal block $D_{r} = (\begin{array}{cc} S_{s s} & S_{s t} \\ \overline{S_{s t}} & S_{t t} \end{array}) .$ Require $\det D_{r} \neq 0$ , and let $c_{1} = \max_{i \in R_{r}} ∣ (B_{r})_{i 1} ∣$ and $c_{2} = \max_{i \in R_{r}} ∣ (B_{r})_{i 2} ∣$ , with an empty maximum equal to zero. Accept the pair only if $(∣ (D_{r}^{- 1})_{i j} ∣)_{i, j = 1}^{2} (\begin{array}{c} c_{1} \\ c_{2} \end{array}) \leq θ^{- 1} (\begin{array}{c} 1 \\ 1 \end{array})$ 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_{b l 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}^{*}$ . 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_{b l 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 = P A P^{*}$ , $\hat{L} = I_{n}$ , and $D_{b l 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 $θ$ , 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_{b l k}$ , store ${\hat{M}}_{r}$ in the $R_{r} \times J_{r}$ block of $\hat{L}$ , and continue on its Hermitian ${\hat{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, \hat{L}, D_{b l 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.

Remarks

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_{b l k}$ with $P A P^{*} = L D_{b l k} L^{*}$ , 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.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Every later filled neighbor lies on the elimination-tree parent path

Statement

Let $v_{k}$ be a vertex in the elimination forest supplied by Elimination-tree column patterns and reach. Every later filled neighbor of $v_{k}$ lies on its parent path and is therefore an ancestor. Consequently, if $v_{s}$ is a child of $v_{k}$ , then every later neighbor of $v_{s}$ other than $v_{k}$ is a later neighbor of $v_{k}$ ; equivalently, $C_{s} ∖ {v_{s}} \subseteq C_{k} .$

Facts & Assumptions

Given: The zero-based ordered vertices, filled graphs, and parent forest from batch-2's graph definition.

[F1]

Elimination-tree column patterns and reach: $C_{k} = {v_{k}} \cup N_{k} (v_{k})$ , and reach follows the supplied parent path.

[F2]

Structural graphs and ordered symmetric elimination: The parent is the later neighbor with least position greater than the child's position.

[F3]

Structural graphs and ordered symmetric elimination: The graph update adds every edge between two distinct vertices in the pivot's later-neighbor set.

Proof

1.1givenF2F3choose

Fix $v_{k}$ and a later filled neighbor $v_{t}$ . If $v_{t}$ is the parent, it is an ancestor by definition. Otherwise let $v_{s}$ be the parent. By [F2], $k < s < t$ . Since $v_{s}$ and $v_{t}$ are both later neighbors of $v_{k}$ , [F3] inserts ${v_{s}, v_{t}}$ when $v_{k}$ is eliminated. Thus $v_{t}$ remains a later neighbor of $v_{s}$ .

1.2F1F2F3algebra

Now let $v_{s}$ be a child of $v_{k}$ . Every later neighbor $v_{t}$ of $v_{s}$ is either $v_{k}$ or is later than $v_{k}$ . In the latter case both $v_{k}$ and $v_{t}$ are later neighbors of $v_{s}$ , so [F3] joins them in the filled graph. Thus every element of $C_{s} ∖ {v_{s}}$ belongs to $C_{k}$ .

2.1step 1.1F2inductionalgebra

If $v_{t}$ is not the parent of $v_{s}$ , replace $v_{k}$ by $v_{s}$ and repeat. At each repetition the ordering position strictly increases and is at most $t$ , because the current vertex remains adjacent to $v_{t}$ and its parent is the earliest later neighbor. The finite increasing sequence must reach position $t$ ; it cannot stop earlier at a root while still having later neighbor $v_{t}$ . Hence $v_{t}$ lies on the parent path from $v_{k}$ and is an ancestor.

3.1step 2.1step 1.2∎

Step 2.1 proves the ancestor assertion, and step 1.2 gives the child-column containment used to assemble fronts.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableprecheck pendingjudge pass (gpt-6-luna)Open item page →

Ordered sparse Cholesky with explicit pivot and range statuses

Definition

Input a Hermitian positive-definite $A \in C^{n \times n}$ in the convention of Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal, its Hermitian structural graph from Undirected structural graph of a Hermitian matrix, and an ordering $π = (v_{0}, \dots, v_{n - 1})$ . Use the operation model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add. Let $P$ be the permutation matrix whose row $j$ is row $v_{j}$ of $I_{n}$ , so the ordered matrix is $B = P A P^{*}$ and $B_{i j} = A_{v_{i} v_{j}}$ . Relabel the filled graph on the original vertices by positions: ${i, j} \in E_{π}^{+}$ exactly when ${v_{i}, v_{j}}$ is an edge of the filled graph. In every displayed sum, accumulate in increasing $k$ from left to right.

Preallocate only the diagonal and lower-triangular positions permitted by $E_{π}^{+}$ . The support guarantee for complex Hermitian Schur complements is proved in Hermitian Schur-complement support stays inside the symmetric filled graph. Initialize those positions from the lower triangle of $B$ , using zero where a position is not present in the original pattern. For $j = 0, \dots, n - 1$ , perform these instructions:

Compute $d_{j} = B_{j j} - \sum_{k < j} l_{j k} \overline{l_{j k}}$ using only already computed entries, with an empty sum equal to zero. If an operation reports range failure, return range-failure $(j)$ . If $d_{j}$ is not a finite positive real number, return invalid-pivot $(j, d_{j})$ .
Set $l_{j j} = \sqrt{d_{j}}$ . If the square root is not finite and positive, return range-failure $(j)$ .
For each $i > j$ such that ${i, j} \in E_{π}^{+}$ , compute $l_{i j} = \frac{B_{i j} - \sum_{k < j} l_{i k} \overline{l_{j k}}}{l_{j j}} .$ If an operation reports range failure, return range-failure $(j)$ . Set structurally absent entries to zero.

If all columns finish, return success $(P, L)$ . In exact arithmetic, the intended factor convention is $P A P^{*} = L L^{*}$ with $L$ lower triangular and positive real diagonal. The finite-arithmetic procedure makes no claim that every positive-definite input returns success: a rounded pivot can fail the stated test.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Block LDL* residual errors propagate with actual block growth

Statement

Consider a successful run of Sparse symmetric-indefinite block LDL* with threshold tests and failure status on a Hermitian input with its declared permutation $P$ and fixed pivot-block sequence. In every formula, $∥ X ∥_{2}$ is the operator norm induced by the Euclidean inner products. At stage $r$ , write the active matrix as $(\begin{array}{cc} D_{r} & B_{r}^{*} \\ B_{r} & C_{r} \end{array}) .$ Suppose the computed trailing block is ${\hat{S}}_{r + 1} = C_{r} - B_{r} D_{r}^{- 1} B_{r}^{*} + Δ_{r},$ where $Δ_{r}$ is the exact local update residual. Embed it into the full permuted coordinates as $E_{r}$ , with zeros on all previously eliminated and current pivot indices. Let $T_{r}$ be the $n \times n$ identity on previously eliminated coordinates and the padded unit lower block elimination matrix $(\begin{array}{cc} I & 0 \\ B_{r} D_{r}^{- 1} & I \end{array})$ on the current pivot and trailing coordinates. Set $W_{1} = I$ and $W_{r} = T_{1} \dots T_{r - 1}$ for $r > 1$ . Then $∥ P A P^{*} - L_{e x} D_{b l k} L_{e x}^{*} ∥_{2} \leq \sum_{r} ∥ W_{r} ∥_{2}^{2} ∥ Δ_{r} ∥_{2} \leq ρ_{b l k} \sum_{r} η_{r} (∥ C_{r} ∥_{2} + ∥ B_{r} ∥_{2}^{2} ∥ D_{r}^{- 1} ∥_{2}),$ provided the actual local residuals satisfy $∥ Δ_{r} ∥_{2} \leq η_{r} (∥ C_{r} ∥_{2} + ∥ B_{r} ∥_{2}^{2} ∥ D_{r}^{- 1} ∥_{2}) .$ Here $L_{e x}$ is the product of the exact-multiplier transformations $T_{r}$ , not a rounded stored multiplier factor. For a nonempty run, $ρ_{b l k} : = \max_{r} ∥ W_{r} ∥_{2}^{2}$ is the actual amplification from this pivot sequence. For an empty pivot partition set $ρ_{b l k} = 0$ ; all stage sums are then zero. The trailing-only statement is conditional in this general form. For the specified kernel, Hermitian block LDL* kernels have explicit roundoff and actual-factor residual bounds proves it with $η_{r} = η_{k_{r}, t_{r}}$ , retaining the actual normalized-determinant and range certificates. It makes no uniform smallness claim for $ρ_{b l k}$ , $∥ D_{r}^{- 1} ∥_{2}$ , or $η_{r}$ .

In exact arithmetic every accepted block is nonsingular and each update has $Δ_{r} = 0$ , so a successful run returns $P A P^{*} = L D_{b l k} L^{*}$ .

For the actual rounded output, let ${\hat{T}}_{r}$ be the $n \times n$ transformation built from stored ${\hat{M}}_{r}$ , padded by the identity on previously eliminated coordinates. Let $F_{r, a c t}$ be the $(k_{r} + t_{r}) \times (k_{r} + t_{r})$ reconstruction residual from the local kernel lemma, and define $F_{r}$ by embedding $F_{r, a c t}$ into the current pivot and trailing coordinates, with zero rows and columns on all previously eliminated indices. Set ${\hat{W}}_{1} = I_{n}$ and ${\hat{W}}_{r} = {\hat{T}}_{1} \dots {\hat{T}}_{r - 1}$ . Then $P A P^{*} - \hat{L} D_{b l k} {\hat{L}}^{*} = \sum_{r} {\hat{W}}_{r} F_{r} {\hat{W}}_{r}^{*}, ∥ P A P^{*} - \hat{L} D_{b l k} {\hat{L}}^{*} ∥_{2} \leq \sum_{r} ∥ {\hat{W}}_{r} ∥_{2}^{2} f_{r} \leq {\hat{ρ}}_{b l k} \sum_{r} f_{r},$ where $f_{r}$ is the proved explicit local bound. For a nonempty run set ${\hat{ρ}}_{b l k} = \max_{r} ∥ {\hat{W}}_{r} ∥_{2}^{2}$ , and for an empty pivot partition set ${\hat{ρ}}_{b l k} = 0$ . This includes multiplier coupling residuals as well as trailing updates. Neither actual growth nor inverse-pivot conditioning is assumed uniformly small.

Facts & Assumptions

Given: A successful sequence of Hermitian $1 \times 1$ or $2 \times 2$ pivots, the actual local update residuals $Δ_{r}$ , and the displayed local error bounds.

[F1]

Sparse symmetric-indefinite block LDL* with threshold tests and failure status: The declared permutation is applied once; each accepted pivot block is Hermitian and nonsingular, and the exact trailing update is $C - B D^{- 1} B^{*}$ .

[F2]

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: For a linear map between finite-dimensional inner-product spaces, the operator norm is the maximum of $∥ T v ∥$ over unit vectors (and is zero on the zero domain).

[A1]

For each stage $r$ , the computed trailing block is $C_{r} - B_{r} D_{r}^{- 1} B_{r}^{*} + Δ_{r}$ and $∥ Δ_{r} ∥_{2} \leq η_{r} (∥ C_{r} ∥_{2} + ∥ B_{r} ∥_{2}^{2} ∥ D_{r}^{- 1} ∥_{2})$ .

[F3]

Hermitian block LDL* kernels have explicit roundoff and actual-factor residual bounds proves the concrete local trailing residual, exact pivot acceptance, and full stored-multiplier reconstruction residual.

Proof

1.1givenF1algebra

For each accepted block, $D_{r}$ is invertible by its pivot test. Direct block multiplication gives $(\begin{array}{cc} D_{r} & B_{r}^{*} \\ B_{r} & C_{r} \end{array}) = (\begin{array}{cc} I & 0 \\ B_{r} D_{r}^{- 1} & I \end{array}) (\begin{array}{cc} D_{r} & 0 \\ 0 & C_{r} - B_{r} D_{r}^{- 1} B_{r}^{*} \end{array}) (\begin{array}{cc} I & D_{r}^{- 1} B_{r}^{*} \\ 0 & I \end{array}),$ with the right-hand side an ordinary matrix product. Thus in exact arithmetic each elimination step is a valid Hermitian congruence. In the increasing-stage product $T_{1} \dots T_{r}$ , the earlier factors act as the identity on columns supported on the still-active coordinates, so multiplication by $T_{r}$ inserts precisely the stored multiplier columns for $J_{r}$ . The product is therefore the stored unit lower block-triangular $L$ , and completion gives $P A P^{*} = L D_{b l k} L^{*}$ with block-diagonal $D_{b l k}$ ; empty products give the empty identity.

1.2givenF1basealgebra

With a computed update, the middle trailing block differs by $Δ_{r}$ . Hence the reconstructed active matrix at stage $r$ differs from the block factorization with ${\hat{S}}_{r + 1}$ by the embedded matrix whose only nonzero block is $- Δ_{r}$ in the trailing coordinates.

2.1step 1.2F1IHinductionalgebra

Substitute the next-stage factorization into the trailing block of step 1.2. The local residual from stage $r + 1$ is conjugated by the padded stage- $r$ lower elimination transformation. Repeated substitution therefore yields $P A P^{*} - L_{e x} D_{b l k} L_{e x}^{*} = - \sum_{r} W_{r} E_{r} W_{r}^{*} .$ After one stage this is step 1.2. Replacing the next trailing block adds $- T_{1} E_{2} T_{1}^{*}$ ; each later substitution adds the next embedded residual conjugated by all preceding $T_{h}$ . Induction on the number of processed pivot blocks gives exactly $W_{r} = T_{1} \dots T_{r - 1}$ and the displayed identity.

3.1F2step 2.1algebra

For any compatible maps $X, Y$ , [F2] gives $∥ X Y v ∥_{2} \leq ∥ X ∥_{2} ∥ Y v ∥_{2} \leq ∥ X ∥_{2} ∥ Y ∥_{2} ∥ v ∥_{2}$ , so $∥ X Y ∥_{2} \leq ∥ X ∥_{2} ∥ Y ∥_{2}$ . If $E_{r}$ is the zero-padded trailing block $Δ_{r}$ , then $∥ E_{r} x ∥_{2} = ∥ Δ_{r} x_{t a i l} ∥_{2} \leq ∥ Δ_{r} ∥_{2} ∥ x_{t a i l} ∥_{2} \leq ∥ Δ_{r} ∥_{2} ∥ x ∥_{2}$ , hence $∥ E_{r} ∥_{2} \leq ∥ Δ_{r} ∥_{2}$ . Also $∥ X^{*} ∥_{2} = ∥ X ∥_{2}$ : express the Euclidean norm as $\sup_{∥ v ∥ = 1} ∣ ⟨ v, w ⟩ ∣$ by Cauchy-Schwarz and take the two finite unit-vector suprema in either order. These inequalities and the triangle inequality bound each summand in step 2.1 by $∥ W_{r} ∥_{2}^{2} ∥ Δ_{r} ∥_{2}$ and give the first asserted bound.

4.1step 3.1A1discharge-inductionalgebra

Apply [A1] to each $Δ_{r}$ in step 3.1 and use $∥ W_{r} ∥_{2}^{2} \leq ρ_{b l k}$ . Summing gives the second bound. Since every $D_{r}$ is invertible but may be ill-conditioned and the transformation products may grow, no universal stability constant follows.

5.1F3step 3.1step 4.1algebra

For each accepted concrete kernel apply [F3]. Its $η_{k_{r}, t_{r}}$ supplies [A1], so steps 1.1, 1.2, 2.1, 3.1, and 4.1 give the claimed trailing-only estimate for the conceptual $L_{e x}$ . For actual stored multipliers, let ${\hat{T}}_{r, a c t}$ be the active block of ${\hat{T}}_{r}$ . Then [F3] gives the active identity $A_{r} = {\hat{T}}_{r, a c t} diag (D_{r}, {\hat{S}}_{r + 1}) {\hat{T}}_{r, a c t}^{*} + F_{r, a c t}$ , including the off-diagonal residual $N_{r} = {\hat{M}}_{r} D_{r} - B_{r}$ . Padding this identity uses $F_{r}$ as defined above; zero-padding preserves its operator norm, so $∥ F_{r} ∥_{2} = ∥ F_{r, a c t} ∥_{2} \leq f_{r}$ .

6.1F1F2F3step 3.1step 5.1inductiondischarge-inductionalgebra∎

Substitute the next active identity into the previous trailing block. After one stage the reconstruction residual is $F_{1}$ ; each additional stage adds its padded $F_{r}$ conjugated by all preceding stored-multiplier transformations. Induction gives $P A P^{*} - \hat{L} D_{b l k} {\hat{L}}^{*} = \sum_{r} {\hat{W}}_{r} F_{r} {\hat{W}}_{r}^{*}$ . The same submultiplicativity from step 3.1 and [F3] give the actual-growth bound. In exact arithmetic every local multiplier and Schur residual is zero, recovering the original exact factorization.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Ordered sparse Cholesky has the symbolic filled pattern when no cancellation occurs

Statement

Let $A \in C^{n \times n}$ be Hermitian positive definite and use its pattern from Undirected structural graph of a Hermitian matrix. The local Hermitian Schur-support lemma Hermitian Schur-complement support stays inside the symmetric filled graph applies. In exact arithmetic, the Cholesky recurrence in Ordered sparse Cholesky with explicit pivot and range statuses returns the unique factor $L$ satisfying $P A P^{*} = L L^{*}$ and positive diagonal, and every nonzero strict-lower entry of $L$ is permitted by the filled graph $G_{π}^{+}$ .

For $i > j$ with ${i, j} \in E_{π}^{+}$ (where ordered position $i$ represents original vertex $v_{i}$ ), define the recurrence numerator $ν_{i j} = B_{i j} - \sum_{k < j} l_{i k} \overline{l_{j k}}, B = P A P^{*} .$ If $ν_{i j} \neq 0$ at every permitted strict-lower position, then the numerical nonzero pattern of $L$ is exactly the lower-triangular part of $G_{π}^{+}$ together with its diagonal. Without this no-cancellation hypothesis only the upper-pattern inclusion is asserted.

Facts & Assumptions

Given: A Hermitian positive-definite matrix $A$ , the stated batch-2 graph/ordering interface, and its Schur-support hypothesis.

[F1]

Ordered sparse Cholesky with explicit pivot and range statuses: The permutation matrix has row $j$ equal to row $v_{j}$ of $I_{n}$ , and the exact algorithm uses $d_{j} = B_{j j} - \sum_{k < j} ∣ l_{j k} ∣^{2}$ , $l_{j j} = \sqrt{d_{j}}$ , and $l_{i j} = (B_{i j} - \sum_{k < j} l_{i k} \overline{l_{j k}}) / l_{j j}$ on filled positions.

[F2]

Hermitian Schur-complement support stays inside the symmetric filled graph: With nonzero scalar pivots, each Hermitian Schur complement is supported inside the Hermitian filled graph.

[F3]

A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: A Hermitian positive-definite matrix has a unique factorization $C = R R^{*}$ with $R$ lower triangular and positive real diagonal.

Proof

1.1givenF1F3algebra

A permutation preserves positive definiteness: for $x \neq 0$ , $P^{*} x \neq 0$ and $x^{*} B x = (P^{*} x)^{*} A (P^{*} x) > 0$ . Thus [F3] gives a unique exact Cholesky factor $R$ of $B$ .

2.1step 1.1F3algebra

Independently of the sparse algorithm, define dense active matrices on $a, b \geq j$ by $S_{a b}^{j} = B_{a b} - \sum_{k < j} r_{a k} \overline{r_{b k}}$ . Since $B = R R^{*}$ and $R$ is lower triangular, $S_{j j}^{j} = r_{j j}^{2} > 0$ and $S_{i j}^{j} = r_{i j} r_{j j}$ for $i > j$ . Subtracting $S_{a j}^{j} S_{j b}^{j} / S_{j j}^{j} = r_{a j} \overline{r_{b j}}$ gives $S_{a b}^{j + 1}$ . Thus these are precisely the dense Hermitian Schur updates starting from $S^{0} = B$ , with every pivot nonzero, without assuming anything about the sparse output.

3.1step 2.1F1F2algebra

Apply [F2] to the dense Schur sequence from step 2.1, using original vertex labels $v_{a}, v_{b}$ for ordered positions $a, b$ . If ${i, j} \notin E_{π}^{+}$ with $i > j$ , it is absent from the active filled graph at stage $j$ , so $S_{i j}^{j} = 0$ . As $S_{i j}^{j} = r_{i j} r_{j j}$ and $r_{j j} > 0$ , this forces $r_{i j} = 0$ . Hence the dense factor $R$ already has the required structural support, before it is compared with the sparse recurrence.

4.1step 2.1step 3.1F1baseIHinductionalgebra

Induct on the sparse column index $j$ , with no preceding columns at $j = 0$ . Assume $l_{i k} = r_{i k}$ for all $k < j$ . By step 2.1 the pivot recurrence in [F1] gives $d_{j} = S_{j j}^{j} = r_{j j}^{2} > 0$ and $l_{j j} = r_{j j}$ . On every permitted position its numerator is $S_{i j}^{j} = r_{i j} r_{j j}$ , so the computed $l_{i j}$ equals $r_{i j}$ . On an omitted position the algorithm sets $l_{i j} = 0$ , which equals $r_{i j}$ by step 3.1. This completes the induction, proving $L = R$ and success at every exact pivot.

5.1step 3.1step 4.1F1algebra

At each permitted strict-lower position, the recurrence gives $l_{i j} = ν_{i j} / l_{j j}$ and step 4.1 gives $l_{j j} > 0$ . Hence $ν_{i j} \neq 0$ implies $l_{i j} \neq 0$ . Under the stated no-cancellation condition every permitted position is nonzero; together with step 3.1 and $L = R$ this gives equality of patterns.

6.1step 3.1step 4.1step 5.1discharge-induction∎

Step 4.1 establishes that the exact algorithm returns the unique Cholesky factor; step 3.1 proves the structural upper pattern in the complex Hermitian case; step 5.1 proves equality under the no-cancellation hypothesis. No finite-precision success or stability claim follows from this exact-arithmetic theorem.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableprecheck pendingOpen item page →

Scalar multifrontal Cholesky and solves on the elimination forest

Definition

Input a Hermitian positive-definite matrix $A \in C^{n \times n}$ with $n \geq 1$ , its Hermitian structural graph from Undirected structural graph of a Hermitian matrix, and an ordering $π = (v_{0}, \dots, v_{n - 1})$ . Let $P$ be the permutation matrix whose row $r$ is row $v_{r}$ of $I_{n}$ , and put $B = P A P^{*}$ . Use the filled graph and parent forest of Structural graphs and ordered symmetric elimination and the column patterns of Elimination-tree column patterns and reach. For each original vertex $v_{r}$ , let its front index set be $F_{r} = {v_{r}} \cup N_{r}^{+},$ where $N_{r}^{+}$ is its later-neighbor set in the filled graph. Assign each nonzero off-diagonal matrix entry $A_{p q}$ and each diagonal entry $A_{p p}$ once to the front of the endpoint eliminated first (the diagonal goes to its own front); zero off-diagonal entries need no assignment. Treat front arrays as indexed by original-vertex labels, but store the factor in ordered coordinates of $B$ : for $v_{q} \in F_{r} ∖ {v_{r}}$ , its factor entry is $L_{q r}$ , where $q > r$ is the ordering position. Initialize $L$ to zero on ordered diagonal and lower-triangular positions, allocating every position permitted by the filled column pattern, including structural zeros. Use the operation model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add for all finite arithmetic, including contribution assembly and solves. A range failure during assembly, factorization or solving returns range-failure with the current position.

Traverse fronts in increasing pivot position $r$ (every child has smaller position than its parent). At front $r$ , initialize a zero dense Hermitian array $Φ_{r}$ indexed by $F_{r}$ and add the entries assigned to $v_{r}$ . Process the children in increasing pivot position $s$ ; for each child, add its stored contribution array to the entries whose indices lie in $F_{s} ∖ {v_{s}}$ , using the common original-vertex labels. The inclusion needed for this addition is supplied by Every later filled neighbor lies on the elimination-tree parent path. For the pivot $v_{r}$ , let $d = (Φ_{r})_{v_{r} v_{r}}$ . If it is not finite and positive, return invalid-pivot $(r, d)$ ; otherwise compute $l_{r r} = \sqrt{d}$ and, for each later position $q$ with $v_{q} \in F_{r}$ , compute $l_{q r} = (Φ_{r})_{v_{q} v_{r}} / l_{r r}$ in increasing $q$ . Apply Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add to each operation and return range-failure $(r)$ at the first range error. Store the computed diagonal and all entries $L_{q r}$ in the preallocated slots. For lower-triangular trailing positions with later positions $q \geq p > r$ and $v_{q}, v_{p} \in F_{r}$ , in increasing $(q, p)$ order, update $(Φ_{r})_{v_{q} v_{p}} \leftarrow fl ((Φ_{r})_{v_{q} v_{p}} - l_{q r} \overline{l_{p r}})$ ; set the Hermitian counterpart by conjugation and keep the diagonal real. Send the trailing contribution array to the parent; at a root discard only the empty final remainder. A failed pivot or range operation stops the factorization with its indexed status. These scalar steps have the same exact pivot and Schur update as Ordered sparse Cholesky with explicit pivot and range statuses.

After a successful factorization, input a right-hand side $b \in C^{n}$ and use these solve instructions:

Set $x = P b$ .
For $j = 0, \dots, n - 1$ , divide $x_{j}$ by $l_{j j}$ , then for every stored $l_{i j}$ with $i > j$ in increasing $i$ set $x_{i} \leftarrow x_{i} - l_{i j} x_{j}$ .
For $j = n - 1, \dots, 0$ , set $x_{j} \leftarrow (x_{j} - \sum_{i > j} \overline{l_{i j}} x_{i}) / \overline{l_{j j}}$ , accumulating the sum from left to right in increasing $i$ , using the backward-substitution convention of Forward and backward substitution for triangular linear systems.
Return $z = P^{*} x$ .

The factorization returns either $(P, L)$ or a pivot/range status. The solve returns the computed vector $z$ or range-failure with the current position. The solve arithmetic uses the declared finite-precision model; no exact-solution or finite-precision error guarantee is asserted here.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Scalar multifrontal elimination is equivalent to sparse Cholesky with column-count costs

Statement

Assume exact arithmetic, a Hermitian positive-definite $A$ , and a successful ordered factorization using Scalar multifrontal Cholesky and solves on the elimination forest. The fronts and contribution arrays give the same Cholesky factor as scalar elimination in ordering $π$ . With $d_{r} = ℓ_{r} + 1 = ∣ F_{r} ∣$ , the arithmetic work for assembly and scalar front updates is $O ⁣ (\sum_{r = 0}^{n - 1} d_{r}^{2}),$ the symbolic factor allocation has exactly $\sum_{r = 0}^{n - 1} d_{r}$ positions, and each forward/back substitution solve uses $O (\sum_{r} d_{r})$ scalar operations. These are arithmetic and factor-storage counts; they are not wall-clock or total workspace bounds.

Facts & Assumptions

Given: A Hermitian positive-definite matrix, an ordering, its filled graph and elimination forest, and exact-arithmetic multifrontal execution.

[F1]

Scalar multifrontal Cholesky and solves on the elimination forest: Each nonzero off-diagonal entry and each diagonal entry is assigned once to its earliest endpoint's front; each front adds child contribution arrays, eliminates its one pivot by a Schur update, and retains every permitted symbolic factor slot.

[F2]

Every later filled neighbor lies on the elimination-tree parent path: For a child $s$ of $r$ , $F_{s} ∖ {v_{s}} \subseteq F_{r}$ .

[F3]

Every later filled neighbor lies on the elimination-tree parent path: Every later filled neighbor of a vertex lies on its parent path, so vertices in distinct descendant branches cannot have a filled edge.

[F4]

Forward and backward substitution are correct, unique, and quadratic in scalar operations: Forward and backward substitution solve nonsingular triangular systems uniquely by the row recurrences stated in that theorem.

[F5]

A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: Every Hermitian positive-definite matrix has an exact Cholesky factor with positive diagonal, hence is nonsingular.

Proof

1.1givenF1F2F3baseinduction

For each vertex $v_{r}$ , let $T_{r}$ be its subtree in the elimination forest and let $X_{r} = F_{r} ∖ {v_{r}}$ . Define the local matrix for $T_{r}$ on $T_{r} \cup X_{r}$ to contain exactly the original entries assigned to fronts in $T_{r}$ ; its $X_{r} \times X_{r}$ block is zero, since entries wholly within $X_{r}$ are assigned to later fronts. If $u \in T_{r}$ and $w \notin T_{r} \cup X_{r}$ had an original edge, then either $w$ is earlier than $u$ , making $u$ a later filled neighbor and ancestor of $w$ , which would put $w$ in $T_{r}$ , or $w$ is later than $u$ , making $w$ a later filled neighbor and ancestor of $u$ . In the latter case, repeated application of the child-column containment in [F2] from $u$ up to $v_{r}$ puts $w$ in $F_{r}$ ; since $w \neq v_{r}$ and $w \notin T_{r}$ , it belongs to $X_{r}$ . Both cases contradict the choice of $w$ by [F2,F3]. The induction invariant is that the returned array is the Schur contribution on $X_{r}$ after eliminating $T_{r}$ from this local matrix. If $v_{r}$ is a leaf, every entry assigned to its front has at least one endpoint $v_{r}$ , so its initialized front is exactly this local matrix, with zero external-external block. The scalar update $C - b b^{*} / d$ therefore returns its Schur contribution.

2.1step 1.1F1F2F3F5IHinductionalgebra

Let $v_{r}$ have children $v_{s_{1}}, \dots, v_{s_{q}}$ . By [F2], each child interface $X_{s_{h}}$ lies in $F_{r}$ , so every extend-add is defined. By [F3], there is no original matrix coupling between interiors of distinct child subtrees: such an edge would make its later endpoint a filled neighbor outside the earlier endpoint's parent path. Form the local matrix on the union of those child interiors and $F_{r}$ , using only original entries assigned to these child subtrees or to $v_{r}$ and leaving entries wholly in $X_{r}$ zero. Its child-interior block is $D = diag (D_{1}, \dots, D_{q})$ , and its coupling to the current front is $B = [B_{1} \dots B_{q}]$ partitioned by child subtree. Each $D_{h} = A [T_{s_{h}}, T_{s_{h}}]$ is a principal submatrix of the positive-definite $A$ , so it is positive definite; [F5] gives a Cholesky factor with positive diagonal and therefore shows $D_{h}$ is nonsingular. Its Schur complement on the current front is $C - B D^{- 1} B^{*} = C - \sum_{h} B_{h} D_{h}^{- 1} B_{h}^{*}$ . The correction $- B D^{- 1} B^{*} = - \sum_{h} B_{h} D_{h}^{- 1} B_{h}^{*}$ is exactly the sum of child contributions by the induction invariant; adding them to the entries assigned to $v_{r}$ assembles this same local Schur complement. The pivot update $C - b b^{*} / d$ then eliminates $v_{r}$ and proves the invariant for $T_{r}$ .

3.1step 2.1F1algebra

The invariant at each root eliminates all vertices. Each pivot column is therefore computed from the same exact Schur complement as scalar elimination in $π$ , so the multifrontal factors equal the scalar Cholesky factors.

3.2step 1.1step 2.1F1F2algebra

Front $r$ has $d_{r} = ℓ_{r} + 1$ indices. Its dense scalar pivot update and initialization from assigned entries use at most a constant multiple of $d_{r}^{2}$ arithmetic operations. Embedding and adding a child contribution touches at most that child's dense trailing block, whose entries are already counted by the child's $d_{s}^{2}$ bound. Summing over fronts gives $O (\sum_{r} d_{r}^{2})$ arithmetic work. By [F1], each factor column retains one diagonal slot and all $ℓ_{r}$ later-neighbor slots, including structural zeros, so symbolic factor storage is exactly $\sum_{r} d_{r}$ .

4.1step 3.1F1F4algebra

The forward column updates in [F1] solve $L x = P b$ : after column $j$ is processed, row $j$ satisfies its equation, and the pivot contribution has been subtracted from each later row. This is the unique solution in [F4]. The descending conjugate updates solve $L^{*} y = x$ by the backward recurrence in [F4]. Since $P A P^{*} = L L^{*}$ , these equations imply $P A P^{*} y = P b$ ; multiplying by $P^{*}$ gives $A (P^{*} y) = b$ . Thus $P^{*} y$ is the unique solution of $A z = b$ .

5.1step 3.2step 4.1F1algebra

Each stored off-diagonal factor entry is visited once in each triangular solve, with one multiply and one subtraction; each diagonal contributes one division. Hence the two solves use $O (n + \sum_{r} ℓ_{r}) = O (\sum_{r} d_{r})$ operations, separate from the factorization work in step 3.2.

6.1step 3.1step 3.2step 4.1step 5.1discharge-induction∎

Step 3.1 gives scalar equivalence, step 3.2 gives factorization work and factor storage, and steps 4.1–5.1 give solve correctness and work.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Nested dissection gives the stated work and factor-storage bounds on regular grids

Statement

Let $d \in {2, 3}$ , $k \geq 2$ , and $n = k^{d}$ . Identify the coordinate grid ${0, \dots, k - 1}^{d}$ with the zero-based matrix indices by the lexicographic bijection in Recursive coordinate-separator ordering for two- and three-dimensional grids. Let $A \in R^{n \times n}$ be symmetric positive definite, with structural graph a subgraph of the $d$ -dimensional nearest-neighbor grid. Under the coordinate nested-dissection ordering, exact scalar multifrontal Cholesky has $\begin{array}{ccc} d & arithmetic work & symbolic factor storage \\ 2 & O (n^{3 / 2}) & O (n \log n) \\ 3 & O (n^{2}) & O (n^{4 / 3}) . \end{array}$ The storage is the number of allocated factor entries, including structural zeros, and excludes temporary contribution arrays. The bounds use the stated grid geometry; they assert no general-graph bound. For $k = 1$ , there is one pivot and both work and factor storage are $O (1)$ .

Facts & Assumptions

Given: A real symmetric positive-definite matrix with a grid-subgraph pattern, the recursive ordering, and exact scalar multifrontal Cholesky.

[F1]

Recursive coordinate-separator ordering for two- and three-dimensional grids: Every box is separated by the union of its selected median coordinate hyperplanes; child boxes are ordered before that separator.

[F2]

Nested-dissection grid fronts are bounded by a box separator and its exterior boundary: For the full grid and a vertex in the separator of a box of side at most $s$ , its factor-column size $d_{v} = ℓ_{v} + 1$ is at most $3 d s^{d - 1}$ .

[F3]

Filled edges are witnessed by paths through earlier eliminated vertices: A filled edge at the elimination of a vertex is equivalent to an original-graph walk between its endpoints whose internal vertices were eliminated earlier.

[F4]

Scalar multifrontal elimination is equivalent to sparse Cholesky with column-count costs: Exact factorization work is $O (\sum_{v} d_{v}^{2})$ and symbolic factor storage is exactly $\sum_{v} d_{v}$ .

Proof

1.1F1inductionalgebra

If a box side has length $m \geq 2$ , the median rule leaves each child side with length at most $⌈ m / 2 ⌉$ ; a side of length $1$ stays $1$ . Iterating gives side lengths at depth $r$ at most $s_{r} = ⌈ k / 2^{r} ⌉$ . There are at most $2^{d r}$ boxes at that depth because each box has at most $2^{d}$ children. By depth $R = ⌈ \log_{2} k ⌉$ , every side has length $1$ , so all remaining boxes are terminal. For $0 \leq r \leq R$ , $k / 2^{r} \geq 1 / 2$ , hence $s_{r} \leq 2 k / 2^{r}$ .

1.2givenF1F4algebra

If $k = 1$ , the grid and its ordering contain one terminal pivot and its factor column contains only the diagonal. Hence $d_{v} = 1$ for its unique vertex, and [F4] gives $O (1)$ work and exactly one stored factor entry.

1.3givenF1F2F3algebra

Let $G^{'}$ be the structural graph of $A$ and let $G$ be the full nearest-neighbor grid on the same vertices. They use the same coordinate ordering. If a pair is an edge in a filled graph of $G^{'}$ , [F3] supplies a witness walk in $G^{'}$ with internal vertices eliminated earlier; since $G^{'}$ is a subgraph of $G$ , the same walk witnesses that edge in the corresponding filled graph of $G$ . Thus every later filled neighbor in $G^{'}$ is also one in $G$ , and each subgraph column size is at most the full-grid column size. Fix a box at depth $r$ . Its separator has at most $d s_{r}^{d - 1}$ vertices by the union bound over its at most $d$ median hyperplanes; the terminal singleton satisfies the same bound. By [F2], each such pivot has full-grid column size at most $3 d s_{r}^{d - 1}$ , so the same bound holds for $A$ .

2.1step 1.3F3F4algebra

The factorization work contributed by one depth- $r$ box is therefore at most a constant depending only on $d$ times $s_{r}^{d - 1} s_{r}^{2 (d - 1)} = s_{r}^{3 (d - 1)}$ , using [F4]. Summing over at most $2^{d r}$ boxes at each depth and using $s_{r} \leq 2 k / 2^{r}$ gives $O ⁣ (k^{3 (d - 1)} \sum_{r = 0}^{R} 2^{- r (2 d - 3)}) .$ For $d = 2$ , the geometric ratio is $2^{- 1}$ , so this is $O (k^{3})$ . For $d = 3$ , the ratio is $2^{- 3}$ , so it is $O (k^{6})$ .

2.2step 1.3F2F3F4algebra

The storage contributed by one depth- $r$ box is at most a constant times $s_{r}^{d - 1} s_{r}^{d - 1} = s_{r}^{2 (d - 1)}$ , again by [F2] and [F4]. Summing over boxes and using $s_{r} \leq 2 k / 2^{r}$ gives $O ⁣ (k^{2 (d - 1)} \sum_{r = 0}^{R} 2^{- r (d - 2)}) .$ For $d = 2$ , there are $O (\log k)$ equal-order terms, giving $O (k^{2} \log k)$ . For $d = 3$ , the series is bounded by $\sum_{r \geq 0} 2^{- r} = 2$ , giving $O (k^{4})$ .

3.1step 1.2step 2.1step 2.2F1F2F3F4algebra∎

When $d = 2$ , $n = k^{2}$ gives $k^{3} = n^{3 / 2}$ and $k^{2} \log k = O (n \log n)$ for $k \geq 2$ . When $d = 3$ , $n = k^{3}$ gives $k^{6} = n^{2}$ and $k^{4} = n^{4 / 3}$ . Thus steps 1.2, 2.1 and 2.2 give the displayed rates and the $k = 1$ case. The proof used the coordinate-box and grid-boundary counts in [F1]–[F2] together with the fill containment proved in step 1.3, so it does not imply a bound for arbitrary graphs.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Certified real-component Hermitian one-by-one and two-by-two LDL* kernels

Definition

Input stored Hermitian $D \in C^{k \times k}$ , $B \in C^{t \times k}$ and $C \in C^{t \times t}$ , with $k \in {1, 2}$ , $t \geq 0$ , threshold $0 < θ \leq 1$ , unit roundoff $0 < u < 1$ , and a finite certificate budget. Use Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add. Divide complex values by a nonzero real denominator by separately dividing their real and imaginary components, using the model's real operations; no complex division is used. Any invalid operation, nonfinite output or nonzero exact intermediate outside the normal range returns range-failure. Hermitian counterparts, sign changes and conjugation are exact copies.

For a complex value $z = x + i y$ , $∣ z ∣$ denotes its exact mathematical modulus $\sqrt{x^{2} + y^{2}}$ ; this convention does not add a modulus operation to the floating-point model. Moduli in guard specifications and error bounds have this meaning, while the algorithm obtains only the rigorous bounds produced by the rounded scaled-norm procedure below.

The pivot controller uses exact real-RAM arithmetic on the stored real components and the supplied exact $u, θ$ , separately from the rounded numerical kernel. Its allowed operations are real addition, subtraction, multiplication, division by a certified nonzero real denominator, fixed nonnegative integer powers, and comparisons. Each field operation or comparison consumes one unit of the nonnegative integer controller budget; a fixed power is expanded into its stated finite chain of multiplications. Before any controller operation, if no unit remains, return pivot-inconclusive. Exact sign/absolute-value and maximum decisions use comparisons and conditional sign changes. For binary/rational stored values and rational $u, θ$ , exact rational arithmetic implements this controller with finite integers; no bit-complexity bound is claimed. There is no optional unspecified certifier or sign oracle. For complex modulus guards, a successful two-component scaled norm first scales by the larger absolute real component, then rounds both divisions, squares, sum, positive square root and rescaling. Its returned $h$ gives bounds $h / (1 + u)^{4} \leq ∣ z ∣ \leq h / (1 - u)^{4}$ ; zero is exact. Maxima use the corresponding lower/upper bounds and an empty maximum is zero. Evaluate modulus guards once per distinct stored complex value in row-major order, using only the displayed rounded scaled norm; its finite floating operations carry their own range status. No exact square root or additional modulus operation is used by the controller. Evaluate each displayed rational bound left to right, entrywise in row-major order; evaluate column maxima in increasing row order, then the at-most-two-term matrix-vector bounds in increasing column order, and finally the acceptance comparisons in row order. Compute each of $(1 - u)^{4}, (1 + u)^{4}, (1 + u)^{5}$ by left-associated repeated multiplication. These prescribed finite expression trees and finite input loops fix the guard procedure and its budget count. If acceptance is not established, evaluate the stated lower-bound failure comparisons; if neither conclusion follows, return pivot-inconclusive without refinement.

For $k = 1$ , write $D = [d]$ , $d$ real. If $d = 0$ return pivot-failure. Certify $\max_{i} ∣ B_{i 1} ∣ \leq ∣ d ∣ / θ$ using the guard bounds. A rigorous lower maximum exceeding $∣ d ∣ / θ$ returns pivot-failure; an unresolved comparison returns pivot-inconclusive. Set ${\hat{M}}_{i 1}$ by rounded real-component divisions of $B_{i 1}$ by $d$ .

For $k = 2$ , write $D = (\begin{array}{cc} a & z \\ \overline{z} & c \end{array})$ with real $a, c$ , and set $s = \max (∣ a ∣, ∣ c ∣, ∣ Re z ∣, ∣ Im z ∣)$ . If $s = 0$ return pivot-failure. Compute the four real entries of $\hat{E} = fl (D / s)$ and the conjugate counterpart by copying. In order compute $p = fl (\hat{a} \hat{c}), q_{1} = fl ((Re \hat{z})^{2}), q_{2} = fl ((Im \hat{z})^{2}), q = fl (q_{1} + q_{2}), \hat{d} = fl (p - q) .$ Put $ϵ_{d} = 3 ((1 + u)^{5} - 1)$ and $\hat{J} = adj (\hat{E}) = (\begin{array}{cc} \hat{c} & - \hat{z} \\ - \overline{\hat{z}} & \hat{a} \end{array})$ by copies. Unless $∣ \hat{d} ∣ > ϵ_{d}$ is certified, return pivot-inconclusive. For each entry obtain rigorous modulus bounds $j_{i j}^{-} \leq ∣ {\hat{J}}_{i j} ∣ \leq j_{i j}^{+}$ and set $U_{i j} = \frac{j_{i j}^{+}}{s (1 - u) (∣ \hat{d} ∣ - ϵ_{d})}, V_{i j} = \frac{j_{i j}^{-}}{s (1 + u) (∣ \hat{d} ∣ + ϵ_{d})} .$ Let $c_{j}^{-}, c_{j}^{+}$ bound $\max_{i} ∣ B_{i j} ∣$ . Accept only if $U c^{+} \leq θ^{- 1} (1, 1)^{T}$ componentwise. If any coordinate of $V c^{-}$ exceeds $θ^{- 1}$ return pivot-failure; otherwise an unresolved test returns pivot-inconclusive. On acceptance compute ${\hat{B}}_{s} = fl (B / s)$ , $K = fl ({\hat{B}}_{s} \hat{J})$ by sequential two-term complex dots, then $\hat{M} = fl (K / \hat{d})$ by real-component divisions. No explicit reciprocal $1 / s$ is formed.

For either block size, compute each allocated lower-triangle entry of $\hat{Z} = fl (\hat{M} B^{*})$ by sequential $k$ -term dots. Compute $fl (C - \hat{Z})$ there, retain only its real component on the diagonal, and obtain upper entries by exact conjugation. Return success with stored $D, \hat{M}, \hat{S}$ and the pivot certificates. An empty trailing block returns empty $\hat{M}, \hat{S}$ . In the sparse application, allocate the original block-neighbor clique and retain positions even when their numerical value is zero. Additional sparsity drops must be recorded separately as additive perturbations.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

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$ .

5 · Examples, counterexamples and false statements

None yet.

Sparse direct elimination and ordering

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Threshold partial-pivot sparse LU with explicit fill and failure statuses

Definition

Undirected structural graph of a Hermitian matrix

Definition

Recursive coordinate-separator ordering for two- and three-dimensional grids

Definition

Filled edges are witnessed by paths through earlier eliminated vertices

Statement

Facts & Assumptions

Proof

Real threshold sparse LU has a backward residual bound with actual growth

Statement

Facts & Assumptions

Proof

Elimination-tree column patterns and reach

Definition

Nested-dissection grid fronts are bounded by a box separator and its exterior boundary

Statement

Facts & Assumptions

Proof

Hermitian Schur-complement support stays inside the symmetric filled graph

Statement

Facts & Assumptions

Proof

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

Definition

Remarks

Every later filled neighbor lies on the elimination-tree parent path

Statement

Facts & Assumptions

Proof

Ordered sparse Cholesky with explicit pivot and range statuses

Definition

Block LDL* residual errors propagate with actual block growth

Statement

Facts & Assumptions

Proof

Ordered sparse Cholesky has the symbolic filled pattern when no cancellation occurs

Statement

Facts & Assumptions

Proof

Scalar multifrontal Cholesky and solves on the elimination forest

Definition

Scalar multifrontal elimination is equivalent to sparse Cholesky with column-count costs

Statement

Facts & Assumptions

Proof

Nested dissection gives the stated work and factor-storage bounds on regular grids

Statement

Facts & Assumptions

Proof

Certified real-component Hermitian one-by-one and two-by-two LDL* kernels

Definition

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

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources