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}