Module vector 

Chapter 5.8.3 — The sparse work vector

Purpose

The simplex kernels (FTRAN, BTRAN, pivot row, updates) produce vectors whose density ranges from a few entries to completely dense, often within the same solve. SparseVec serves both regimes, in the spirit of HiGHS’s HVector: values live in a dense work array of length size, so any entry is read or written in O(1), and an optional pattern lists the positions that may be nonzero, so that sparse operations cost O(count) instead of O(size).

Notation

y ∈ R^size is the vector, stored densely in val. When the vector is in sparse mode, P = idx[0..count] is its pattern; in dense mode no pattern is kept and count = size by convention. A packed vector is a pair of slices (ι, ν) meaning Σ_k ν_k e_{ι_k}.

Operations (each with a sparse path, used when the relevant pattern is known, and a dense path over all size positions):

• clear: y ← 0;
• scatter(α, ι, ν): y ← y + α Σ_k ν_k e_{ι_k} (packed → work);
• axpy(α, x): y ← y + α x for another work vector x;
• gather: work → packed list of the nonzero entries;
• tidy: zero out entries with |y_i| ≤ ε (a drop tolerance) and drop them from P.

Algorithm S (Sparse update of the work vector)

To add δ to y_i:

S1. [Record.] If the vector is in sparse mode and mark[i] is false, set mark[i] ← true and append i to the pattern. S2. [Update.] Set val[i] ← val[i] + δ.

axpy applies S to every i with x_i ≠ 0, enumerating i over the pattern of x if it has one and over 0..size otherwise; the two enumerations visit the same set of positions and perform, at each, the identical floating-point operation, so the sparse and dense paths give bit-for-bit equal values. clear resets only the pattern positions when count ≤ 0.3·size (the HiGHS threshold, a policy constant of this chapter) and the whole array otherwise.

The mark array makes membership in P an O(1) test that does not depend on val[i] ≠ 0: an entry that cancels to exactly zero stays in the pattern and is never duplicated. HiGHS instead keeps cancelled entries at a tiny sentinel value; the explicit mark costs one byte per position and keeps exact zeros exact.

Invariants

(V1) val.len() = mark.len() = size. (V2) Sparse mode: the entries of P are distinct and < size; mark[i] ⇔ i ∈ P; and val[i] ≠ 0 ⇒ i ∈ P (the pattern is a superset of the support; it may contain explicit zeros). (V3) Dense mode: P is empty and every mark[i] is false.

Checked by SparseVec::check_invariants.

References

Hall & McKinnon (2005); HiGHS HVector (src/simplex/HVector*), studied, not copied; Gilbert & Peierls (1988) for why the pattern matters.

Structs

SparseVec

Work vector with a dense value array and an optional nonzero pattern.