Skip to main content

xingo_sparse/
ordering.rs

1//! # Chapter 5.10 — Fill-reducing orderings: [`Natural`], [`Amd`], [`Colamd`]
2//!
3//! *New with task L1.3 (PLAN.md trilha L; D-0080, decision D10: the
4//! orderings are our own from v0.1, no C, no GPL/LGPL).*
5//!
6//! ## Purpose
7//! The cost of a sparse factorization is decided before the first flop, by
8//! the order of elimination. An [`Ordering`] looks at a [`Pattern`]
9//! (Chapter 5.9) and returns a [`Perm`]; it never sees values. Two targets
10//! ([`OrderingTarget`]):
11//!
12//! * [`OrderingTarget::Symmetric`] — a symmetric order `P (S + Sᵀ) Pᵀ` for
13//!   Cholesky or `LDLᵀ` (the KKT systems of the interior-point method,
14//!   L1.5): the permutation of the rows *and* columns;
15//! * [`OrderingTarget::Columns`] — a column order `S Q` for an LU with row
16//!   pivoting (or a QR): it reduces the fill of the Cholesky factor of
17//!   `QᵀSᵀSQ`, which bounds the `U` of every row-pivoted LU of `S Q`
18//!   (George & Ng 1987), without forming `SᵀS`.
19//!
20//! Three orderings, stateless policies:
21//!
22//! * [`Natural`] — the identity (the reference of every table);
23//! * [`Amd`] — approximate minimum degree on the graph of `S + Sᵀ`
24//!   (Amestoy, Davis & Duff 1996), with aggressive absorption, mass
25//!   elimination, supervariables and dense-row detection; for the
26//!   `Columns` target it orders the graph of `SᵀS`, formed explicitly;
27//! * [`Colamd`] — column approximate minimum degree (Davis, Gilbert,
28//!   Larimore & Ng 2004): the same process on the quotient graph of `SᵀS`
29//!   started from the rows of `S`, never forming `SᵀS`; for the `Symmetric`
30//!   target, the SYMAMD construction (every off-diagonal pair `{i, j}` of
31//!   `S + Sᵀ` is a row with two entries, whose `MᵀM` has the pattern of
32//!   `S + Sᵀ`).
33//!
34//! Both run Algorithm Q of Chapter 5.11; this chapter is their setup.
35//!
36//! ## Notation
37//! `S` is `m × n`; `r_i` and `c_j` are its row and column counts.
38//! `κ(α, N) = max(16, ⌊α √N⌋)` is the *dense threshold* (SuiteSparse's
39//! rule); a negative `α` disables dense detection. Excluded (dense or
40//! empty) indices are ordered last, in increasing index order.
41//!
42//! ## Algorithm A (AMD)
43//! A1. [Graph.] `G ← S + Sᵀ` without its diagonal (Algorithm S of Chapter
44//!     5.9; for `Columns`, the graph of `SᵀS` by Algorithm G). An error
45//!     unless `S` is square for `Symmetric`.
46//! A2. [Dense rows.] With `δ = κ(dense, n)` (`dense` default 10), every
47//!     node of degree `> δ` is excluded: ordering it in the middle would
48//!     cost as much as it fills, and its presence would spoil every
49//!     degree it touches.
50//! A3. [Order.] Algorithm Q with `A_i = G`'s adjacency, no initial
51//!     elements, the bound `min(d̄_i, δ_i)`, AMD's conventions (largest
52//!     index first among equal degrees, the postorder Q8 as output);
53//!     aggressive absorption as asked (default on).
54//! A4. Append the excluded nodes. Return the [`Perm`] (`fwd` = pivot order).
55//!
56//! ## Algorithm C (COLAMD)
57//! C1. [Dense columns.] With `κ_c = κ(dense_col, min(m, n))` (default
58//!     `dense_col = 10`), exclude every column with `c_j > κ_c`.
59//! C2. [Dense rows.] With `κ_r = κ(dense_row, n)` (default 10), drop every
60//!     row with more than `κ_r` entries in non-excluded columns: a dense row
61//!     makes `SᵀS` dense and says nothing useful about the order.
62//! C3. [Null columns.] Exclude every column left without a row (they are
63//!     ordered last, before the dense columns, as COLAMD does).
64//! C4. [Order.] Algorithm Q with no `A_i`, the surviving rows as initial
65//!     elements, COLAMD's score `δ_i` (no `min` with the previous score) and
66//!     COLAMD's conventions (smallest index first among ties, initial rows
67//!     before pivot rows in Q3, the pivot order Q8′ as output); aggressive
68//!     absorption on.
69//! C5. Append the null columns, then the dense ones.
70//!
71//! For `Symmetric` (SYMAMD): exclude the nodes of `S + Sᵀ` of degree
72//! `> κ(dense_col, n)`; every edge `{i, j}` (`i < j`) between the others is
73//! an initial element `{i, j}`; then C4–C5 with the excluded nodes.
74//!
75//! ## Invariants
76//! (O1) Every ordering returns a [`Perm`] of `n` (the number of columns)
77//!      satisfying (P1) of Chapter 5.9, and fails only on an input error
78//!      (a non-square pattern for `Symmetric`, (P2) violated).
79//! (O2) [`Natural`] is the identity; the others are deterministic
80//!      functions of the pattern.
81//!
82//! ## Defaults and their source
83//! `Amd { dense: None (= 10), aggressive: true }` and `Colamd { dense_row:
84//! None (= 10), dense_col: None (= 10) }` are SuiteSparse's `AMD_DENSE`,
85//! `AMD_AGGRESSIVE`, `COLAMD_DENSE_ROW` and `COLAMD_DENSE_COL` defaults
86//! (AMD 2.x and COLAMD 2.x user guides).
87//!
88//! ## References
89//! Amestoy, Davis & Duff, SIAM J. Matrix Anal. Appl. 17(4), 1996, and
90//! Algorithm 837 (AMD), ACM TOMS 30(3), 2004; Davis, Gilbert, Larimore &
91//! Ng, "A column approximate minimum degree ordering algorithm" and
92//! Algorithm 836 (COLAMD), ACM TOMS 30(3), 2004; George & Ng (1987); the
93//! contract of the crate (`Ordering`, `OrderingTarget`, `Natural`, `Amd`,
94//! `Colamd`).
95
96use crate::factor::count_f64;
97use crate::perm::idx32;
98use crate::qgraph::{self, Input};
99use crate::real::lt;
100use crate::{Pattern, Perm, SparseError};
101
102/// What an ordering is asked to reduce fill for.
103#[derive(Clone, Copy, Debug, PartialEq, Eq)]
104pub enum OrderingTarget {
105    /// A symmetric order of a square pattern (Cholesky, `LDLᵀ`): rows and
106    /// columns are permuted alike.
107    Symmetric,
108    /// A column order for an LU with row pivoting (or a QR): the pattern
109    /// of `SᵀS`, without forming it (COLAMD).
110    Columns,
111}
112
113/// Fill-reducing orderings. Implementations are stateless policies
114/// (invariants (O1)–(O2)).
115pub trait Ordering {
116    /// A permutation of the columns of `pattern` (for `Symmetric`, of its
117    /// rows and columns alike).
118    fn order(&self, pattern: &Pattern, target: OrderingTarget) -> Result<Perm, SparseError>;
119    /// A short name for logs and tables.
120    fn name(&self) -> &'static str;
121}
122
123/// The identity ordering.
124#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
125pub struct Natural;
126
127/// Approximate minimum degree (Amestoy, Davis & Duff 1996), Algorithm A:
128/// quotient graph with element absorption, approximate external degrees,
129/// mass elimination of indistinguishable nodes and dense-row detection.
130/// Our own implementation (D10); SuiteSparse AMD is the oracle in tests.
131#[derive(Clone, Copy, Debug, PartialEq)]
132pub struct Amd {
133    /// Nodes of degree above `max(16, dense · √n)` are ordered last
134    /// (`None`: AMD's default `10`; negative: no dense detection).
135    pub dense: Option<f64>,
136    /// Aggressive absorption of elements (AMD's default: on).
137    pub aggressive: bool,
138}
139
140impl Default for Amd {
141    fn default() -> Self {
142        Self {
143            dense: None,
144            aggressive: true,
145        }
146    }
147}
148
149/// Column approximate minimum degree (Davis, Gilbert, Larimore & Ng 2004),
150/// Algorithm C: the AMD idea applied to the pattern of `SᵀS` without
151/// forming it, for an LU with row pivoting. Our own implementation (D10).
152#[derive(Clone, Copy, Debug, Default, PartialEq)]
153pub struct Colamd {
154    /// Rows with more than `max(16, dense_row · √n)` entries are ignored
155    /// (`None`: COLAMD's default `10`; negative: none is).
156    pub dense_row: Option<f64>,
157    /// Columns with more than `max(16, dense_col · √min(m, n))` entries
158    /// are ordered last (`None`: COLAMD's default `10`; negative: none
159    /// is).
160    pub dense_col: Option<f64>,
161}
162
163/// The default dense knob of AMD and COLAMD.
164const DENSE_DEFAULT: f64 = 10.0;
165
166/// The least dense threshold (SuiteSparse's `16`).
167const DENSE_MIN: usize = 16;
168
169/// `κ(α, N) = max(16, ⌊α √N⌋)`; `usize::MAX` (never dense) for `α < 0`.
170fn dense_threshold(alpha: Option<f64>, big_n: usize) -> usize {
171    let a = alpha.unwrap_or(DENSE_DEFAULT);
172    if lt(a, 0.0) {
173        return usize::MAX;
174    }
175    floor_usize(a * count_f64(big_n).sqrt()).max(DENSE_MIN)
176}
177
178/// `⌊x⌋` for a finite `x ≥ 0` (saturating, as `as` is).
179#[inline]
180#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)] // x ≥ 0, saturating
181fn floor_usize(x: f64) -> usize {
182    x as usize
183}
184
185/// A square check for the `Symmetric` target.
186fn square(pattern: &Pattern) -> Result<usize, SparseError> {
187    let n = pattern.n_cols();
188    if pattern.n_rows == n {
189        Ok(n)
190    } else {
191        Err(SparseError::Dimension {
192            what: "pattern (a symmetric ordering needs a square one)",
193            expected: n,
194            found: pattern.n_rows,
195        })
196    }
197}
198
199/// Compressed lists: `idx[ptr[i]..ptr[i + 1]]` is list `i`.
200type Lists = (Vec<usize>, Vec<u32>);
201
202/// The off-diagonal adjacency of a symmetric pattern.
203fn adjacency(g: &Pattern) -> Lists {
204    let n = g.n_cols();
205    let mut ptr = Vec::with_capacity(n + 1);
206    let mut idx = Vec::with_capacity(g.nnz());
207    ptr.push(0);
208    for j in 0..n {
209        idx.extend(g.col(j).iter().copied().filter(|&i| i as usize != j));
210        ptr.push(idx.len());
211    }
212    (ptr, idx)
213}
214
215/// The off-diagonal adjacency of `S + Sᵀ` for a square `S` (Algorithm S of
216/// Chapter 5.9 straight into the lists the engine takes: one transpose
217/// and one merge per column, no intermediate pattern).
218fn sym_adjacency(s: &Pattern) -> Lists {
219    let t = s.transpose();
220    let n = s.n_cols();
221    let mut ptr = Vec::with_capacity(n + 1);
222    let mut out = Vec::with_capacity(2 * s.nnz());
223    ptr.push(0);
224    for j in 0..n {
225        let (a, b) = (s.col(j), t.col(j));
226        let jj = idx32(j);
227        let (mut p, mut q) = (0, 0);
228        while p < a.len() && q < b.len() {
229            let (x, y) = (a[p], b[q]);
230            let next = x.min(y);
231            p += usize::from(x == next);
232            q += usize::from(y == next);
233            if next != jj {
234                out.push(next);
235            }
236        }
237        out.extend(a[p..].iter().chain(&b[q..]).copied().filter(|&i| i != jj));
238        ptr.push(out.len());
239    }
240    (ptr, out)
241}
242
243/// No lists at all (`n` empty ones).
244fn no_lists(n: usize) -> Lists {
245    (vec![0; n + 1], Vec::new())
246}
247
248/// `fwd` = `ordered`, then the excluded indices of each group in order.
249fn finish(n: usize, mut fwd: Vec<u32>, groups: &[&[bool]]) -> Perm {
250    for g in groups {
251        fwd.extend((0..n).filter(|&j| g[j]).map(idx32));
252    }
253    debug_assert_eq!(fwd.len(), n);
254    let p = Perm::from_fwd(fwd).expect("(O1): the ordering is a permutation");
255    debug_assert_eq!(p.check_invariants(), Ok(()));
256    p
257}
258
259impl Ordering for Natural {
260    fn order(&self, pattern: &Pattern, target: OrderingTarget) -> Result<Perm, SparseError> {
261        pattern.check_invariants()?;
262        let n = match target {
263            OrderingTarget::Symmetric => square(pattern)?,
264            OrderingTarget::Columns => pattern.n_cols(),
265        };
266        Ok(Perm::identity(n))
267    }
268    fn name(&self) -> &'static str {
269        "natural"
270    }
271}
272
273impl Ordering for Amd {
274    fn order(&self, pattern: &Pattern, target: OrderingTarget) -> Result<Perm, SparseError> {
275        pattern.check_invariants()?;
276        // A1.
277        let (adj_ptr, adj_idx) = match target {
278            OrderingTarget::Symmetric => {
279                square(pattern)?;
280                sym_adjacency(pattern)
281            }
282            OrderingTarget::Columns => adjacency(&pattern.ata()),
283        };
284        let n = adj_ptr.len() - 1;
285        // A2.
286        let delta = dense_threshold(self.dense, n);
287        let excluded: Vec<bool> = (0..n)
288            .map(|i| adj_ptr[i + 1] - adj_ptr[i] > delta)
289            .collect();
290        // A3.
291        let (elem_ptr, elem_idx) = no_lists(0);
292        let fwd = qgraph::order(Input {
293            n,
294            adj_ptr,
295            adj_idx,
296            elem_ptr,
297            elem_idx,
298            excluded: excluded.clone(),
299            aggressive: self.aggressive,
300            previous_degree: true,
301            column_order: false,
302        });
303        // A4.
304        Ok(finish(n, fwd, &[excluded.as_slice()]))
305    }
306    fn name(&self) -> &'static str {
307        "amd"
308    }
309}
310
311impl Ordering for Colamd {
312    fn order(&self, pattern: &Pattern, target: OrderingTarget) -> Result<Perm, SparseError> {
313        pattern.check_invariants()?;
314        match target {
315            OrderingTarget::Columns => Ok(self.columns(pattern)),
316            OrderingTarget::Symmetric => {
317                square(pattern)?;
318                Ok(self.symmetric(&pattern.symmetric()?))
319            }
320        }
321    }
322    fn name(&self) -> &'static str {
323        "colamd"
324    }
325}
326
327impl Colamd {
328    /// Algorithm C.
329    fn columns(self, s: &Pattern) -> Perm {
330        let (m, n) = (s.n_rows, s.n_cols());
331        // C1.
332        let kc = dense_threshold(self.dense_col, m.min(n));
333        let dense: Vec<bool> = (0..n).map(|j| s.col(j).len() > kc).collect();
334        // C2.
335        let t = s.transpose();
336        let kr = dense_threshold(self.dense_row, n);
337        let mut elem_ptr = Vec::with_capacity(m + 1);
338        let mut elem_idx = Vec::with_capacity(s.nnz());
339        elem_ptr.push(0);
340        let mut has_row = vec![false; n];
341        for i in 0..m {
342            let start = elem_idx.len();
343            elem_idx.extend(t.col(i).iter().copied().filter(|&j| !dense[j as usize]));
344            let row = &elem_idx[start..];
345            if row.is_empty() || row.len() > kr {
346                elem_idx.truncate(start);
347                continue;
348            }
349            for &j in row {
350                has_row[j as usize] = true;
351            }
352            elem_ptr.push(elem_idx.len());
353        }
354        // C3.
355        let null: Vec<bool> = (0..n).map(|j| !dense[j] && !has_row[j]).collect();
356        let excluded: Vec<bool> = (0..n).map(|j| dense[j] || null[j]).collect();
357        // C4.
358        let (adj_ptr, adj_idx) = no_lists(n);
359        let fwd = qgraph::order(Input {
360            n,
361            adj_ptr,
362            adj_idx,
363            elem_ptr,
364            elem_idx,
365            excluded,
366            aggressive: true,
367            previous_degree: false,
368            column_order: true,
369        });
370        // C5.
371        finish(n, fwd, &[null.as_slice(), dense.as_slice()])
372    }
373
374    /// SYMAMD: Algorithm C on the edge rows of the symmetric pattern `g`.
375    fn symmetric(self, g: &Pattern) -> Perm {
376        let n = g.n_cols();
377        let (aptr, aidx) = adjacency(g);
378        let kc = dense_threshold(self.dense_col, n);
379        let dense: Vec<bool> = (0..n).map(|j| aptr[j + 1] - aptr[j] > kc).collect();
380        let mut elem_ptr = vec![0_usize];
381        let mut elem_idx = Vec::new();
382        for j in 0..n {
383            if dense[j] {
384                continue;
385            }
386            for &i in &aidx[aptr[j]..aptr[j + 1]] {
387                if (i as usize) < j && !dense[i as usize] {
388                    elem_idx.push(i);
389                    elem_idx.push(idx32(j));
390                    elem_ptr.push(elem_idx.len());
391                }
392            }
393        }
394        let (adj_ptr, adj_idx) = no_lists(n);
395        let fwd = qgraph::order(Input {
396            n,
397            adj_ptr,
398            adj_idx,
399            elem_ptr,
400            elem_idx,
401            excluded: dense.clone(),
402            aggressive: true,
403            previous_degree: false,
404            column_order: true,
405        });
406        finish(n, fwd, &[dense.as_slice()])
407    }
408}
409
410#[cfg(test)]
411mod tests {
412    use super::*;
413    use proptest::prelude::*;
414
415    /// xorshift64*.
416    struct Rng(u64);
417    impl Rng {
418        fn new(seed: u64) -> Self {
419            Self(seed | 1)
420        }
421        fn below(&mut self, n: usize) -> usize {
422            self.0 ^= self.0 >> 12;
423            self.0 ^= self.0 << 25;
424            self.0 ^= self.0 >> 27;
425            usize::try_from(self.0.wrapping_mul(0x2545_F491_4F6C_DD1D) % (n as u64)).unwrap()
426        }
427        fn shuffle(&mut self, v: &mut [u32]) {
428            for i in (1..v.len()).rev() {
429                let j = self.below(i + 1);
430                v.swap(i, j);
431            }
432        }
433    }
434
435    /// A pattern from `(i, j)` pairs (duplicates collapse).
436    fn pat(m: usize, n: usize, e: &[(usize, usize)]) -> Pattern {
437        let mut cols: Vec<Vec<u32>> = vec![Vec::new(); n];
438        for &(i, j) in e {
439            cols[j].push(idx32(i));
440        }
441        let mut col_ptr = vec![0];
442        let mut row_idx = Vec::new();
443        for mut c in cols {
444            c.sort_unstable();
445            c.dedup();
446            row_idx.extend(c);
447            col_ptr.push(row_idx.len());
448        }
449        Pattern::from_raw_parts(m, col_ptr, row_idx).unwrap()
450    }
451
452    /// The symmetric pattern of an undirected graph given by its edges,
453    /// relabelled by `label`.
454    fn graph(n: usize, edges: &[(usize, usize)], label: &[u32]) -> Pattern {
455        let mut e: Vec<(usize, usize)> = (0..n).map(|i| (i, i)).collect();
456        for &(a, b) in edges {
457            let (a, b) = (label[a] as usize, label[b] as usize);
458            e.push((a, b));
459            e.push((b, a));
460        }
461        pat(n, n, &e)
462    }
463
464    fn random_label(rng: &mut Rng, n: usize) -> Vec<u32> {
465        let mut l: Vec<u32> = (0..n).map(idx32).collect();
466        rng.shuffle(&mut l);
467        l
468    }
469
470    /// A random tree on `n` nodes.
471    fn tree_edges(rng: &mut Rng, n: usize) -> Vec<(usize, usize)> {
472        (1..n).map(|i| (i, rng.below(i))).collect()
473    }
474
475    /// The `k × k` grid graph in its natural (row-major) numbering.
476    fn grid_edges(k: usize) -> Vec<(usize, usize)> {
477        let mut e = Vec::new();
478        for r in 0..k {
479            for c in 0..k {
480                let v = r * k + c;
481                if c + 1 < k {
482                    e.push((v, v + 1));
483                }
484                if r + 1 < k {
485                    e.push((v, v + k));
486                }
487            }
488        }
489        e
490    }
491
492    /// The edge–node incidence pattern (`|E| × n`): its `MᵀM` is the graph.
493    fn incidence(n: usize, edges: &[(usize, usize)], label: &[u32]) -> Pattern {
494        let mut e = Vec::new();
495        for (r, &(a, b)) in edges.iter().enumerate() {
496            e.push((r, label[a] as usize));
497            e.push((r, label[b] as usize));
498        }
499        pat(edges.len().max(1), n, &e)
500    }
501
502    fn fill(s: &Pattern, p: &Perm) -> usize {
503        s.cholesky_nnz(p).unwrap()
504    }
505
506    // -----------------------------------------------------------------
507    // Naive references.
508    // -----------------------------------------------------------------
509
510    /// Exact minimum degree on the explicit elimination graph (ties: the
511    /// smallest index) — the classical algorithm AMD approximates.
512    fn exact_minimum_degree(s: &Pattern) -> Perm {
513        let n = s.n_cols();
514        let g = s.symmetric().unwrap();
515        let mut adj: Vec<Vec<bool>> = vec![vec![false; n]; n];
516        // `g` is symmetric: column j lists the neighbours of j.
517        for (j, row) in adj.iter_mut().enumerate() {
518            for &i in g.col(j) {
519                if i as usize != j {
520                    row[i as usize] = true;
521                }
522            }
523        }
524        let mut alive = vec![true; n];
525        let mut fwd = Vec::with_capacity(n);
526        for _ in 0..n {
527            let degree = |v: usize| (0..n).filter(|&w| alive[w] && adj[v][w]).count();
528            let p = (0..n)
529                .filter(|&v| alive[v])
530                .min_by_key(|&v| (degree(v), v))
531                .unwrap();
532            let nb: Vec<usize> = (0..n).filter(|&w| alive[w] && adj[p][w]).collect();
533            for &a in &nb {
534                for &b in &nb {
535                    if a != b {
536                        adj[a][b] = true;
537                    }
538                }
539            }
540            alive[p] = false;
541            fwd.push(idx32(p));
542        }
543        Perm::from_fwd(fwd).unwrap()
544    }
545
546    /// The least fill over all `n!` orders (brute force, `n ≤ 7`).
547    fn optimal_fill(s: &Pattern) -> usize {
548        fn rec(k: usize, v: &mut Vec<u32>, s: &Pattern, best: &mut usize) {
549            if k == v.len() {
550                let f = s.cholesky_nnz(&Perm::from_fwd(v.clone()).unwrap()).unwrap();
551                *best = (*best).min(f);
552                return;
553            }
554            for i in k..v.len() {
555                v.swap(k, i);
556                rec(k + 1, v, s, best);
557                v.swap(k, i);
558            }
559        }
560        let mut v: Vec<u32> = (0..s.n_cols()).map(idx32).collect();
561        let mut best = usize::MAX;
562        rec(0, &mut v, s, &mut best);
563        best
564    }
565
566    fn random_graph(rng: &mut Rng, n: usize, pct: usize) -> Pattern {
567        let mut e = Vec::new();
568        for a in 0..n {
569            for b in a + 1..n {
570                if rng.below(100) < pct {
571                    e.push((a, b));
572                }
573            }
574        }
575        let id: Vec<u32> = (0..n).map(idx32).collect();
576        graph(n, &e, &id)
577    }
578
579    // -----------------------------------------------------------------
580    // Examples and properties.
581    // -----------------------------------------------------------------
582
583    #[test]
584    fn natural_and_errors() {
585        let s = pat(2, 3, &[(0, 0), (1, 2)]);
586        assert!(
587            Natural
588                .order(&s, OrderingTarget::Columns)
589                .unwrap()
590                .is_identity()
591        );
592        assert!(Natural.order(&s, OrderingTarget::Symmetric).is_err());
593        assert!(Amd::default().order(&s, OrderingTarget::Symmetric).is_err());
594        assert!(
595            Colamd::default()
596                .order(&s, OrderingTarget::Symmetric)
597                .is_err()
598        );
599        assert_eq!(
600            Amd::default()
601                .order(&s, OrderingTarget::Columns)
602                .unwrap()
603                .len(),
604            3
605        );
606        assert_eq!(
607            Colamd::default()
608                .order(&s, OrderingTarget::Columns)
609                .unwrap()
610                .len(),
611            3
612        );
613        let empty = Pattern::empty(0, 0);
614        for o in [
615            &Natural as &dyn Ordering,
616            &Amd::default(),
617            &Colamd::default(),
618        ] {
619            assert!(
620                o.order(&empty, OrderingTarget::Symmetric)
621                    .unwrap()
622                    .is_empty()
623            );
624            assert_ne!(o.name(), "");
625        }
626        assert_eq!(dense_threshold(None, 100), 100);
627        assert_eq!(dense_threshold(Some(1.0), 4), DENSE_MIN);
628        assert_eq!(dense_threshold(Some(-1.0), 4), usize::MAX);
629    }
630
631    /// A path long enough that the flag of step Q4 (`n + 1` per pivot, in
632    /// `u32`) restarts (Chapter 5.11, "Constant factors"): the order is
633    /// still perfect (`nnz(L) = 2n − 1`).
634    #[test]
635    fn long_path_restarts_the_flag_and_stays_perfect() {
636        let n = 100_000;
637        let edges: Vec<(usize, usize)> = (1..n).map(|i| (i, i - 1)).collect();
638        let s = pat(n, n, &edges).symmetric().unwrap();
639        for o in [&Amd::default() as &dyn Ordering, &Colamd::default()] {
640            let p = o.order(&s, OrderingTarget::Symmetric).unwrap();
641            assert_eq!(s.cholesky_nnz(&p).unwrap(), 2 * n - 1, "{}", o.name());
642        }
643    }
644
645    /// Example 5.10.1: the arrowhead with its hub first fills completely
646    /// in the natural order; AMD and COLAMD order the hub last (by degree —
647    /// mass-eliminated with the last leaf — for small `n`, as a dense node
648    /// for large `n`) and fill nothing.
649    #[test]
650    fn ex_5_10_1_arrowhead() {
651        for n in [8_usize, 30, 400] {
652            let edges: Vec<(usize, usize)> = (1..n).map(|i| (0, i)).collect();
653            let id: Vec<u32> = (0..n).map(idx32).collect();
654            let s = graph(n, &edges, &id);
655            let nat = fill(&s, &Natural.order(&s, OrderingTarget::Symmetric).unwrap());
656            assert_eq!(nat, n * (n + 1) / 2);
657            for o in [&Amd::default() as &dyn Ordering, &Colamd::default()] {
658                let p = o.order(&s, OrderingTarget::Symmetric).unwrap();
659                assert_eq!(fill(&s, &p), 2 * n - 1, "{} n = {n}", o.name());
660                // Last, or mass-eliminated with the last leaf (Q5).
661                assert!(
662                    p.inv[0] as usize + 2 >= n,
663                    "{}: hub at {}",
664                    o.name(),
665                    p.inv[0]
666                );
667            }
668            let m = incidence(n, &edges, &id);
669            let p = Colamd::default()
670                .order(&m, OrderingTarget::Columns)
671                .unwrap();
672            assert_eq!(fill(&s, &p), 2 * n - 1);
673        }
674    }
675
676    /// Example 5.10.2: on a `k × k` grid, AMD (on a random relabelling)
677    /// fills less than the natural band order.
678    #[test]
679    fn ex_5_10_2_grids_beat_the_band() {
680        let mut rng = Rng::new(7);
681        for k in [6_usize, 10, 20, 30] {
682            let n = k * k;
683            let e = grid_edges(k);
684            let id: Vec<u32> = (0..n).map(idx32).collect();
685            let band = fill(&graph(n, &e, &id), &Perm::identity(n));
686            let label = random_label(&mut rng, n);
687            let s = graph(n, &e, &label);
688            let amd = fill(
689                &s,
690                &Amd::default().order(&s, OrderingTarget::Symmetric).unwrap(),
691            );
692            let sym = fill(
693                &s,
694                &Colamd::default()
695                    .order(&s, OrderingTarget::Symmetric)
696                    .unwrap(),
697            );
698            let m = incidence(n, &e, &label);
699            let col = fill(
700                &s,
701                &Colamd::default()
702                    .order(&m, OrderingTarget::Columns)
703                    .unwrap(),
704            );
705            assert!(
706                amd <= band && sym <= band && col <= band,
707                "k {k}: band {band}, amd {amd}, symamd {sym}, colamd {col}"
708            );
709        }
710    }
711
712    /// Brute force: on every small random graph the fill of AMD is at
713    /// least the optimum (a check of the counter) and, summed over the
714    /// sample, within 10 % of exact minimum degree and of 1.25× the
715    /// optimum; the same for COLAMD on the incidence pattern.
716    #[test]
717    fn brute_force_against_minimum_degree_and_optimum() {
718        let mut rng = Rng::new(2026);
719        let (mut amd_s, mut col_s, mut md_s, mut opt_s) = (0, 0, 0, 0);
720        for case in 0..300 {
721            let n = 2 + case % 6;
722            let s = random_graph(&mut rng, n, 20 + case % 50);
723            let opt = optimal_fill(&s);
724            let amd = fill(
725                &s,
726                &Amd::default().order(&s, OrderingTarget::Symmetric).unwrap(),
727            );
728            let mut edges = Vec::new();
729            for j in 0..n {
730                for &i in s.col(j) {
731                    if (i as usize) < j {
732                        edges.push((i as usize, j));
733                    }
734                }
735            }
736            let id: Vec<u32> = (0..n).map(idx32).collect();
737            let m = incidence(n, &edges, &id);
738            let col = fill(
739                &s,
740                &Colamd::default()
741                    .order(&m, OrderingTarget::Columns)
742                    .unwrap(),
743            );
744            let md = fill(&s, &exact_minimum_degree(&s));
745            assert!(amd >= opt && col >= opt && md >= opt);
746            amd_s += amd;
747            col_s += col;
748            md_s += md;
749            opt_s += opt;
750        }
751        let r = |a: usize, b: usize| count_f64(a) / count_f64(b);
752        assert!(r(amd_s, md_s) <= 1.10, "AMD/MD {}", r(amd_s, md_s));
753        assert!(r(col_s, md_s) <= 1.10, "COLAMD/MD {}", r(col_s, md_s));
754        assert!(r(amd_s, opt_s) <= 1.25 && r(col_s, opt_s) <= 1.25);
755    }
756
757    /// Larger graphs: AMD within 10 % of exact minimum degree in total.
758    #[test]
759    fn amd_tracks_exact_minimum_degree() {
760        let mut rng = Rng::new(11);
761        let (mut amd_s, mut md_s) = (0, 0);
762        for case in 0..40 {
763            let n = 20 + case;
764            let s = random_graph(&mut rng, n, 3 + case % 8);
765            amd_s += fill(
766                &s,
767                &Amd::default().order(&s, OrderingTarget::Symmetric).unwrap(),
768            );
769            md_s += fill(&s, &exact_minimum_degree(&s));
770        }
771        assert!(
772            count_f64(amd_s) <= 1.10 * count_f64(md_s),
773            "AMD {amd_s} MD {md_s}"
774        );
775    }
776
777    proptest! {
778        /// (O1): every ordering is a bijection, for both targets, on random
779        /// rectangular patterns with empty and dense lines.
780        #[test]
781        fn orderings_are_permutations(m in 1_usize..40, n in 1_usize..40,
782                                      e in prop::collection::vec((0_usize..40, 0_usize..40), 0..300),
783                                      dense_line in 0_usize..3, knob in -1.0_f64..2.0) {
784            let mut e: Vec<(usize, usize)> = e.into_iter().map(|(i, j)| (i % m, j % n)).collect();
785            if dense_line == 1 {
786                e.extend((0..n).map(|j| (0, j)));
787            } else if dense_line == 2 {
788                e.extend((0..m).map(|i| (i, 0)));
789            }
790            let s = pat(m, n, &e);
791            let sq = pat(n, n, &e.iter().map(|&(i, j)| (i % n, j)).collect::<Vec<_>>());
792            let orderings: [&dyn Ordering; 5] = [
793                &Natural,
794                &Amd::default(),
795                &Amd { dense: Some(knob), aggressive: false },
796                &Colamd::default(),
797                &Colamd { dense_row: Some(knob), dense_col: Some(knob) },
798            ];
799            for o in orderings {
800                let p = o.order(&s, OrderingTarget::Columns).unwrap();
801                prop_assert_eq!(p.len(), n);
802                prop_assert!(p.check_invariants().is_ok());
803                let q = o.order(&sq, OrderingTarget::Symmetric).unwrap();
804                prop_assert_eq!(q.len(), n);
805                prop_assert!(q.check_invariants().is_ok());
806                prop_assert_eq!(o.order(&sq, OrderingTarget::Symmetric).unwrap(), q);
807            }
808        }
809
810        /// Trees (relabelled at random) are eliminated without fill by AMD
811        /// and SYMAMD, and COLAMD on their incidence pattern; the natural
812        /// order of the relabelled tree is never better.
813        #[test]
814        fn trees_have_no_fill(n in 1_usize..120, seed in any::<u64>()) {
815            let mut rng = Rng::new(seed);
816            let e = tree_edges(&mut rng, n);
817            let label = random_label(&mut rng, n);
818            let s = graph(n, &e, &label);
819            let none = 2 * n - 1;
820            prop_assert!(fill(&s, &Perm::identity(n)) >= none);
821            prop_assert_eq!(fill(&s, &Amd::default().order(&s, OrderingTarget::Symmetric).unwrap()), none);
822            prop_assert_eq!(fill(&s, &Colamd::default().order(&s, OrderingTarget::Symmetric).unwrap()), none);
823            let m = incidence(n, &e, &label);
824            prop_assert_eq!(fill(&s, &Colamd::default().order(&m, OrderingTarget::Columns).unwrap()), none);
825            prop_assert_eq!(fill(&s, &Amd::default().order(&m, OrderingTarget::Columns).unwrap()), none);
826        }
827
828        /// Structured matrices: a block-arrow (dense border of width `w`
829        /// first, then independent diagonal blocks) relabelled at random —
830        /// the orderings never fill more than the natural order of the
831        /// unrelabelled matrix, which puts the border first and so turns
832        /// all the blocks into one clique. (With one block the natural
833        /// order has no fill at all, and a minimum-degree tie can cost one
834        /// entry: the case is excluded, it is not a property; so are borders
835        /// whose nodes have no more neighbours than the block nodes.)
836        #[test]
837        fn block_arrows_beat_the_natural_order(blocks in 2_usize..8, size in 2_usize..6,
838                                               w in 1_usize..4, seed in any::<u64>()) {
839            // The block nodes must be the ones of least degree
840            // (`size − 1 + w < blocks · size`), else minimum degree may
841            // start on the border as the natural order does.
842            prop_assume!(size + w <= blocks * size);
843            let mut rng = Rng::new(seed);
844            let n = w + blocks * size;
845            let mut e = Vec::new();
846            for b in 0..blocks {
847                let base = w + b * size;
848                for x in 0..size {
849                    for y in x + 1..size {
850                        e.push((base + x, base + y));
851                    }
852                    for c in 0..w {
853                        e.push((c, base + x));
854                    }
855                }
856            }
857            let id: Vec<u32> = (0..n).map(idx32).collect();
858            let nat = fill(&graph(n, &e, &id), &Perm::identity(n));
859            let label = random_label(&mut rng, n);
860            let s = graph(n, &e, &label);
861            for o in [&Amd::default() as &dyn Ordering, &Colamd::default()] {
862                let f = fill(&s, &o.order(&s, OrderingTarget::Symmetric).unwrap());
863                prop_assert!(f <= nat, "{}: {} > natural {}", o.name(), f, nat);
864            }
865        }
866    }
867}