TheoremStatement: AI-adaptedProof: AI-generatedPipeline-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.

ILU(0) factor slots, setup work, and application work

Statement

Let $F$ be a field, $n \geq 1$ , and $A \in M_{n} (F)$ have a valid canonical CSR record with strictly increasing column indices in each row. Let $P = {(i, j) : a_{i j} \neq 0}$ and $s = nnz (A)$ . Run Fixed-pattern ILU(0) factorization and application. The procedure terminates with a missing-diagonal or zero-pivot status, or returns ok.

On an ok return, define $P_{L} = {(i, k) \in P : i > k}, P_{U} = {(k, j) \in P : k \leq j},$ and put $ℓ = ∣ P_{L} ∣$ , $q = ∣ P_{U} ∣$ , and $u = q - n$ . The stored strict-lower slots of $L$ are exactly $P_{L}$ , and the stored slots of $U$ are exactly $P_{U}$ ; the unit diagonal of $L$ is implicit. Thus the factors use exactly $ℓ + q = s$ numeric slots. Here a factor's stored-slot count retains a slot even if an update makes its value zero.

For each $(i, k) \in P_{L}$ , let $R_{i k} = {j > k : (i, j) \in P}, C_{k} = {j > k : (k, j) \in P},$ and set $I = \sum_{(i, k) \in P_{L}} ∣ R_{i k} \cap C_{k} ∣$ and $J = \sum_{(i, k) \in P_{L}} (∣ R_{i k} ∣ + ∣ C_{k} ∣)$ . On a successful setup, the factorization performs exactly $ℓ$ divisions, $I$ multiplications, and $I$ subtractions. The two-pointer merges perform at most $J$ column-index comparisons, in addition to one validation visit for each of the $n$ row intervals and the $s$ stored entries.

Applying a successful factor pair to one vector by the specified two triangular solves performs exactly $ℓ + u = s - n$ multiplications, $s - n$ subtractions, and $n$ divisions, and returns the unique vector produced by forward and backward substitution. These counts concern setup and one application separately. They assert no convergence, conditioning improvement, or accuracy guarantee. The stored-pattern conclusion is about $L$ and $U$ ; it does not assert that the product $L U$ has support contained in $P$ .

Facts & Assumptions

Given: A field $F$ , a canonical sorted CSR record for $A \in M_{n} (F)$ with $n \geq 1$ , and a successful run of the fixed-pattern ILU(0) algorithm.

[A1]

Field: every nonzero field element has a multiplicative inverse, so division by a checked nonzero pivot is defined.

[F1]

Fixed-pattern ILU(0) factorization and application: the returned $L$ and $U$ use only input-pattern slots; each multiplier update is made only at a matching pair of input-pattern positions; every matching slot is visited even if its current value is zero; and application traverses every stored strict-lower and strict-upper factor slot once.

[F2]

Compressed sparse row matrices with stored-entry semantics: a canonical CSR record has no repeated column and no stored zero, so its stored-entry count is $s = nnz (A)$ .

[F3]

Forward and backward substitution for triangular linear systems: for lower-triangular $L$ with nonzero diagonal, forward substitution uses $x_{i} = ℓ_{i i}^{- 1} (b_{i} - \sum_{j < i} ℓ_{i j} x_{j})$ .

[F4]

Forward and backward substitution for triangular linear systems: for upper-triangular $U$ with nonzero diagonal, backward substitution uses $x_{i} = u_{i i}^{- 1} (b_{i} - \sum_{j > i} u_{i j} x_{j})$ .

[F5]

Forward and backward substitution are correct, unique, and quadratic in scalar operations: when $L$ is lower triangular with nonzero diagonal, forward substitution produces the unique solution of $L x = b$ .

[F6]

Forward and backward substitution are correct, unique, and quadratic in scalar operations: when $U$ is upper triangular with nonzero diagonal, backward substitution produces the unique solution of $U x = b$ .

Proof

1.1givenA1F1F2algebra

The input has finite arrays and $n$ is finite. Validation visits the $n$ row intervals and $s$ stored entries once; the factorization loops over at most $n$ rows, finitely many pattern entries, and finite row-list merges. Every division is preceded by a nonzero-pivot check, and [A1] makes each such division defined. Thus the procedure either returns one of its specified failure statuses or completes with ok.

2.1F1step 1.1

If the procedure returns ok, each processed pivot is nonzero by its check, so the returned $U$ has nonzero diagonal. The definition sets $L$ to be unit lower triangular and retains only upper entries in $U$ .

3.1F1F2step 2.1induction

Initially the work values occupy exactly the input slots $P$ . Each multiplier is written only at a strict-lower slot in $P_{L}$ , and each update is performed only when both matching row positions are in $P$ . No update allocates a new position. Induction over the finite row and pivot loops therefore gives stored patterns $P_{L}$ and $P_{U}$ for $L$ and $U$ , respectively.

3.2F1F3F4F5F6step 2.1

The forward recurrence in [F3] applied to unit-lower $L$ and the backward recurrence in [F4] applied to $U$ are well-defined because $L_{i i} = 1$ and every $U_{i i} \neq 0$ . By [F5] and [F6] they produce the unique successive triangular-solve outputs specified by the algorithm.

4.1F2step 3.1algebra

The sets $P_{L}$ and $P_{U}$ are disjoint and partition $P$ : every $(i, j) \in P$ has exactly one of $i > j$ or $i \leq j$ . Hence $ℓ + q = ∣ P ∣ = s$ . Since the unit diagonal of $L$ is implicit, this is exactly the factor numeric-slot count.

4.2F1step 3.1algebra

On success, the outer lower-pattern loop processes every one of the $ℓ$ positions once and performs one division there. For a fixed $(i, k) \in P_{L}$ , the update loop visits exactly the indices in $R_{i k} \cap C_{k}$ ; each visit performs one multiplication and one subtraction. Summing these counts gives exactly $ℓ$ divisions and $I$ multiplications and subtractions.

5.1F1F2step 4.2algebra

Both lists in each intersection are strictly increasing. A two-pointer merge advances at least one pointer at every comparison and stops when one list ends, so it makes at most the sum of the two list lengths, $∣ R_{i k} ∣ + ∣ C_{k} ∣$ , comparisons. Summing over $P_{L}$ gives the bound $J$ ; validation visits each row interval and stored entry once.

6.1F1F3F4step 4.1algebra∎

The forward recurrence in [F3] performs one multiplication and subtraction for each stored strict-lower slot, hence $ℓ$ of each and no diagonal divisions. The backward recurrence in [F4] performs one multiplication and subtraction for each stored strict-upper slot, hence $u$ of each, and one division for each of its $n$ rows. Since $ℓ + u = ℓ + q - n = s - n$ , the stated application counts follow.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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

Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., §§10.3.1–10.3.2, printed pp. 301–310 (standard reference, not scraped)
Richard Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed., §§3.4.1–3.4.2, printed pp. 38–41 (standard reference, not scraped)