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().