feral_ordering_core/quotient_graph/
mod.rs

1//! Shared quotient-graph machinery for AMD-family bottom-up
2//! orderings.
3//!
4//! This module hosts the workspace, elimination loop, and assembly-
5//! tree postorder used by `feral-amd` and (planned) `feral-amf`.
6//! Both orderings share the quotient-graph data structures
7//! (`PE / IW / LEN / NV / ELEN`), the standard / aggressive element
8//! absorption logic, the mass-elimination fast path, the
9//! supervariable hash bucket detection, and the inline garbage
10//! collector. They differ only in the *selection metric* —
11//! approximate degree (AMD) vs approximate fill (AMF) — which is
12//! abstracted behind the [`Metric`] trait. Phase A shipped the trait
13//! plus the AMD-specialised [`MinDegree`] impl; Phase B.2 added
14//! [`MinFill`] driving the parallel `run_elimination_amf` /
15//! `create_element_amf` / `select_pivot_amf` / `finalize_step_amf`
16//! family in `algo.rs`. The duplicated inner loops trade LoC for a
17//! zero-risk AMD bit-parity contract.
18//!
19//! Reference: Amestoy, Davis, Duff (1996) "An approximate minimum
20//! degree ordering algorithm," SIAM J. Matrix Analysis 17:886-905;
21//! Amestoy (1999) habilitation thesis (AMF metric).
22
23#![allow(dead_code)]
24// Quotient-graph internals (Workspace fields, StepFlops fields, etc.)
25// are pub because the planned `feral-amf` crate will read them
26// directly. They are deliberately not part of the locked
27// ordering-crate contract; see CONTRACT_VERSION.
28#![allow(missing_docs)]
29
30mod algo;
31mod metric;
32mod workspace;
33
34pub use algo::{
35    create_element, create_element_amf, finalize_permutation, finalize_step, finalize_step_amf,
36    run_elimination, run_elimination_amf, select_pivot, select_pivot_amf, StepFlops,
37};
38pub use metric::{Metric, MinDegree, MinFill};
39pub use workspace::{clear_flag, flip, Workspace, NONE};
40
41use crate::{CscPattern, OrderingError};
42
43/// Tunable parameters for the shared quotient-graph workspace.
44///
45/// Only the workspace-relevant parameters live here. Crate-specific
46/// knobs (e.g. `aggressive` for the elimination loop) are passed
47/// directly to the relevant entry point.
48#[derive(Debug, Clone)]
49pub struct WorkspaceOptions {
50    /// Dense-row threshold multiplier (Davis 1996 §5). A variable
51    /// with initial degree exceeding
52    /// `min(max(16, floor(dense_alpha * sqrt(n))), n)` is deferred to
53    /// the end of the ordering — the `max(16)` floor is applied before
54    /// the `min(n)` cap, matching faer `amd.rs:173-179`. A negative
55    /// value uses a raw threshold of `n - 2` with the same clamps; for
56    /// `n >= 18` that is exactly `n - 2`, suppressing deferral for
57    /// everything but true hubs of degree `n - 1`.
58    pub dense_alpha: f64,
59}
60
61impl Default for WorkspaceOptions {
62    fn default() -> Self {
63        Self { dense_alpha: 10.0 }
64    }
65}
66
67/// Diagnostic counters extracted from a completed [`Workspace`].
68///
69/// Surfaced by [`order`] alongside the permutation so callers can
70/// build crate-specific stats structs without re-borrowing the
71/// workspace internals.
72#[derive(Debug, Clone, Copy, Default)]
73pub struct OrderDiagnostics {
74    pub ncmpa: u32,
75    pub n_mass_elim: u32,
76    pub n_supervar_merge: u32,
77    pub ndense: i32,
78    pub flops: StepFlops,
79}
80
81/// Run a metric-driven AMD-family ordering on a full-symmetric
82/// pattern, returning the permutation plus diagnostic counters.
83///
84/// Equivalent to:
85///
86/// ```ignore
87/// let mut ws = Workspace::new(pattern, opts)?;
88/// let flops = M::run_elimination(&mut ws, aggressive)?;
89/// let perm = finalize_permutation(&mut ws);
90/// ```
91///
92/// `M` selects the metric (and, transitively, the elimination loop).
93/// AMD uses [`MinDegree`]; the planned AMF crate will pass `MinFill`.
94pub fn order<M: Metric>(
95    pattern: &CscPattern<'_>,
96    opts: &WorkspaceOptions,
97    aggressive: bool,
98) -> Result<(Vec<i32>, OrderDiagnostics), OrderingError> {
99    let n_buckets = M::n_buckets(pattern.n);
100    let mut ws = Workspace::new_with_n_buckets(pattern, opts, n_buckets)?;
101    let flops = M::run_elimination(&mut ws, aggressive)?;
102    let diag = OrderDiagnostics {
103        ncmpa: ws.ncmpa,
104        n_mass_elim: ws.n_mass_elim,
105        n_supervar_merge: ws.n_supervar_merge,
106        ndense: ws.ndense,
107        flops,
108    };
109    let perm = finalize_permutation(&mut ws);
110    Ok((perm, diag))
111}
feral_ordering_core/quotient_graph/mod.rs

feral_ordering_core/quotient_graph/
mod.rs
