Skip to main content

xingo_sparse/
perm.rs

1//! # Chapter 5.9 — Permutations and sparsity patterns
2//!
3//! *New with task L1.3 (PLAN.md trilha L).*
4//!
5//! ## Purpose
6//! A fill-reducing ordering (Chapter 5.10) looks only at *where* the
7//! nonzeros of a matrix are, never at their values, and answers with a
8//! permutation. This chapter fixes both objects: [`Pattern`], the
9//! structure of a compressed matrix without its values, and [`Perm`], a
10//! permutation stored together with its inverse. It also measures what an
11//! ordering is for — the number of nonzeros of the Cholesky factor of the
12//! permuted pattern (Algorithm E) — which is the yardstick of every test
13//! and of the acceptance tables of the orderings.
14//!
15//! ## Notation
16//! A [`Pattern`] `S` with `n_rows = m` and `n = n_cols` columns stores, as
17//! a [`CscMatrix`] does, the row indices of column `j` in
18//! `row_idx[col_ptr[j]..col_ptr[j + 1]]`. A [`Perm`] `π` of `0..n` is the
19//! pair of arrays
20//!
21//! * `fwd[k] = i` — the *old* index `i` that comes `k`-th in the new order
22//!   (the `k`-th pivot of an elimination, the `k`-th column of `A Q`);
23//! * `inv[i] = k` — the new position of the old index `i`.
24//!
25//! As matrices: `P` with `(P x)_k = x_{fwd[k]}`, so `P A Pᵀ` has entry
26//! `(k, l) = a_{fwd[k], fwd[l]}`.
27//!
28//! For a square pattern `S` let `G(S)` be the undirected graph on `0..n`
29//! with an edge `{i, j}` (`i ≠ j`) whenever `s_ij` or `s_ji` is stored: the
30//! graph of `S + Sᵀ` without its diagonal. `L` is the Cholesky factor of a
31//! symmetric positive definite matrix with the pattern of `P (S + Sᵀ) Pᵀ`
32//! (and a full diagonal), `nnz(L)` its number of entries *including* the
33//! diagonal — the *fill* of the ordering in the tables (no numerical
34//! cancellation is assumed: the structural count).
35//!
36//! ## Algorithm S (Symmetrization `S + Sᵀ`)
37//! S1. Compute `Sᵀ` by Algorithm T of Chapter 5.8 (indices only).
38//! S2. For each column `j`, merge the sorted lists of column `j` of `S` and
39//!     of `Sᵀ`, keeping each index once. The result has sorted columns.
40//!
41//! ## Algorithm E (Elimination tree and Cholesky counts, by row subtrees)
42//! Given the symmetric graph `G` and the permutation `π`; let `C = P G Pᵀ`.
43//! Row `k` of `L` is the set of `l ≤ k` reached from the entries `c_kl`,
44//! `l < k`, by walking up the elimination tree of the leading `k × k`
45//! block (the *row subtree*, Liu 1986).
46//!
47//! E1. Set `parent[k] ← ∅`, `mark[k] ← ∅` for all `k`, `count ← n` (the
48//!     diagonal).
49//! E2. For `k = 0, 1, …, n − 1`: set `mark[k] ← k`; for every neighbour `i`
50//!     of `fwd[k]` with `l = inv[i] < k`, walk `x ← l, parent[x], …` while
51//!     `mark[x] ≠ k`: set `mark[x] ← k`, `count ← count + 1` (the entry
52//!     `l_kx`), and if `parent[x] = ∅` set `parent[x] ← k` and stop.
53//! E3. Return `count`.
54//!
55//! The walk of E2 from `l` stops at the first node already in row `k`'s
56//! subtree, so every node of the row subtree is visited once: the cost is
57//! `O(nnz(L) + nnz(S))`, no `log` and no sort. Setting `parent` the first
58//! time a root is reached is Liu's elimination-tree algorithm without path
59//! compression.
60//!
61//! ## Algorithm P (Postorder of the elimination tree, heaviest child last)
62//! *New with task L1.5b.* Given `G` and `π`, a permutation `π′` with the
63//! same filled graph whose subtrees are contiguous and whose heaviest
64//! child comes right before its parent.
65//!
66//! P1. Run Algorithm E, keeping `parent[k]` and the column counts `c_k`
67//!     (entries of column `k` of `L`, diagonal included).
68//! P2. Order the children of every node by increasing `(c, k)`: the child
69//!     with the largest column count — the largest front — last.
70//! P3. Visit the roots in increasing order, each subtree depth first with
71//!     the children in the order of P2, and number every node after its
72//!     children: `post[t]` is the `t`-th node. Return `fwd′[t] =
73//!     fwd[post[t]]`.
74//!
75//! Every topological order of the elimination tree — a postorder in
76//! particular — eliminates with the same filled graph (Liu 1990, §3), so
77//! `nnz(L)` does not change; the postorder makes each subtree a run of
78//! consecutive columns, so every chain of only children (a fundamental
79//! supernode) is contiguous; and placing the heaviest child last puts the
80//! largest front next to its parent. That matters to a supernodal
81//! backend: faer 0.24 (read, not copied) merges a child supernode into its
82//! parent in its relaxed amalgamation *only* when the child immediately
83//! precedes the parent, and SuiteSparse's AMD postorders its assembly tree
84//! with the largest front last for the same reason. With the children in
85//! index order instead, faer stored 2.78 M entries of `L` for the
86//! augmented system of maros-r7 (the same 1.21 M structural ones) and
87//! factorized 11× slower (task L1.5b, D4). Cost `O(nnz(L) + n log n)`.
88//!
89//! ## Algorithm G (The pattern of `SᵀS`)
90//! For COLAMD (Chapter 5.10) the relevant symmetric graph is that of `SᵀS`,
91//! whose Cholesky factor bounds the `U` of an LU with partial pivoting and
92//! is the `R` of a QR factorization (George & Ng 1987). Column `j` of `SᵀS`
93//! is the union, over the rows `i` of column `j` of `S`, of the columns of
94//! row `i` (rows read from `Sᵀ`): mark-and-collect, then sort each column.
95//! Cost `O(Σ_i r_i²)` with `r_i` the row counts — which is why COLAMD itself
96//! never forms it.
97//!
98//! ## Invariants
99//! (P1) (= the contract's (S3)) A [`Perm`] of length `n` has `fwd` and `inv`
100//!      of length `n`, entries `< n`, and `inv[fwd[k]] = k` for every `k`
101//!      (so both are bijections). [`Perm::check_invariants`] checks it and
102//!      every constructor asserts it in debug builds.
103//! (P2) A [`Pattern`] satisfies (C1), (C2) and (C4) of Chapter 5.8 (there
104//!      are no values, so (C3) is void): pointers non-decreasing from 0 to
105//!      `nnz`, row indices strictly increasing inside a column and smaller
106//!      than `n_rows`. Checked by [`Pattern::check_invariants`].
107//! (P3) The outputs of Algorithms S and G are symmetric patterns that
108//!      satisfy (P2).
109//! (P4) Algorithm P returns a permutation with the `nnz(L)` of its input
110//!      (checked in the tests against Algorithm E), in which every node
111//!      comes after all of its elimination-tree descendants.
112//!
113//! ## References
114//! Liu, "A compact row storage scheme for Cholesky factors using
115//! elimination trees", ACM TOMS 12(2), 1986, and "The role of elimination
116//! trees in sparse factorization", SIAM J. Matrix Anal. Appl. 11(1), 1990;
117//! George & Ng, "Symbolic factorization for sparse Gaussian elimination
118//! with partial pivoting", SIAM J. Sci. Stat. Comput. 8(6), 1987; Davis,
119//! *Direct Methods for Sparse Linear Systems* (2006), §4.1 and §4.4 (read,
120//! not copied); the contract of the crate (`Pattern`, `Perm`, (S3)).
121
122use crate::index::dim_to_u32;
123use crate::real::Real;
124use crate::{CscMatrix, SparseError};
125
126/// A permutation of `0..n` with its inverse (invariant (P1), the
127/// contract's (S3)).
128///
129/// `fwd[k]` is the old index placed at new position `k`; `inv[i]` is the
130/// new position of the old index `i`. The fields are public, as in the
131/// contract; a value built by hand should be checked with
132/// [`Perm::check_invariants`].
133#[derive(Clone, Debug, PartialEq, Eq)]
134pub struct Perm {
135    /// `fwd[k]`: the old index at new position `k`.
136    pub fwd: Vec<u32>,
137    /// `inv[i]`: the new position of the old index `i`.
138    pub inv: Vec<u32>,
139}
140
141impl Perm {
142    /// The identity permutation of `0..n`.
143    ///
144    /// # Panics
145    /// If `n` exceeds `u32::MAX`.
146    pub fn identity(n: usize) -> Self {
147        assert!(dim_to_u32("permutation", n).is_ok(), "n exceeds u32::MAX");
148        let fwd: Vec<u32> = (0..n).map(idx32).collect();
149        Self {
150            inv: fwd.clone(),
151            fwd,
152        }
153    }
154
155    /// The permutation whose forward array is `fwd`, with its inverse;
156    /// an error unless `fwd` is a bijection of `0..fwd.len()`.
157    pub fn from_fwd(fwd: Vec<u32>) -> Result<Self, SparseError> {
158        let n = fwd.len();
159        dim_to_u32("permutation", n)?;
160        let mut inv = vec![u32::MAX; n];
161        for (k, &i) in fwd.iter().enumerate() {
162            let i = i as usize;
163            if i >= n {
164                return Err(SparseError::IndexOutOfRange {
165                    what: "permutation entry",
166                    index: i,
167                    bound: n,
168                });
169            }
170            if inv[i] != u32::MAX {
171                return Err(SparseError::Malformed(format!(
172                    "(P1): index {i} appears twice in the permutation"
173                )));
174            }
175            inv[i] = idx32(k);
176        }
177        let p = Self { fwd, inv };
178        debug_assert_eq!(p.check_invariants(), Ok(()));
179        Ok(p)
180    }
181
182    /// The length `n`.
183    #[inline]
184    pub fn len(&self) -> usize {
185        self.fwd.len()
186    }
187
188    /// `true` iff `n = 0`.
189    #[inline]
190    pub fn is_empty(&self) -> bool {
191        self.fwd.is_empty()
192    }
193
194    /// The inverse permutation (`fwd` and `inv` exchanged).
195    #[must_use]
196    pub fn inverse(&self) -> Self {
197        Self {
198            fwd: self.inv.clone(),
199            inv: self.fwd.clone(),
200        }
201    }
202
203    /// `true` iff this is the identity.
204    pub fn is_identity(&self) -> bool {
205        self.fwd.iter().enumerate().all(|(k, &i)| i as usize == k)
206    }
207
208    /// Checks invariant (P1).
209    pub fn check_invariants(&self) -> Result<(), SparseError> {
210        let n = self.fwd.len();
211        if self.inv.len() != n {
212            return Err(SparseError::Dimension {
213                what: "inverse permutation",
214                expected: n,
215                found: self.inv.len(),
216            });
217        }
218        for (k, &i) in self.fwd.iter().enumerate() {
219            let i = i as usize;
220            if i >= n {
221                return Err(SparseError::IndexOutOfRange {
222                    what: "permutation entry",
223                    index: i,
224                    bound: n,
225                });
226            }
227            if self.inv[i] as usize != k {
228                return Err(SparseError::Malformed(format!(
229                    "(P1): inv[fwd[{k}]] = {} ≠ {k}",
230                    self.inv[i]
231                )));
232            }
233        }
234        Ok(())
235    }
236}
237
238/// The structure of a compressed sparse column matrix without its values
239/// (invariant (P2)): what the orderings of Chapter 5.10 consume.
240#[derive(Clone, Debug, PartialEq, Eq)]
241pub struct Pattern {
242    /// Number of rows `m`.
243    pub n_rows: usize,
244    /// Column pointers, length `n + 1`.
245    pub col_ptr: Vec<usize>,
246    /// Row indices, strictly increasing inside each column.
247    pub row_idx: Vec<u32>,
248}
249
250impl Pattern {
251    /// The pattern with the given arrays, validated ((P2)).
252    pub fn from_raw_parts(
253        n_rows: usize,
254        col_ptr: Vec<usize>,
255        row_idx: Vec<u32>,
256    ) -> Result<Self, SparseError> {
257        let p = Self {
258            n_rows,
259            col_ptr,
260            row_idx,
261        };
262        p.check_invariants()?;
263        Ok(p)
264    }
265
266    /// The empty `m × n` pattern.
267    ///
268    /// # Panics
269    /// If `m` or `n` exceeds `u32::MAX`.
270    pub fn empty(n_rows: usize, n_cols: usize) -> Self {
271        assert!(dim_to_u32("rows", n_rows).is_ok() && dim_to_u32("columns", n_cols).is_ok());
272        Self {
273            n_rows,
274            col_ptr: vec![0; n_cols + 1],
275            row_idx: Vec::new(),
276        }
277    }
278
279    /// Number of rows `m`.
280    #[inline]
281    pub fn n_rows(&self) -> usize {
282        self.n_rows
283    }
284
285    /// Number of columns `n`.
286    #[inline]
287    pub fn n_cols(&self) -> usize {
288        self.col_ptr.len().saturating_sub(1)
289    }
290
291    /// Number of stored entries.
292    #[inline]
293    pub fn nnz(&self) -> usize {
294        self.row_idx.len()
295    }
296
297    /// The row indices of column `j`.
298    #[inline]
299    pub fn col(&self, j: usize) -> &[u32] {
300        &self.row_idx[self.col_ptr[j]..self.col_ptr[j + 1]]
301    }
302
303    /// `Sᵀ` (Algorithm T of Chapter 5.8, indices only).
304    #[must_use]
305    pub fn transpose(&self) -> Self {
306        // T1–T2. Counts and prefix sums.
307        let mut ptr = vec![0_usize; self.n_rows + 1];
308        for &i in &self.row_idx {
309            ptr[i as usize + 1] += 1;
310        }
311        for i in 0..self.n_rows {
312            ptr[i + 1] += ptr[i];
313        }
314        // T3. Scatter by increasing column (sorted output).
315        let mut next = ptr[..self.n_rows].to_vec();
316        let mut idx = vec![0_u32; self.nnz()];
317        for j in 0..self.n_cols() {
318            for &i in self.col(j) {
319                idx[next[i as usize]] = idx32(j);
320                next[i as usize] += 1;
321            }
322        }
323        let t = Self {
324            n_rows: self.n_cols(),
325            col_ptr: ptr,
326            row_idx: idx,
327        };
328        debug_assert_eq!(t.check_invariants(), Ok(()));
329        t
330    }
331
332    /// `S + Sᵀ` (Algorithm S); the diagonal entries of `S` are kept, none
333    /// is added. An error unless `S` is square.
334    pub fn symmetric(&self) -> Result<Self, SparseError> {
335        let n = self.n_cols();
336        if self.n_rows != n {
337            return Err(SparseError::Dimension {
338                what: "pattern (must be square to symmetrize)",
339                expected: n,
340                found: self.n_rows,
341            });
342        }
343        let t = self.transpose();
344        let mut col_ptr = Vec::with_capacity(n + 1);
345        let mut row_idx = Vec::with_capacity(2 * self.nnz());
346        col_ptr.push(0);
347        for j in 0..n {
348            // S2. Merge two sorted lists.
349            let (a, b) = (self.col(j), t.col(j));
350            let (mut p, mut q) = (0, 0);
351            while p < a.len() || q < b.len() {
352                let x = a.get(p).copied().unwrap_or(u32::MAX);
353                let y = b.get(q).copied().unwrap_or(u32::MAX);
354                let next = x.min(y);
355                p += usize::from(x == next);
356                q += usize::from(y == next);
357                row_idx.push(next);
358            }
359            col_ptr.push(row_idx.len());
360        }
361        let s = Self {
362            n_rows: n,
363            col_ptr,
364            row_idx,
365        };
366        debug_assert_eq!(s.check_invariants(), Ok(()));
367        Ok(s)
368    }
369
370    /// The pattern of `SᵀS` (Algorithm G), diagonal included: an `n × n`
371    /// symmetric pattern.
372    #[must_use]
373    pub fn ata(&self) -> Self {
374        let n = self.n_cols();
375        let t = self.transpose();
376        let mut mark = vec![usize::MAX; n];
377        let mut col_ptr = Vec::with_capacity(n + 1);
378        let mut row_idx = Vec::new();
379        col_ptr.push(0);
380        for j in 0..n {
381            let start = row_idx.len();
382            for &i in self.col(j) {
383                for &k in t.col(i as usize) {
384                    if mark[k as usize] != j {
385                        mark[k as usize] = j;
386                        row_idx.push(k);
387                    }
388                }
389            }
390            row_idx[start..].sort_unstable();
391            col_ptr.push(row_idx.len());
392        }
393        let s = Self {
394            n_rows: n,
395            col_ptr,
396            row_idx,
397        };
398        debug_assert_eq!(s.check_invariants(), Ok(()));
399        s
400    }
401
402    /// `nnz(L)`, diagonal included, of the Cholesky factor of
403    /// `P (S + Sᵀ) Pᵀ` for the permutation `perm` (Algorithm E): the fill
404    /// an ordering yields. An error unless `S` is square with `perm` of the
405    /// same order.
406    pub fn cholesky_nnz(&self, perm: &Perm) -> Result<usize, SparseError> {
407        let n = self.n_cols();
408        if self.n_rows != n || perm.len() != n {
409            return Err(SparseError::Dimension {
410                what: "cholesky_nnz (square pattern and permutation of its order)",
411                expected: n,
412                found: if self.n_rows == n {
413                    perm.len()
414                } else {
415                    self.n_rows
416                },
417            });
418        }
419        perm.check_invariants()?;
420        let (_, counts) = etree_counts(&self.symmetric()?, perm);
421        // E3.
422        Ok(counts.iter().sum())
423    }
424
425    /// Algorithm P on the symmetric pattern `self` (both triangles, as
426    /// [`Pattern::symmetric`] returns): `perm` re-postordered by its
427    /// elimination tree, heaviest child last (invariant (P4)).
428    pub(crate) fn etree_postorder(&self, perm: &Perm) -> Perm {
429        let n = perm.len();
430        debug_assert_eq!(self.n_cols(), n);
431        // P1.
432        let (parent, counts) = etree_counts(self, perm);
433        // P2. Children grouped by parent, by increasing (count, index).
434        let none = usize::MAX;
435        let mut kids: Vec<(usize, usize, usize)> = (0..n)
436            .filter(|&k| parent[k] != none)
437            .map(|k| (parent[k], counts[k], k))
438            .collect();
439        kids.sort_unstable();
440        let mut start = vec![0_usize; n + 1];
441        for &(p, _, _) in &kids {
442            start[p + 1] += 1;
443        }
444        for k in 0..n {
445            start[k + 1] += start[k];
446        }
447        // P3.
448        let mut fwd = Vec::with_capacity(n);
449        let mut stack: Vec<(usize, usize)> = Vec::new();
450        for root in (0..n).filter(|&k| parent[k] == none) {
451            stack.push((root, start[root]));
452            while let Some(top) = stack.last_mut() {
453                let (x, next) = *top;
454                if next < start[x + 1] {
455                    top.1 += 1;
456                    let c = kids[next].2;
457                    stack.push((c, start[c]));
458                } else {
459                    stack.pop();
460                    fwd.push(perm.fwd[x]);
461                }
462            }
463        }
464        let post = Perm::from_fwd(fwd).expect("(P4): a postorder is a permutation");
465        debug_assert!(
466            (0..n).all(|k| parent[k] == none
467                || post.inv[perm.fwd[k] as usize] < post.inv[perm.fwd[parent[k]] as usize]),
468            "(P4): a node before its parent"
469        );
470        post
471    }
472
473    /// Checks invariant (P2).
474    pub fn check_invariants(&self) -> Result<(), SparseError> {
475        dim_to_u32("rows", self.n_rows)?;
476        dim_to_u32("columns", self.n_cols())?;
477        if self.col_ptr.is_empty() {
478            return Err(SparseError::Malformed("(P2): empty pointer array".into()));
479        }
480        if self.col_ptr[0] != 0 || self.col_ptr[self.n_cols()] != self.row_idx.len() {
481            return Err(SparseError::Malformed(format!(
482                "(P2): pointers must run from 0 to nnz = {}",
483                self.row_idx.len()
484            )));
485        }
486        for j in 0..self.n_cols() {
487            if self.col_ptr[j] > self.col_ptr[j + 1] {
488                return Err(SparseError::Malformed(format!(
489                    "(P2): pointer of column {j} decreases"
490                )));
491            }
492            let col = self.col(j);
493            for (p, &i) in col.iter().enumerate() {
494                if i as usize >= self.n_rows {
495                    return Err(SparseError::IndexOutOfRange {
496                        what: "pattern row index",
497                        index: i as usize,
498                        bound: self.n_rows,
499                    });
500                }
501                if p > 0 && col[p - 1] >= i {
502                    return Err(SparseError::Malformed(format!(
503                        "(P2): rows of column {j} not strictly increasing"
504                    )));
505                }
506            }
507        }
508        Ok(())
509    }
510}
511
512impl<T: Real> CscMatrix<T> {
513    /// The structure without values, consumed by the orderings (Chapter
514    /// 5.9).
515    pub fn pattern(&self) -> Pattern {
516        Pattern {
517            n_rows: self.n_rows,
518            col_ptr: self.col_ptr.clone(),
519            row_idx: self.row_idx.clone(),
520        }
521    }
522
523    /// The pattern of `A + Aᵀ` (Algorithm S) for the symmetric orderings;
524    /// an error unless `A` is square.
525    pub fn symmetric_pattern(&self) -> Result<Pattern, SparseError> {
526        self.pattern().symmetric()
527    }
528}
529
530/// Algorithm E (steps E1–E2) on the symmetric graph `g` under `perm`: the
531/// elimination tree (`parent[k]`, `usize::MAX` for a root; positions in
532/// the new order) and the column counts of `L` (diagonal included).
533pub(crate) fn etree_counts(g: &Pattern, perm: &Perm) -> (Vec<usize>, Vec<usize>) {
534    let n = perm.len();
535    // E1.
536    let none = usize::MAX;
537    let mut parent = vec![none; n];
538    let mut mark = vec![none; n];
539    let mut counts = vec![1_usize; n];
540    // E2.
541    for k in 0..n {
542        mark[k] = k;
543        for &i in g.col(perm.fwd[k] as usize) {
544            let mut x = perm.inv[i as usize] as usize;
545            if x >= k {
546                continue;
547            }
548            while mark[x] != k {
549                mark[x] = k;
550                counts[x] += 1;
551                if parent[x] == none {
552                    parent[x] = k;
553                    break;
554                }
555                x = parent[x];
556            }
557        }
558    }
559    (parent, counts)
560}
561
562/// Converts an index below `u32::MAX` to `u32`.
563#[inline]
564pub(crate) fn idx32(i: usize) -> u32 {
565    u32::try_from(i).expect("index exceeds u32::MAX")
566}
567
568#[cfg(test)]
569mod tests {
570    use super::*;
571    use proptest::prelude::*;
572
573    /// A random `m × n` pattern from a list of `(i, j)` (duplicates
574    /// collapse).
575    fn pattern_of(m: usize, n: usize, entries: &[(usize, usize)]) -> Pattern {
576        let mut cols: Vec<Vec<u32>> = vec![Vec::new(); n];
577        for &(i, j) in entries {
578            cols[j % n].push(idx32(i % m));
579        }
580        let mut col_ptr = vec![0];
581        let mut row_idx = Vec::new();
582        for mut c in cols {
583            c.sort_unstable();
584            c.dedup();
585            row_idx.extend(c);
586            col_ptr.push(row_idx.len());
587        }
588        Pattern::from_raw_parts(m, col_ptr, row_idx).unwrap()
589    }
590
591    /// Brute force: `nnz(L)` by eliminating the dense graph of `P G Pᵀ`.
592    fn cholesky_nnz_dense(s: &Pattern, perm: &Perm) -> usize {
593        let n = s.n_cols();
594        let mut adj = vec![vec![false; n]; n];
595        for j in 0..n {
596            for &i in s.col(j) {
597                let (a, b) = (perm.inv[i as usize] as usize, perm.inv[j] as usize);
598                if a != b {
599                    adj[a][b] = true;
600                    adj[b][a] = true;
601                }
602            }
603        }
604        let mut count = n;
605        for k in 0..n {
606            let later: Vec<usize> = (k + 1..n).filter(|&l| adj[k][l]).collect();
607            count += later.len();
608            for &a in &later {
609                for &b in &later {
610                    if a != b {
611                        adj[a][b] = true;
612                    }
613                }
614            }
615        }
616        count
617    }
618
619    #[test]
620    fn perm_constructors_and_errors() {
621        let p = Perm::identity(4);
622        assert!(p.is_identity() && p.check_invariants().is_ok() && p.len() == 4);
623        let q = Perm::from_fwd(vec![2, 0, 3, 1]).unwrap();
624        assert_eq!(q.inv, vec![1, 3, 0, 2]);
625        assert_eq!(q.inverse().inverse(), q);
626        assert!(!q.is_identity() && !q.is_empty());
627        assert!(Perm::from_fwd(vec![0, 0]).is_err());
628        assert!(Perm::from_fwd(vec![0, 2]).is_err());
629        let bad = Perm {
630            fwd: vec![0, 1],
631            inv: vec![1, 0],
632        };
633        assert!(bad.check_invariants().is_err());
634        assert!(Perm::identity(0).is_empty());
635    }
636
637    #[test]
638    fn pattern_validation_and_access() {
639        assert!(Pattern::from_raw_parts(2, vec![0, 2], vec![1, 0]).is_err());
640        assert!(Pattern::from_raw_parts(2, vec![0, 1], vec![2]).is_err());
641        assert!(Pattern::from_raw_parts(2, vec![0, 2, 1], vec![0, 1]).is_err());
642        let p = Pattern::from_raw_parts(3, vec![0, 2, 2, 3], vec![0, 2, 1]).unwrap();
643        assert_eq!((p.n_rows(), p.n_cols(), p.nnz()), (3, 3, 3));
644        assert_eq!(p.col(0), &[0, 2]);
645        assert_eq!(p.col(1), []);
646        assert!(Pattern::empty(2, 3).check_invariants().is_ok());
647        let a = CscMatrix::<f64>::from_raw_parts(
648            3,
649            vec![0, 2, 2, 3],
650            vec![0, 2, 1],
651            vec![1.0, 2.0, 3.0],
652        )
653        .unwrap();
654        assert_eq!(a.pattern(), p);
655        let s = a.symmetric_pattern().unwrap();
656        assert_eq!(s.col(0), &[0, 2]);
657        assert_eq!(s.col(1), &[2]);
658        assert_eq!(s.col(2), &[0, 1]);
659        assert!(Pattern::empty(2, 3).symmetric().is_err());
660        assert!(p.cholesky_nnz(&Perm::identity(2)).is_err());
661    }
662
663    proptest! {
664        /// (P2)/(P3): transposition is an involution, `S + Sᵀ` is symmetric
665        /// and contains `S`, `SᵀS` is symmetric with its diagonal.
666        #[test]
667        fn pattern_algebra(m in 1_usize..12, n in 1_usize..12,
668                           e in prop::collection::vec((0_usize..12, 0_usize..12), 0..60)) {
669            let s = pattern_of(m, n, &e);
670            prop_assert_eq!(s.transpose().transpose(), s.clone());
671            let g = s.ata();
672            prop_assert_eq!(g.transpose(), g.clone());
673            for j in 0..n {
674                if !s.col(j).is_empty() {
675                    prop_assert!(g.col(j).contains(&idx32(j)));
676                }
677            }
678            let q = pattern_of(n, n, &e);
679            let sym = q.symmetric().unwrap();
680            prop_assert_eq!(sym.transpose(), sym.clone());
681            for j in 0..n {
682                for &i in q.col(j) {
683                    prop_assert!(sym.col(j).contains(&i));
684                }
685            }
686        }
687
688        /// Algorithm E against the dense elimination, under random
689        /// permutations.
690        #[test]
691        fn cholesky_count_matches_dense_elimination(
692            n in 1_usize..25,
693            e in prop::collection::vec((0_usize..25, 0_usize..25), 0..80),
694            keys in prop::collection::vec(any::<u32>(), 25),
695        ) {
696            let s = pattern_of(n, n, &e);
697            let mut fwd: Vec<u32> = (0..n).map(idx32).collect();
698            fwd.sort_by_key(|&i| keys[i as usize]);
699            let perm = Perm::from_fwd(fwd).unwrap();
700            prop_assert_eq!(s.cholesky_nnz(&perm).unwrap(), cholesky_nnz_dense(&s, &perm));
701        }
702
703        /// (P4): Algorithm P keeps `nnz(L)` and returns a postorder of the
704        /// elimination tree with the heaviest child of every node right
705        /// before it.
706        #[test]
707        fn etree_postorder_keeps_the_fill(
708            n in 1_usize..25,
709            e in prop::collection::vec((0_usize..25, 0_usize..25), 0..80),
710            keys in prop::collection::vec(any::<u32>(), 25),
711        ) {
712            let s = pattern_of(n, n, &e).symmetric().unwrap();
713            let mut fwd: Vec<u32> = (0..n).map(idx32).collect();
714            fwd.sort_by_key(|&i| keys[i as usize]);
715            let perm = Perm::from_fwd(fwd).unwrap();
716            let post = s.etree_postorder(&perm);
717            prop_assert_eq!(post.check_invariants(), Ok(()));
718            prop_assert_eq!(s.cholesky_nnz(&post).unwrap(), s.cholesky_nnz(&perm).unwrap());
719            let (parent, counts) = etree_counts(&s, &post);
720            // Postorder: a node follows its children, and every subtree is
721            // a contiguous run ending at its root.
722            let mut size = vec![1_usize; n];
723            for k in 0..n {
724                if parent[k] != usize::MAX {
725                    prop_assert!(parent[k] > k);
726                    size[parent[k]] += size[k];
727                }
728            }
729            for (k, &p) in parent.iter().enumerate() {
730                if p != usize::MAX {
731                    // Contiguity: the subtree of p is p − size(p) + 1 ..= p.
732                    prop_assert!(k + size[p] > p);
733                }
734            }
735            // Heaviest child last: the child right before a parent with
736            // children has the largest count among its siblings.
737            for p in 0..n {
738                let kids: Vec<usize> = (0..n).filter(|&k| parent[k] == p).collect();
739                if let Some(&last) = kids.iter().max() {
740                    prop_assert_eq!(last + 1, p);
741                    let heaviest = kids.iter().map(|&k| counts[k]).max().unwrap();
742                    prop_assert_eq!(counts[last], heaviest);
743                }
744            }
745        }
746    }
747}