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, thenTriplets::to_csc(Algorithm C′).