Expand description
§Chapter 5.8.1 — Compressed sparse column storage
§Purpose
CscMatrix is the canonical storage of the constraint matrix A. It is
physically identical to an Arrow ListArray of (row, val) and to R’s
Matrix::dgCMatrix (PLAN.md §4.2), so the fields are public for
zero-copy interoperability; CscMatrix::check_invariants guards them.
§Notation
A ∈ R^{m×n}; column j holds the pairs (row_idx[p], val[p]) for
p ∈ [col_ptr[j], col_ptr[j+1]). A triplet (i, j, v) is one entry of
the coordinate (COO) format; a triplet list may contain duplicates, which
denote the sum of their values, and zeros.
§Algorithm C (Compression of a triplet list)
Given m, n and triplets (i_k, j_k, v_k), k = 0, …, K−1.
C1. [Validate.] Reject an index i_k ≥ m or j_k ≥ n, and a non-finite
v_k.
C2. [Bucket by row.] Counting-sort the triplets by row, stably: row i
receives the pairs (j_k, v_k) in input order. This is a CSR array
with unsorted column indices and possible duplicates.
C3. [Transpose.] Apply Algorithm T (Chapter 5.8) to the arrays of C2. In
the result every column lists its row indices in non-decreasing order,
and duplicates (i, j) are adjacent and still in input order.
C4. [Sum and drop.] Sweep each column once, replacing each run of equal
row indices by the sum of its values (accumulated in input order) and
dropping sums that are exactly zero. Reject a sum that overflows to
±∞. Compact the arrays in place and rebuild col_ptr.
The output satisfies (C1)–(C4) of Chapter 5.8. Because every step is a
stable counting sort, the result — including the rounding of duplicate
sums — depends only on the input, never on hashing or allocation order.
Cost: O(K + m + n) time and space.
Only exact zeros are dropped: deciding that 1e-17 is noise is a
modelling decision taken by the solver’s presolve with its tolerances
(xingo_core::Tolerances::zero), not by storage.
§Invariants
(C1)–(C4) of Chapter 5.8 with ptr = col_ptr, idx = row_idx,
n_major = n, n_minor = m; checked by CscMatrix::check_invariants
and asserted in debug builds after every construction.
§References
Davis, Direct Methods for Sparse Linear Systems (2006), §2.2–2.5
(cs_compress, cs_dupl); Gustavson (1978).
Structs§
- CscMatrix
- Sparse matrix in compressed sparse column (CSC) format.