Skip to main content

Module triplets

Module triplets 

Source
Expand description

§Chapter 5.8.4 — The coordinate builder

New with task L1.7a (PLAN.md trilha L): the contract’s Triplets<T>, the last container of v0.1 after Pattern (L1.3).

§Purpose

A compressed matrix (Chapter 5.8.1) is awkward to build: its entries must arrive column by column, rows sorted, duplicates merged. Code that assembles a matrix — a model reader, the interior-point method stacking [−D Aᵀ; A δI] block by block, a test writing a small example — knows its entries in no particular order and sometimes twice. Triplets is that coordinate (COO) form: three parallel arrays (row, col, val) that grow by Triplets::push in any order, and one conversion, Triplets::to_csc, that sorts, sums the duplicates and validates.

CscMatrix::from_triplets (Chapter 5.8.1) does the same for a slice of (Row, Col, T) tuples and is what the solver uses; it is unchanged. The builder is the incremental form for code outside the solver — plain u32 indices, the arrays public as in the contract, buffers that can be cleared and refilled at every iteration of a method whose pattern is fixed while its values change.

§Notation

A builder of an m × n matrix holds K triplets (i_k, j_k, v_k), k = 0, …, K−1, in insertion order (the order of the push calls). The matrix it denotes has entry a_ij = Σ_{k : i_k = i, j_k = j} v_k, the sum taken in insertion order.

§Algorithm C′ (Compression of a coordinate list)

Algorithm C of Chapter 5.8.1 on the three parallel arrays of the builder (the same four steps, so that the two constructors agree bit for bit on the same list).

C′1. [Validate.] Reject arrays of unequal length ((D1) below), a dimension above u32::MAX, an index i_k ≥ m or j_k ≥ n, and a non-finite v_k. Nothing is validated earlier: push only appends, so an index out of range is reported here, by SparseError::IndexOutOfRange, never panicked on. C′2. [Bucket by row.] Counting-sort the triplets by row, stably: row i receives the pairs (j_k, v_k) in insertion order. C′3. [Transpose.] Algorithm T of Chapter 5.8 on the arrays of C′2. Each column now lists its rows in non-decreasing order, and the duplicates of (i, j) are adjacent and still in insertion order. C′4. [Sum and compact.] Sweep each column once, replacing every run of equal row indices by the sum of its values, accumulated left to right — that is, in insertion order, without reassociation: the result of push(0, 0, 1e16); push(0, 0, 1.0); push(0, 0, −1e16) is (1e16 + 1) − 1e16 = 0 in f64, while pushing −1e16 before 1.0 gives 1. Reject a sum that overflows to ±∞. A sum that is exactly zero is not stored: the output must satisfy (C3) of Chapter 5.8, which forbids explicit zeros in a CscMatrix. Zeros are therefore accepted as input — push(i, j, 0.0) is legal and takes part in the sum — and absent from the output exactly when the sum cancels. Rebuild col_ptr.

Every step is a stable counting sort or a left-to-right sweep, so the output, rounding of duplicate sums included, depends only on the sequence of pushes — never on hashing, allocation or thread. Cost O(K + m + n) time and space.

Divergence from the contract. The contract’s to_csc “drops nothing (zeros are kept)”, under its invariant (S1), which admits stored zeros. The implementation of L1.2 kept the first edition’s stricter (C3) — no explicit zeros, because the solver’s counts rely on it (D-0088, the containers’ invariants) — so a CscMatrix with a stored zero would fail its own CscMatrix::check_invariants. to_csc keeps (C3); what survives of the contract’s sentence is that a zero input is not an error. Listed for ratification (task L1.7a).

§Invariants

(D1) row.len() = col.len() = val.len(): the number of triplets, Triplets::len. Maintained by every method; a value built from the public fields is checked by C′1. (D2) n_rows ≤ u32::MAX and n_cols ≤ u32::MAX ((C4) of Chapter 5.8); Triplets::new asserts it, as CscMatrix::new does. (D3) After a successful to_csc: every row[k] < n_rows, every col[k] < n_cols, every val[k] finite. Not maintained by push (checked in C′1); Triplets::check_invariants checks (D1)–(D3) on demand. (D4) to_csc returns a matrix satisfying (C1)–(C4) of Chapter 5.8 whose entry (i, j) is the insertion-order sum of the pushes at (i, j), or an error; asserted in debug builds.

§References

Davis, Direct Methods for Sparse Linear Systems (2006), §2.1 (the triplet form) and §2.5 (cs_compress, cs_dupl); Gustavson (1978); Chapter 5.8.1 (Algorithm C); the contract of the crate (Triplets<T>).

Structs§

Triplets
Coordinate builder: push (i, j, v) in any order, duplicates summed in insertion order, then Triplets::to_csc (Algorithm C′).