Skip to main content

Module csr

Module csr 

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