Skip to main content

Module index

Module index 

Source
Expand description

§Chapter 5.7 — Typed indices

§Purpose

Columns and rows of a matrix are both numbered from zero, and passing a row number where a column number was expected is the classic silent bug of sparse codes. Col and Row are distinct newtypes, so the compiler rejects that confusion at no runtime cost. They lived in xingo-core (Chapter 1.1) until task L1.2; the containers (Chapter 5.8) and the basis references (Chapter 5.1) speak them, so they moved down with the containers and xingo-core re-exports them unchanged.

§Notation

A matrix has n columns, indexed by j ∈ {0, …, n−1}, and m rows, indexed by i ∈ {0, …, m−1}. Col(j) names column j and Row(i) names row i. In the solver a column is a variable and a row a constraint.

§Representation

Both are u32 wrappers (PLAN.md §3.2; D-0080, Q3): 2³² − 1 entities is ample, and halving the width of row_idx compared with usize saves memory bandwidth in every sparse kernel. Offsets into nonzero arrays (col_ptr, row_ptr) are usize, because nnz may exceed 2³².

§Invariants

(I1) Conversion from usize never truncates: Col::from_usize and Row::from_usize panic beyond u32::MAX. (I2) Range validity (j < n, i < m) is a property of the structure that stores the index and is checked by its check_invariants().

Structs§

Col
Index of a column (in the solver: a variable), 0 ≤ j < n.
Row
Index of a row (in the solver: a constraint), 0 ≤ i < m.