xingo_sparse/symbolic.rs
1//! # Chapter 5.12 — The reusable pivot sequence: [`SymbolicLu`]
2//!
3//! *New with task L1.3 (PLAN.md trilha L; the contract's `SymbolicLu`,
4//! `LuFactor::refactorize_same_pattern` and the pre-order `PreOrder`).*
5//!
6//! ## Purpose
7//! Algorithm L (Chapter 5.3) spends most of its time *deciding*: loading
8//! the doubly linked row and column files, keeping the count lists, and
9//! searching for Markowitz pivots. When the same pattern comes back with
10//! new values — the same basis after a change of scaling or of bounds, a
11//! node of branch and bound that restarts from its parent's basis, a
12//! sequence of systems with one structure — the decisions of the last
13//! factorization are still good ones, and only the arithmetic has to be
14//! redone. [`SymbolicLu`] keeps those decisions: the pivot sequence
15//! `(p_s, q_s)`, `s = 0, …, m − 1`. [`crate::LuFactor::refactorize_same_pattern`]
16//! replays it by a *left-looking* elimination (Algorithm R) that computes
17//! one column of `L` and `U` at a time with a sparse triangular solve, the
18//! scheme of Gilbert & Peierls (1988) with the pivot rows given instead of
19//! searched for.
20//!
21//! This is weaker than the symbolic object of UMFPACK, which also fixes
22//! the patterns of `L` and `U` (a threshold-pivoting Markowitz LU chooses
23//! its pivots by value, so its analysis is not separable; the contract,
24//! *Divergences*): the patterns are recomputed — cheaply, by the reach of
25//! each column — and every pivot is tested again. A pivot refused by the
26//! test, or a sequence of another order, sends the call back to Algorithm
27//! L, so the result is always a valid factorization (or the diagnosis of a
28//! singular basis).
29//!
30//! The optional COLAMD pre-order of the bump ([`crate::Lu::set_pre_order`],
31//! step L5′ of Chapter 5.3) is the other half of the contract's symbolic
32//! phase: it fixes the column order of the first factorization from the
33//! pattern alone, and the sequence it produces is the one Algorithm R
34//! reuses.
35//!
36//! ## Notation
37//! `B` is `m × m` with columns given by a [`ColumnSource`]; the sequence is
38//! `p_s` = `pivot_rows[s]`, `q_s` = `pivot_cols[s]`; its first `σ` steps
39//! (`singletons`) were singleton pivots of the triangular phase (L3–L4),
40//! forced by the structure. At step `s` the rows `p_0, …, p_{s−1}` are
41//! *pivoted*, the others *active*. `L_t` is the `L` column of step `t`
42//! (multipliers `l_it` for active rows `i` at step `t`), indexed by its
43//! pivot row; the graph `G_L` has an edge `p_t → i` for every `l_it`.
44//!
45//! ## Algorithm R (Refactorization with a given pivot sequence)
46//! R1. [Applicable?] If there is no sequence, or its order is not `m`,
47//! fall back to Algorithm L. Validate the source (invariant (B1)).
48//! R2. [Scatter.] For `s = 0, 1, …, m − 1`: let `q = q_s`, `p = p_s`;
49//! scatter column `q` of `B` into the dense row-indexed work vector `x`
50//! and its rows into the pattern `X`.
51//! R3. [Reach.] Find the set of rows reachable from `X` in `G_L` by depth-
52//! first search; it joins `X`. The pivoted rows with an `L` column, in
53//! reverse postorder of the search, are a topological order of the
54//! reach (Gilbert & Peierls 1988).
55//! R4. [Solve.] In that order, for each pivoted row `r` with `x_r ≠ 0`:
56//! `x_i ← x_i − l_ir x_r` for every `l_ir` of `L_r`. Now `x_r` (pivoted
57//! `r`) is the entry `u_{r q}` of `U`, and `x_i` (active `i`) is the
58//! entry `s_iq` of the Schur complement that Algorithm L would have
59//! seen when pivoting column `q`.
60//! R5. [Test.] Let `γ = max_{i active} |x_i|`. If `|x_p| ≤ τ_abs`, or `s ≥ σ`
61//! and `|x_p| < u_R γ` (by default `u_R = u`, Markowitz's threshold of
62//! Chapter 5.3; the singleton steps keep the rule of L3–L4: forced
63//! pivots, no relative test), fall back to Algorithm L.
64//! R6. [Record.] `u_pq ← x_p`; for each pivoted `r ∈ X` with `|x_r| > ε_drop`
65//! record `u_rq = x_r`; for each active `i ≠ p` with `|x_i| > ε_drop`
66//! record `l_is = x_i / x_p` (the `L` column of step `s`, pivot row
67//! `p`). Clear `x` on `X`; row `p` is pivoted.
68//! R7. [Finish.] Step L7 of Chapter 5.3 on the result (the statistics of
69//! the singleton and Markowitz pivots are those of the sequence).
70//!
71//! ## Invariants
72//! (R1) R4 computes the Schur complement column of step `s` exactly as
73//! Algorithm L would (in a different order of the same operations), so
74//! with the same sequence `L U = P B Q` holds to rounding and (F1)–(F3)
75//! of Chapter 5.3 hold (checked by `check_invariants` after step L7 in
76//! debug builds and against the dense product in the tests).
77//! (R2) With the default `u_R = u`, the threshold test of R5 is the one
78//! Algorithm L applies to its bump pivots, so a sequence is replayed
79//! only when it would have been acceptable to Algorithm L for these
80//! values. [`crate::Lu::set_refactor_pivot_tol`] may lower `u_R`
81//! (never `u`, which Algorithm L keeps).
82//!
83//! ## The replay threshold (task L1.5b)
84//! A Markowitz search accepts the sparsest pivot that passes `u`, so many
85//! recorded pivots sit just above it: in L1.3, 30 of 109 bases (93 Netlib
86//! optimal bases and 16 unsymmetric Harwell–Boeing matrices), with every
87//! value perturbed by an independent ±1 %, fell back on the first replay.
88//! Measured in L1.5b on the same 109, first replay of `B₂` with the
89//! sequence of `B₁`:
90//!
91//! | `u_R` | fallbacks | replays with a residual > 10× the fresh one |
92//! |---|---|---|
93//! | `u = 10⁻²` (default) | 30 | 0 |
94//! | `5·10⁻³` | 19 | 0 |
95//! | `10⁻³` | 9 | 0 |
96//! | `10⁻⁴` | 2 | 2 (orsirr_1 ×43, degen3 ×290) |
97//!
98//! (residual `‖B x − b‖_∞ / (‖B‖_∞‖x‖_∞ + ‖b‖_∞)` for `b = B·1`). The
99//! default stays `u`, which keeps (R2); `u_R = u/10` is the measured
100//! compromise for a caller that replays sequences over drifting values
101//! (the simplex method does not replay yet: integration pending, D-0091
102//! (a)).
103//! (R3) A [`SymbolicLu`] is recorded after every successful factorization
104//! (Algorithm L or R) and dropped after a failed one; its two arrays
105//! are permutations of `0..m` (`debug_assert` in the tests).
106//!
107//! ## Complexity
108//! R2–R6 cost `O(nnz(B) + flops)` — the flops of the elimination itself,
109//! with no count lists, no search and no linked files. Step L7 is shared.
110//!
111//! ## References
112//! Gilbert & Peierls, "Sparse partial pivoting in time proportional to
113//! arithmetic operations", SIAM J. Sci. Stat. Comput. 9(5), 1988; Davis &
114//! Palamadai Natarajan, "Algorithm 907: KLU", ACM TOMS 37(3), 2010
115//! (refactorization with the previous pivots); Davis, "Algorithm 832:
116//! UMFPACK V4.3", ACM TOMS 30(2), 2004 (symbolic and numeric phases);
117//! Suhl & Suhl (1990); the contract of the crate (`SymbolicLu`,
118//! *Divergences*).
119
120use crate::basis::ColumnSource;
121use crate::error::LuError;
122use crate::factor::{Elim, LuOptions, idx32};
123use crate::real::{Real, is_exact_zero, is_zero, lt};
124use crate::solve::NO_ETA;
125use crate::store::NIL;
126use crate::update::BasisUpdate;
127use crate::{Lu, LuFactor};
128
129/// The reusable part of a factorization: its pivot sequence (Chapter
130/// 5.12), consumed by [`crate::LuFactor::refactorize_same_pattern`].
131#[derive(Clone, Debug, Default, PartialEq, Eq)]
132pub struct SymbolicLu {
133 /// `p_s`: the pivot row of step `s`.
134 pub pivot_rows: Vec<u32>,
135 /// `q_s`: the pivot position (column of `B`) of step `s`.
136 pub pivot_cols: Vec<u32>,
137 /// The number `σ` of leading steps that were singleton pivots of the
138 /// triangular phase (forced; Algorithm R applies no relative test to
139 /// them).
140 pub singletons: usize,
141 /// `nnz(L)` the sequence produced last time.
142 pub nnz_l: usize,
143 /// `nnz(U)` (diagonal included) the sequence produced last time.
144 pub nnz_u: usize,
145}
146
147impl SymbolicLu {
148 /// The order `m` of the basis the sequence belongs to.
149 #[inline]
150 pub fn m(&self) -> usize {
151 self.pivot_rows.len()
152 }
153}
154
155impl<T: Real, U: BasisUpdate<T>> Lu<T, U> {
156 /// [`LuFactor::refactorize_same_pattern`]: Algorithm R, or Algorithm L
157 /// as the fallback.
158 pub(crate) fn refactorize_impl<C: ColumnSource<T>>(&mut self, cols: &C) -> Result<(), LuError> {
159 // R1.
160 let m = cols.m();
161 if self.symbolic.as_ref().is_some_and(|s| s.m() == m) {
162 self.factors.valid = false;
163 self.factors.spike_valid = false;
164 cols.validate()?;
165 let sym = self.symbolic.take().expect("checked above");
166 let prev = self.factors.stats;
167 let rel_tol = self.refactor_pivot_tol.unwrap_or(self.opts.rel_pivot_tol);
168 let replay = eliminate_fixed(cols, &sym, &self.opts, rel_tol);
169 self.symbolic = Some(sym);
170 if let Some(mut e) = replay {
171 // R7.
172 e.col_singletons = prev.col_singletons;
173 e.row_singletons = prev.row_singletons;
174 e.markowitz_pivots = prev.markowitz_pivots;
175 self.factors.m = m;
176 let done = self.finish(e);
177 debug_assert!(done.is_ok(), "Algorithm R never reports dead columns");
178 self.factors.stats.symbolic_reuses += 1;
179 return done;
180 }
181 }
182 self.factors.stats.symbolic_fallbacks += 1;
183 self.factorize(cols)
184 }
185}
186
187/// Steps R2–R6; `None` when a pivot is refused (R5) or the sequence is
188/// inconsistent.
189#[allow(clippy::too_many_lines)] // one step per block, as in the chapter
190fn eliminate_fixed<T: Real, C: ColumnSource<T>>(
191 cols: &C,
192 sym: &SymbolicLu,
193 opts: &LuOptions,
194 rel_tol: f64,
195) -> Option<Elim<T>> {
196 let m = cols.m();
197 let abs_tol = T::from_f64(opts.abs_pivot_tol);
198 let rel_tol = T::from_f64(rel_tol);
199 let drop_tol = T::from_f64(opts.drop_tol);
200 let mut e = Elim {
201 nnz_basis: 0,
202 max_basis: T::ZERO,
203 col_singletons: 0,
204 row_singletons: 0,
205 markowitz_pivots: 0,
206 step_row: sym.pivot_rows.clone(),
207 step_col: sym.pivot_cols.clone(),
208 diag: vec![T::ZERO; m],
209 l_start: vec![0],
210 l_pivot: Vec::new(),
211 l_index: Vec::new(),
212 l_value: Vec::new(),
213 u_trip: Vec::with_capacity(sym.nnz_u.saturating_sub(m)),
214 dead: Vec::new(),
215 };
216 e.l_index.reserve(sym.nnz_l);
217 e.l_value.reserve(sym.nnz_l);
218 let mut row_step = vec![NIL; m];
219 let mut eta_of_row = vec![NO_ETA; m];
220 let mut x = vec![T::ZERO; m];
221 let mut in_pat = vec![NIL; m];
222 let mut done = vec![NIL; m];
223 let mut pat: Vec<u32> = Vec::new();
224 let mut post: Vec<u32> = Vec::new();
225 let mut stack: Vec<(u32, usize)> = Vec::new();
226 for s in 0..m {
227 let (p, q) = (sym.pivot_rows[s] as usize, sym.pivot_cols[s] as usize);
228 if p >= m || q >= m || row_step[p] != NIL {
229 return None;
230 }
231 // R2. Scatter.
232 pat.clear();
233 cols.for_each_entry(q, |i, v| {
234 let iu = i as usize;
235 if in_pat[iu] != s {
236 in_pat[iu] = s;
237 pat.push(i);
238 }
239 x[iu] += v;
240 e.nnz_basis += 1;
241 e.max_basis = e.max_basis.max(v.abs());
242 });
243 // R3. Reach in G_L, by depth-first search from every seed.
244 post.clear();
245 let eta_start = |r: usize, eta_of_row: &[u32], l_start: &[usize]| match eta_of_row[r] {
246 NO_ETA => 0,
247 t => l_start[t as usize],
248 };
249 for t in 0..pat.len() {
250 let r0 = pat[t] as usize;
251 if done[r0] == s {
252 continue;
253 }
254 done[r0] = s;
255 stack.push((idx32(r0), eta_start(r0, &eta_of_row, &e.l_start)));
256 while let Some(top) = stack.last_mut() {
257 let r = top.0 as usize;
258 let eta = eta_of_row[r];
259 if eta != NO_ETA && top.1 < e.l_start[eta as usize + 1] {
260 let k = e.l_index[top.1];
261 top.1 += 1;
262 let ku = k as usize;
263 if done[ku] != s {
264 done[ku] = s;
265 if in_pat[ku] != s {
266 in_pat[ku] = s;
267 pat.push(k);
268 }
269 stack.push((k, eta_start(ku, &eta_of_row, &e.l_start)));
270 }
271 } else {
272 stack.pop();
273 if eta != NO_ETA {
274 post.push(idx32(r));
275 }
276 }
277 }
278 }
279 // R4. Solve with L in topological order.
280 for &r in post.iter().rev() {
281 let r = r as usize;
282 let xr = x[r];
283 if is_exact_zero(xr) {
284 continue;
285 }
286 let t = eta_of_row[r] as usize;
287 for k in e.l_start[t]..e.l_start[t + 1] {
288 let i = e.l_index[k] as usize;
289 x[i] -= e.l_value[k] * xr;
290 }
291 }
292 // R5. Threshold test.
293 let xp = x[p];
294 let gamma = pat
295 .iter()
296 .filter(|&&i| row_step[i as usize] == NIL)
297 .fold(T::ZERO, |g, &i| g.max(x[i as usize].abs()));
298 let refused =
299 !lt(abs_tol, xp.abs()) || (s >= sym.singletons && lt(xp.abs(), rel_tol * gamma));
300 if refused {
301 return None;
302 }
303 // R6. Record U, the diagonal and L; clear x.
304 let q32 = idx32(q);
305 e.diag[p] = xp;
306 let mut any = false;
307 for &i in &pat {
308 let iu = i as usize;
309 let v = x[iu];
310 x[iu] = T::ZERO;
311 if is_zero(v, drop_tol) || iu == p {
312 continue;
313 }
314 if row_step[iu] == NIL {
315 e.l_index.push(i);
316 e.l_value.push(v / xp);
317 any = true;
318 } else {
319 e.u_trip.push((i, q32, v));
320 }
321 }
322 if any {
323 eta_of_row[p] = idx32(e.l_pivot.len());
324 e.l_pivot.push(idx32(p));
325 e.l_start.push(e.l_index.len());
326 }
327 row_step[p] = s;
328 }
329 Some(e)
330}