Skip to main content

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}