Skip to main content

Module csc

Module csc 

Source
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.