Expand description
§Chapter 5.8.2 — Compressed sparse row storage
§Purpose
CsrMatrix stores A by rows. The simplex method computes the pivot
row α_r = ρ_r A_N row-wise when ρ_r is sparse (Hall & McKinnon 2005),
and presolve and domain propagation walk constraints row by row. The CSR
copy is derived from the canonical CscMatrix on demand by
CscMatrix::to_csr; whoever needs it repeatedly (the solver) owns and
caches it, so the solver’s Model stays a plain value.
§Notation
Row i holds the pairs (col_idx[p], val[p]) for
p ∈ [row_ptr[i], row_ptr[i+1]). The arrays (row_ptr, col_idx, val) of
A are exactly the CSC arrays of Aᵀ.
§Invariants
(C1)–(C4) of Chapter 5.8 with ptr = row_ptr, idx = col_idx,
n_major = m, n_minor = n; checked by CsrMatrix::check_invariants.
§References
Hall & McKinnon, “Hyper-sparsity in the revised simplex method and how to exploit it”, Comput. Optim. Appl. 32, 2005; Davis (2006), §2.5.
Structs§
- CsrMatrix
- Sparse matrix in compressed sparse row (CSR) format.