TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck pass

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.

Validated CSR matrix-vector multiplication terminates with a status

Statement

Let $F$ be a field, let $m, n \in Z$ , let $r, c$ be finite integer arrays, and let $v, x$ be finite arrays with entries in $F$ . The algorithm Validated compressed sparse row matrix-vector product terminates on every such input. Its return status is invalid-dimension, invalid-index, or ok with a vector in $F^{m}$ .

Facts & Assumptions

Given: A field $F$ , integer dimension candidates $m, n$ , finite integer arrays $r, c$ , and finite arrays $v, x$ with entries in $F$ .

[L1]

Validated compressed sparse row matrix-vector product: with $s = length (v)$ , the routine first returns invalid-dimension unless $m, n \in N$ , $length (r) = m + 1$ , $length (c) = s$ , and $length (x) = n$ .

[L2]

Validated compressed sparse row matrix-vector product: after the dimension checks, finite scans check $0 \leq r_{i} \leq s$ for $0 \leq i \leq m$ , $r_{0} = 0$ , $r_{m} = s$ , $r_{i} \leq r_{i + 1}$ for $i < m$ , and $0 \leq c_{t} < n$ for $t < s$ ; any failure returns invalid-index.

[L3]

Validated compressed sparse row matrix-vector product: after validation, the routine initializes $y_{i} = 0_{F}$ for $i < m$ , traverses $t = r_{i}, \dots, r_{i + 1} - 1$ in each row, updates $y_{i} \leftarrow y_{i} + v_{t} x_{c_{t}}$ , and returns ok with $y$ .

Proof

1.1givenL1L2algebra

The tests in [L1] are finite and either return invalid-dimension or establish natural dimensions and the required array lengths. Since the arrays are finite, $s = length (v)$ is also a finite natural. The pointer-bound, pointer-monotonicity, and column-index scans in [L2] have respectively $m + 1$ , $m$ , and $s$ iterations, with two additional endpoint tests; every accessed index exists by [L1]. Thus validation finishes, either returning invalid-index or establishing all conditions in [L2].

2.1givenL1L2L3step 1.1algebra∎

If validation passes, [L2] gives $0 = r_{0} \leq \dots \leq r_{m} = s$ and $0 \leq c_{t} < n$ . Hence the row ranges partition ${0, \dots, s - 1}$ and have total length $\sum_{i < m} (r_{i + 1} - r_{i}) = s$ . The initialization and outer loop in [L3] each have $m$ iterations, and the inner loops have $s$ iterations in total. Every $v_{t}$ and $x_{c_{t}}$ accessed exists; field addition and multiplication keep each accumulator in $F$ . The routine therefore returns ok with a vector in $F^{m}$ . If $m = 0$ , validation forces $s = 0$ and returns the empty vector; empty row ranges likewise require no updates. Together with step 1.1 this proves the claim.

Depends on

Validated compressed sparse row matrix-vector product

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

2 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., Chapter 3 §3.5, printed pp. 95–96 (standard reference, not scraped)