1use crate::factor::count_f64;
97use crate::perm::idx32;
98use crate::qgraph::{self, Input};
99use crate::real::lt;
100use crate::{Pattern, Perm, SparseError};
101
102#[derive(Clone, Copy, Debug, PartialEq, Eq)]
104pub enum OrderingTarget {
105 Symmetric,
108 Columns,
111}
112
113pub trait Ordering {
116 fn order(&self, pattern: &Pattern, target: OrderingTarget) -> Result<Perm, SparseError>;
119 fn name(&self) -> &'static str;
121}
122
123#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
125pub struct Natural;
126
127#[derive(Clone, Copy, Debug, PartialEq)]
132pub struct Amd {
133 pub dense: Option<f64>,
136 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#[derive(Clone, Copy, Debug, Default, PartialEq)]
153pub struct Colamd {
154 pub dense_row: Option<f64>,
157 pub dense_col: Option<f64>,
161}
162
163const DENSE_DEFAULT: f64 = 10.0;
165
166const DENSE_MIN: usize = 16;
168
169fn 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#[inline]
180#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)] fn floor_usize(x: f64) -> usize {
182 x as usize
183}
184
185fn 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
199type Lists = (Vec<usize>, Vec<u32>);
201
202fn 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
215fn 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
243fn no_lists(n: usize) -> Lists {
245 (vec![0; n + 1], Vec::new())
246}
247
248fn 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 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 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 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 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 fn columns(self, s: &Pattern) -> Perm {
330 let (m, n) = (s.n_rows, s.n_cols());
331 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 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 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 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 finish(n, fwd, &[null.as_slice(), dense.as_slice()])
372 }
373
374 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 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 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 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 fn tree_edges(rng: &mut Rng, n: usize) -> Vec<(usize, usize)> {
472 (1..n).map(|i| (i, rng.below(i))).collect()
473 }
474
475 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 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 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 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 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 #[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 #[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 #[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 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 #[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 #[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 #[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 #[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 #[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 #[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 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}