Skip to main content

xingo_sparse/
lib.rs

1//! # Chapter 5 — `xingo-sparse`: sparse linear algebra for optimization
2//!
3//! *Second edition (PLAN.md trilha L, task L1.2; D-0080 and its two
4//! addenda).* The first edition of this chapter was the crate
5//! `xingo-linalg`: the LU factorization of the simplex basis with
6//! Forrest–Tomlin updates and hypersparse solves. This edition moves it,
7//! together with the compressed containers of `xingo-core` (formerly
8//! Chapter 1.2), into a crate that does not depend on the solver and can
9//! be published on its own. **The migration has no numerical effect**:
10//! instantiated with `f64`, every operation below performs the same
11//! floating-point operations in the same order as the first edition, so
12//! the solver's results are bit for bit those of before (checked on the
13//! MIPLIB anchors and the `nl9` set, D-0080 addendum 2).
14//!
15//! ## 5.A The layer inversion
16//! Before: `xingo-linalg → xingo-core` (the factorization borrowed the
17//! containers, the typed indices, the error type and the tolerances of
18//! the solver's core). Now: `xingo-core → xingo-sparse`, and
19//! `xingo-sparse` depends on nothing in the workspace. Each borrowed item
20//! received a home here:
21//!
22//! | first edition (in `xingo-core`)          | second edition (here)                         |
23//! |------------------------------------------|-----------------------------------------------|
24//! | `CscMatrix`, `CsrMatrix`, `SparseVec`     | [`CscMatrix<T>`], [`CsrMatrix<T>`], [`SparseVec<T>`] (§5.8), `T = f64` by default |
25//! | `Col`, `Row` (Chapter 1.1)                | [`Col`], [`Row`] (§5.7), the same newtypes      |
26//! | `CoreError`                               | [`SparseError`] (containers) and [`LuError`] (factorization), §5.0 |
27//! | `Tolerances::{markowitz, zero}`           | [`LuOptions::rel_pivot_tol`], [`LuOptions::drop_tol`] |
28//! | `Tolerances::{lt, approx_eq, is_zero, …}` | the comparison helpers of §5.6 (crate-private)  |
29//!
30//! `xingo-core` re-exports the containers at their old paths as the `f64`
31//! instances (`xingo_core::CscMatrix = xingo_sparse::CscMatrix<f64>`, and
32//! so on), re-exports [`Col`] and [`Row`], and converts [`SparseError`] and
33//! [`LuError`] into its `CoreError`; the solver maps its `Tolerances` into
34//! [`LuOptions`] when it creates a factor.
35//!
36//! ## 5.B Scalars and genericity
37//! Every container and the factorization are generic in the scalar
38//! `T: `[`Real`] (§5.6), with `T = f64` the default type parameter, so
39//! `CscMatrix` written without parameters is `CscMatrix<f64>`. [`Real`] is
40//! the small trait a threshold-pivoting LU needs — the field operations, a
41//! total order on the values that occur (`PartialOrd`, NaN excluded by
42//! contract), `abs`, `max`, `is_finite`, conversion from and to `f64` —
43//! and is implemented here for `f64` only; `xingo-extprec` (trilha L2)
44//! will implement it for double-double and quad-double. Intervals are not
45//! `Real` (no total order, no single rounding; D-0080, Q2).
46//!
47//! *Genericity costs nothing* (D-0080, addendum 2): the code is generic
48//! by monomorphization only — no trait objects in the kernels — and every
49//! method of [`Real`] for `f64` is an `#[inline]` call of the inherent
50//! `f64` method, so `Lu<f64>` compiles to the same machine operations as
51//! the first edition's `Factor`. Options and statistics stay in `f64`
52//! (they are thresholds and counters, not data); a threshold enters the
53//! kernels through [`Real::from_f64`], the identity for `f64`.
54//!
55//! ## 5.C Comparisons
56//! The rule of the solver — "never compare `f64` outside
57//! `xingo_core::Tolerances`" — cannot hold in a crate below `xingo-core`.
58//! Its equivalent here: **every comparison of floating-point values goes
59//! through the helpers of §5.6** (`lt`, `le`, `approx_eq`, `is_zero`,
60//! `is_exact_zero`, the same definitions as `Tolerances`, generic in `T`),
61//! and every *threshold* of the factorization is a field of [`LuOptions`]
62//! — never a bare literal in a kernel. The two constants that remain are
63//! policy, documented where they are defined: the clearing fraction of
64//! [`SparseVec::clear`] (`0.3`, Chapter 5.8.3) and the moving-average
65//! weight [`HYPER_HISTORY_WEIGHT`] (Chapter 5.4).
66//!
67//! ## 5.D Contract and implementation
68//! The approved contract (`contracts/xingo-sparse/src/lib.rs`, L1.1) is the
69//! specification of the whole v0.1. This edition realizes the part listed
70//! for L1.2; its divergences from the contract are recorded in the cycle's
71//! decisions and listed for ratification.
72//!
73//! | contract                         | here                                                    |
74//! |----------------------------------|---------------------------------------------------------|
75//! | `Real`                           | [`Real`] (adds `Sum`, needed for bit-identical sums)     |
76//! | `CscMatrix<T>`, `CsrMatrix<T>`, `SparseVec<T>` | the same layouts; first-edition methods kept |
77//! | `Triplets<T>`, `BlockPartition` | [`Triplets`] (§5.8.4; `to_csc` keeps (C3): a zero *sum* is not stored, zero *inputs* are legal; + `from_csc`, `len`, `is_empty`, `clear`, `reserve`, `check_invariants`), [`BlockPartition`] (§5.8.5; + `new`, `from_sizes`, `check_invariants` and the block accessors) (L1.7a) |
78//! | `SparseError`, `LuError`         | [`SparseError`], [`LuError`] (variants of the first edition, see §5.0) |
79//! | `ColumnRef`, `Sign`, `ColumnSource<T>` | [`ColumnRef`], [`Sign`], [`ColumnSource`] (static dispatch) |
80//! | `LuOptions`, `LuStats`, `SolveStats`, `UpdateStats` | [`LuOptions`] (+ `drop_tol`), [`LuStats`], [`SolveStats`], [`UpdateStats`] |
81//! | `Lu<T, U = ForrestTomlin<T>>`, `LuFactor<T>`, `Factors<T>` | [`Lu`], [`LuFactor`], [`Factors`] |
82//! | `BasisUpdate<T>`, `ForrestTomlin<T>` | [`BasisUpdate`], [`ForrestTomlin`]                  |
83//! | `UpdateOutcome`, `RefactorReason` | [`UpdateOutcome`], [`RefactorReason`] (unchanged)      |
84//! | `Pattern`, `Perm`, `CscMatrix::{pattern, symmetric_pattern}` | [`Pattern`] (+ `transpose`, `symmetric`, `ata`, `cholesky_nnz`), [`Perm`] (L1.3) |
85//! | `Ordering`, `OrderingTarget`, `Natural`, `Amd`, `Colamd` | the same (L1.3; `Amd::default()` has aggressive absorption on) |
86//! | `PreOrder`, `LuOptions::pre_order`, `SymbolicLu`, `LuStats::symbolic_reuses` | [`PreOrder`], `Lu::{set_pre_order, pre_order}` (not an `LuOptions` field: see [`Lu::set_pre_order`]), [`SymbolicLu`] (+ `singletons`), `LuStats::{symbolic_reuses, symbolic_fallbacks}` (L1.3) |
87//! | `LuFactor::{refactorize_same_pattern, symbolic}` | the same (L1.3); the replay threshold `Lu::{set_refactor_pivot_tol, refactor_pivot_tol}` (L1.5b, default = `rel_pivot_tol`) |
88//! | `Equilibration`, `Scaling<T>` | [`Equilibration`], [`Scaling`] (+ `check_invariants`; §5.13, L1.5) |
89//! | `Inertia`, `Regularization<T>`, `Refinement<T>`, `RefineReport<T>`, `KktForm`, `KktSolver<T>`, `KktError` | the same (§5.14, L1.5), plus `Default` for the option structs, `Regularization::{none, relative_to, is_quasi_definite}`, `KktForm::expected_inertia`, `KktError::Structure`, [`EQUILIBRATION_PASSES`]; the augmented inertia reads `{positive: m, negative: n}`; L1.5b: `Regularization::scale` with [`ShiftScale`] (shifts in the equilibrated matrix by default), `KktError::NotFinite`, [`RefineWorkspace`] and `KktSolver::solve_refined_with`, refinement by GMRES |
90//! | `FaerLdl`, `FaerSymbolic`, `FaerNumeric<T>` (feature `faer`) | the same (§5.15, L1.5), plus read-only accessors |
91//! | `DenseBlock<T>`, `DenseKernel<T>`, `NaiveDense`, `FaerDense`, `DenseError` | the same (§5.16, L1.5); `sytrf` also returns its permutation and `2×2` marks |
92//! | `SupernodalOptions`, `SymbolicLdl`, `NumericLdl<T>`, `SupernodalLdl<T, K>` | the same (§5.17, L1.6a), plus `SupernodalOptions::supernodal_switch` (the simplicial/supernodal switch), the accessors `SymbolicLdl::{n_supernodes, relaxation_zeros, is_simplicial, check_invariants}` and `NumericLdl::{order, n_supernodes, perm, scale}`, `SupernodalLdl::kernel`, the constants `PANEL` and `RELAX_CUTOFFS`; the structs carry private fields the solves need (a numeric factor solves after its symbolic phase is dropped), and `diag`/`blocks` hold the factor of `P K_reg Pᵀ` in the caller's units. L1.6b: `SupernodalOptions::{zero_pivot_tol, pivot_threshold}`, `NumericLdl::{is_pivoted, delayed, supernodes, rows}` and `NumericLdl::perm` as the pivot order, for the `LBLᵀ` of the unregularized augmented system (Algorithm M, with delayed pivots: not in the contract, which foresaw intranodal pivots only) |
93//!
94//! ## 5.E What the tasks add
95//! * **L1.3** (done) — [`Perm`] and [`Pattern`] (§5.9), the orderings
96//!   [`Natural`], [`Amd`] and [`Colamd`] behind [`Ordering`] (§5.10, our
97//!   own; their engine, Algorithm Q, in §5.11), the reusable pivot
98//!   sequence [`SymbolicLu`] with [`LuFactor::refactorize_same_pattern`]
99//!   and the COLAMD pre-order of the bump [`Lu::set_pre_order`] (§5.12,
100//!   step L5′ of §5.3). With `pre_order = None` (the default) Algorithm L
101//!   is unchanged, bit for bit; the simplex uses none of it yet.
102//! * **L1.4** (after P3.9) — `BartelsGolub<T>`, the second
103//!   [`BasisUpdate`]; the trait already separates the update policy from
104//!   the stored factors ([`Factors`]), so the simplex will not change.
105//! * **L1.5** (done) — row/column scaling [`Scaling`] by the policies of
106//!   [`Equilibration`] (§5.13); the KKT interface [`KktSolver`] with the
107//!   regularization policy and the iterative refinement shared by every
108//!   backend (§5.14); the optional backend [`FaerLdl`] over faer's sparse
109//!   `LDLᵀ`/`LBLᵀ` ordered by our [`Amd`] (§5.15, feature `faer`; since
110//!   0.2.0 the recommended backend is the own [`SupernodalLdl`], §5.17,
111//!   D-0099); and the
112//!   dense kernels [`DenseKernel`], [`NaiveDense`] and `FaerDense`
113//!   (§5.16). The simplex uses none of it, and faer is not in the
114//!   solver's build: the workspace depends on this crate without default
115//!   features.
116//! * **L1.5b** (done) — before 0.1.0: a default regularization that holds
117//!   at the end of an interior-point method (shifts in the equilibrated
118//!   matrix, §5.14), refinement by right-preconditioned GMRES with
119//!   reusable work vectors, non-finite factors reported, solves without
120//!   allocation and exact bump counts (§5.15), the elimination-tree
121//!   postorder before faer's supernodes (§5.9, Algorithm P), a faster
122//!   Algorithm Q (§5.11), and the replay threshold of Algorithm R (§5.12).
123//! * **L1.7a** (done) — what 0.1.0 ships besides the code: the last two
124//!   containers of the contract, the coordinate builder [`Triplets`]
125//!   (§5.8.4, Algorithm C′) and [`BlockPartition`] (§5.8.5, Algorithm B);
126//!   the crate's README, CHANGELOG and three runnable examples
127//!   (`examples/`: a basis LU with a Forrest–Tomlin update, the orderings
128//!   against the natural order, one KKT step of an interior-point method);
129//!   complete item documentation. No solver path changes (nothing uses the
130//!   two new types yet).
131//! * **L1.6a** (done) — the own [`SupernodalLdl`] (§5.17): elimination
132//!   tree and relaxed supernodes on top of the postorder of §5.9, a
133//!   left-looking supernodal `LDLᵀ` with `1×1` pivots, the bumping of
134//!   step K3 with the sign each block expects and an exact count of the
135//!   bumped pivots, generic in `T` with the dense kernels of §5.16, solves
136//!   without allocation; the engine of §5.11 rewritten over one
137//!   garbage-collected workspace (same output). `FaerLdl` stays as the
138//!   optional backend and the oracle.
139//! * **L1.6b** (done) — the `LBLᵀ` of the unregularized augmented system in
140//!   [`SupernodalLdl`] (§5.17, Algorithm M): Bunch–Kaufman `1×1`/`2×2`
141//!   pivots inside each supernode through `DenseKernel::sytrf`, delayed
142//!   pivots to the parent supernode (MA57's scheme) for the columns with
143//!   no acceptable pivot, a zero pivot at a root reported as a singular
144//!   matrix; the regularized path untouched bit for bit. [`NaiveDense`]
145//!   with contiguous blocked loops (§5.16). Measured and not adopted:
146//!   nested dissection (our AMD's fill is 0.97× METIS's on average), a strided `DenseKernel`, `PANEL = 64`.
147//!
148//! ## Purpose (the first edition, unchanged)
149//! The revised simplex method (Chapter 6) works with the basis matrix `B`
150//! only through three operations: factorize `B`, solve with `B` or `Bᵀ`,
151//! and replace one column of `B`. This crate provides them
152//! (`PLAN.md` §5 items 1–2, tasks P1.1–P1.2):
153//!
154//! * §5.0 [`error`] — [`SparseError`], [`LuError`], [`KktError`] and
155//!   [`DenseError`];
156//! * §5.1 [`basis`] — how the basis is named: [`ColumnRef`] into `[A | ±I]`,
157//!   and the general [`ColumnSource`];
158//! * §5.2 (private) — dynamic row/column files and count lists;
159//! * §5.3 [`factor`] — [`Lu`] and [`LuFactor::factorize`], Algorithm L:
160//!   singleton (triangular) phase, then Markowitz pivoting with a relative
161//!   threshold on the bump (Suhl & Suhl 1990);
162//! * §5.4 [`solve`] — [`LuFactor::ftran`] and [`LuFactor::btran`]: the
163//!   dense Algorithms F and B and the hypersparse Algorithms HF and HB
164//!   (Gilbert–Peierls reach), chosen per call by the density policy of
165//!   Hall & McKinnon (task P1.4);
166//! * §5.5 [`update`] — [`LuFactor::update`] through the [`BasisUpdate`]
167//!   policy, the Forrest–Tomlin update [`ForrestTomlin`] (Algorithm U), and
168//!   the refactorization policy ([`UpdateOutcome`]);
169//! * §5.6 [`real`] — the scalar trait [`Real`] and the comparisons;
170//! * §5.7 [`index`] — the typed indices [`Col`] and [`Row`];
171//! * §5.8 [`compressed`], [`csc`], [`csr`], [`vector`] — the containers
172//!   (Algorithms T, C and S; Chapter 1.2 of the first edition); [`triplets`]
173//!   — the coordinate builder [`Triplets`] (Algorithm C′); [`partition`] —
174//!   [`BlockPartition`] (Algorithm B);
175//! * §5.9 [`perm`] — [`Perm`] and [`Pattern`], and the Cholesky count of an
176//!   ordering (Algorithm E);
177//! * §5.10 [`ordering`] — [`Ordering`], [`Natural`], [`Amd`] (Algorithm A),
178//!   [`Colamd`] (Algorithm C);
179//! * §5.11 (private) — approximate minimum degree on a quotient graph
180//!   (Algorithm Q), the engine of both;
181//! * §5.12 [`symbolic`] — [`SymbolicLu`] and Algorithm R
182//!   ([`LuFactor::refactorize_same_pattern`]);
183//! * §5.13 [`scaling`] — [`Equilibration`] and [`Scaling`] (Algorithms G,
184//!   R and I);
185//! * §5.14 [`kkt`] — [`KktSolver`] and its shared policy: regularization
186//!   (Algorithm K) and iterative refinement (Algorithm F);
187//! * §5.15 `faer_ldl` (feature `faer`) — [`FaerLdl`] (Algorithms A, N, S);
188//! * §5.16 [`dense`] — [`DenseKernel`], [`NaiveDense`], `FaerDense`
189//!   (Algorithms P, B, T, G, S);
190//! * §5.17 [`supernodal`] — [`SupernodalLdl`], our own supernodal `LDLᵀ`
191//!   (Algorithms A, N, U, D, S).
192//!
193//! ## Notation
194//! `B ∈ R^{m×m}`; *rows* `i` and basis *positions* `k` both range over
195//! `0..m` but are distinct index spaces. `P B Q = L U` with `P`, `Q`
196//! permutations, `L` unit lower and `U` upper triangular; after `t`
197//! updates `B = Pᵀ L R₁⁻¹ ⋯ R_t⁻¹ U Qᵀ` with row etas `R_e` and updated
198//! `P`, `Q`, `U`. Identifiers follow the chapters: `l_ic`, `u_pj`, `mu`
199//! (`μ`), `alpha_r` (`α_r`), `tau` (`τ`), `sigma` (`σ`). Indices are `u32`
200//! in the stored arrays, pointers `usize` (PLAN.md §3.2; D-0080, Q3).
201//!
202//! ## Contract with the simplex method
203//! 1. `lu.factorize(&(&heading[..], &a))` (a [`ColumnSource`]); on
204//!    [`LuError::Singular`] replace each `cols[k]` by
205//!    `ColumnRef::Logical(rows[k], _)` and factorize again.
206//! 2. `ftran(&mut v)` maps a row-indexed `v` to the position-indexed
207//!    `B⁻¹ v`; `btran(&mut v)` maps a position-indexed `v` to the
208//!    row-indexed `B⁻ᵀ v`. Both take `&mut self`: the factor owns the work
209//!    arrays of the solves and the density statistics that choose between
210//!    the dense and the hypersparse algorithms. Give the right-hand side in
211//!    sparse mode with a correct pattern to allow the hypersparse
212//!    algorithms; the result comes back in sparse mode, its pattern a
213//!    superset of its support (Chapter 5.4, invariant (V1)).
214//! 3. To pivot position `r` out for column `a_q`:
215//!    `ftran_for_update(&mut a_q)` (giving `α_q`), then
216//!    `update(r, α_q[r])`. On [`UpdateOutcome::RefactorNeeded`] (or any
217//!    error) refactorize with the new heading; the factor never does so on
218//!    its own (D-0016).
219//!
220//! ## Safety
221//! Per D-0006 this is the one crate where `unsafe` is permitted (audited,
222//! `// SAFETY:` comments, Miri where executable). This edition, like the
223//! first, uses none; optimized kernels wait for measurements (task P1.10).
224//! The `faer` feature (L1.5) brings faer's own `unsafe` kernels in as a
225//! dependency; the code of this crate stays free of `unsafe`.
226//!
227//! ## References
228//! Suhl & Suhl (1990); Forrest & Tomlin (1972); Maros, *Computational
229//! Techniques of the Simplex Method* (2003), ch. 5 and 8; Davis, *Direct
230//! Methods for Sparse Linear Systems* (2006); Duff, Erisman & Reid (1986);
231//! Koberstein (2005), ch. 5; Gilbert & Peierls (1988); Hall & McKinnon
232//! (2005); Gustavson (1978); Amestoy, Davis & Duff (1996); Davis, Gilbert,
233//! Larimore & Ng (2004); the contract of the crate
234//! (`contracts/xingo-sparse`, D-0080).
235
236// Without `faer`, the chapter text still names FaerLdl/FaerDense.
237#![cfg_attr(not(feature = "faer"), allow(rustdoc::broken_intra_doc_links))]
238
239pub mod basis;
240pub mod compressed;
241pub mod csc;
242pub mod csr;
243pub mod dense;
244pub mod error;
245pub mod factor;
246#[cfg(feature = "faer")]
247pub mod faer_ldl;
248pub mod index;
249pub mod kkt;
250pub mod ordering;
251pub mod partition;
252pub mod perm;
253mod qgraph;
254pub mod real;
255pub mod scaling;
256pub mod solve;
257mod store;
258pub mod supernodal;
259pub mod symbolic;
260pub mod triplets;
261pub mod update;
262pub mod vector;
263
264#[cfg(test)]
265mod tests;
266
267/// The code blocks of the crate's README, compiled and run as doc-tests
268/// (`cargo test --doc`) so that the README never drifts from the API. The
269/// README is not the root documentation — this chapter is. (Since L1.6a
270/// the KKT snippet runs on `SupernodalLdl`, so no feature is needed.)
271#[cfg(doctest)]
272#[doc = include_str!("../README.md")]
273pub struct ReadmeDoctests;
274
275pub use basis::{ColumnRef, ColumnSource, Sign};
276pub use csc::CscMatrix;
277pub use csr::CsrMatrix;
278#[cfg(feature = "faer")]
279pub use dense::FaerDense;
280pub use dense::{DenseBlock, DenseKernel, NaiveDense};
281pub use error::{DenseError, KktError, LuError, SparseError};
282pub use factor::{Factors, Lu, LuFactor, LuOptions, LuStats, PreOrder};
283#[cfg(feature = "faer")]
284pub use faer_ldl::{FaerLdl, FaerNumeric, FaerSymbolic};
285pub use index::{Col, Row};
286pub use kkt::{
287    EQUILIBRATION_PASSES, Inertia, KktForm, KktSolver, RefineReport, RefineWorkspace, Refinement,
288    Regularization, ShiftScale,
289};
290pub use ordering::{Amd, Colamd, Natural, Ordering, OrderingTarget};
291pub use partition::BlockPartition;
292pub use perm::{Pattern, Perm};
293pub use real::Real;
294pub use scaling::{Equilibration, Scaling};
295pub use solve::{HYPER_HISTORY_WEIGHT, SolveStats};
296pub use supernodal::{NumericLdl, SupernodalLdl, SupernodalOptions, SymbolicLdl};
297pub use symbolic::SymbolicLu;
298pub use triplets::Triplets;
299pub use update::{BasisUpdate, ForrestTomlin, RefactorReason, UpdateOutcome, UpdateStats};
300pub use vector::SparseVec;