feral_scotch/
lib.rs

1//! SCOTCH-style nested-dissection fill-reducing ordering.
2//!
3//! Clean-room pure-Rust implementation of the algorithms described in
4//! Pellegrini, "SCOTCH: A software package for static mapping by dual
5//! recursive bipartitioning of process and architecture graphs"
6//! (HPCN Europe, 1996), §3. This crate provides an alternative to
7//! [`feral_metis`](../feral_metis) with:
8//!
9//! - Graph compression (supervariable merging before partitioning).
10//! - Direct vertex-separator FM (tighter separators than edge-cut
11//!   conversion on structured meshes).
12//! - Adaptive refinement (boundary / halo FM). A band-FM refiner
13//!   (`band_fm`) is implemented and unit-tested but is not yet wired
14//!   into the default ND driver.
15//!
16//! The public surface conforms to the FERAL ordering-crate contract
17//! (`dev/plans/ordering-crate-contract.md`): [`CscPattern`],
18//! [`OrderingStats`], [`OrderingError`], and [`CONTRACT_VERSION`] are
19//! re-exported from `feral-ordering-core`.
20//!
21//! **Status: S1–S5 complete.** [`scotch_order`] and
22//! [`scotch_order_full`] run the full pipeline — graph compression,
23//! connected-component split, multilevel coarsening, best-of-
24//! `n_sep_trials` initial bisection, halo-FM uncoarsening, direct
25//! vertex separator, and recursive ND with an AMD leaf fallback.
26//!
27//! ## Clean-room provenance
28//!
29//! No code is copied or paraphrased from SCOTCH's C source
30//! (`libscotch/`, CeCILL-C). Algorithms are reconstructed from
31//! Pellegrini 1996 §3 and the research notes under `dev/research/`.
32//! Constants, data layouts, and hash choices are independently
33//! justified and documented per-module.
34
35#![forbid(unsafe_code)]
36#![deny(missing_docs)]
37
38#[allow(dead_code)]
39mod band_fm;
40#[allow(dead_code)]
41mod compress;
42#[allow(dead_code)]
43mod graph;
44#[allow(dead_code)]
45mod halo_fm;
46mod node_nd;
47#[allow(dead_code)]
48mod vertex_separator;
49
50#[cfg(test)]
51mod test_util;
52
53pub use feral_ordering_core::{CscPattern, OrderingError, OrderingStats, CONTRACT_VERSION};
54
55/// Tunable parameters for SCOTCH nested-dissection ordering.
56///
57/// Defaults mirror SCOTCH 7.0's vertex-separation ordering defaults as
58/// documented in the audit of `dev/plans/ordering-scotch.md`:
59/// `cmin = 100` (coarsening floor), `amd_switch = 120`,
60/// `n_sep_trials = 5`, `fm_move_cap = 200`, `bal = 0.05`,
61/// `compress_ratio = 0.7`, `seed = 0xDEAD_BEEF`.
62///
63/// **S1 status:** only [`compress`](Self::compress) and
64/// [`compress_ratio`](Self::compress_ratio) are consumed by shipped
65/// code. The remaining fields are defined at the S1 boundary so that
66/// the public type does not drift between milestones.
67#[derive(Debug, Clone)]
68pub struct ScotchOptions {
69    /// Apply graph compression before partitioning.
70    pub compress: bool,
71    /// Compress only if `n_compressed / n < compress_ratio` (i.e.,
72    /// compress only when compression saves at least
73    /// `(1 - compress_ratio) * 100` % of vertices). SCOTCH uses 0.75;
74    /// we follow the plan's slightly more aggressive 0.7.
75    pub compress_ratio: f64,
76    /// Switch from recursive ND to AMD on subproblems with at most
77    /// this many vertices (SCOTCH default: 120).
78    pub amd_switch: u32,
79    /// Stop coarsening when the graph has fewer than this many
80    /// vertices (SCOTCH `cmin` = 100 for vertex-separation contexts).
81    pub coarsen_floor: u32,
82    /// Number of separator trials at each recursion level (SCOTCH
83    /// default: 5).
84    pub n_sep_trials: u32,
85    /// FM refinement: per-pass move cap (SCOTCH default: 200).
86    pub fm_move_cap: u32,
87    /// FM refinement: per-call pass cap. SCOTCH's default is "passes
88    /// until no improvement"; we clamp at 32 for bounded runtime.
89    pub fm_pass_cap: u32,
90    /// Imbalance tolerance (SCOTCH default: 0.05).
91    pub max_imbalance: f64,
92    /// Carry the **node separator** through uncoarsening and refine it
93    /// at every level, instead of refining the 2-way bisection with
94    /// halo FM and building the separator once at the finest level.
95    ///
96    /// The old path optimised the wrong objective at every level: halo
97    /// FM minimises an edge cut, and minimum edge cut and minimum
98    /// vertex separator are different problems. `feral-metis` had the
99    /// identical defect and fixing it there was worth 3.1x on a
100    /// collocation KKT; the same measurement for this crate is in
101    /// `dev/research/scotch-kahip-node-separator-2026-09-18.md`.
102    pub node_refine: bool,
103    /// Deterministic RNG seed for coarsening matching.
104    pub seed: u64,
105}
106
107impl Default for ScotchOptions {
108    fn default() -> Self {
109        Self {
110            compress: true,
111            compress_ratio: 0.7,
112            amd_switch: 120,
113            coarsen_floor: 100,
114            n_sep_trials: 5,
115            fm_move_cap: 200,
116            fm_pass_cap: 32,
117            max_imbalance: 0.05,
118            node_refine: true,
119            seed: 0xDEAD_BEEF,
120        }
121    }
122}
123
124/// Crate-specific diagnostic counters for SCOTCH nested dissection.
125///
126/// Zero-initialized at the start of each ordering call and filled in
127/// as the pipeline runs. S1 only touches the compression counters.
128#[derive(Debug, Default, Clone, PartialEq, Eq)]
129pub struct ScotchStats {
130    /// Number of vertices dropped by compression at the top level
131    /// (`n_original - n_compressed`). Zero if compression was
132    /// attempted but returned `None`, or if compression is disabled.
133    pub n_compressed_out: u32,
134    /// Number of coarsening levels built. Unused until S2.
135    pub n_levels: u32,
136    /// Number of top-level connected components encountered. Unused
137    /// until S5.
138    pub n_components: u32,
139    /// Number of vertices assigned to a separator at any level.
140    /// Unused until S5.
141    pub n_separator_vertices: u32,
142    /// Number of FM passes executed across all levels. Unused until
143    /// S3/S4.
144    pub n_fm_passes: u32,
145    /// Number of times the recursion bottomed out in the AMD leaf
146    /// fallback. Unused until S5.
147    pub n_amd_leaf_calls: u32,
148}
149
150/// Compute a fill-reducing SCOTCH nested-dissection ordering.
151///
152/// Thin wrapper over [`scotch_order_full`] that discards the
153/// diagnostic stats. Returns a permutation `perm` (new-to-old).
154pub fn scotch_order(pattern: &CscPattern<'_>) -> Result<Vec<i32>, OrderingError> {
155    scotch_order_full(pattern, &ScotchOptions::default()).map(|(perm, _, _)| perm)
156}
157
158/// Contract-conforming ordering producer.
159///
160/// Signature matches the shape every FERAL ordering crate must expose
161/// per `dev/plans/ordering-crate-contract.md`: input is a
162/// full-symmetric [`CscPattern`] and options; output is a three-tuple
163/// of `(perm, OrderingStats, crate-stats)`, with errors in
164/// [`OrderingError`].
165///
166/// `OrderingStats.time_us` is the wall-clock time of this call.
167/// `fill_estimate` and `flop_estimate` stay `None` — SCOTCH does not
168/// produce them at the ordering boundary; they belong to a downstream
169/// symbolic analysis.
170///
171/// Runs the S1–S5 pipeline: optional graph compression, connected-
172/// component split, multilevel coarsening, best-of-`n_sep_trials`
173/// initial bisection, halo-FM uncoarsening refinement, direct
174/// vertex-separator via two-sided FM, recursion on each side with an
175/// AMD leaf fallback at `amd_switch`.
176pub fn scotch_order_full(
177    pattern: &CscPattern<'_>,
178    opts: &ScotchOptions,
179) -> Result<(Vec<i32>, OrderingStats, ScotchStats), OrderingError> {
180    if pattern.col_ptr.len() != pattern.n + 1 {
181        return Err(OrderingError::MalformedInput);
182    }
183    let t0 = std::time::Instant::now();
184    let mut stats = ScotchStats::default();
185    let perm = node_nd::scotch_nd_order(pattern, opts, &mut stats)?;
186    let ordering_stats = OrderingStats {
187        time_us: t0.elapsed().as_micros() as u64,
188        fill_estimate: None,
189        flop_estimate: None,
190    };
191    Ok((perm, ordering_stats, stats))
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197
198    #[test]
199    fn options_defaults_match_plan() {
200        let o = ScotchOptions::default();
201        assert!(o.compress);
202        assert_eq!(o.compress_ratio, 0.7);
203        assert_eq!(o.amd_switch, 120);
204        assert_eq!(o.coarsen_floor, 100);
205        assert_eq!(o.n_sep_trials, 5);
206        assert_eq!(o.fm_move_cap, 200);
207        assert_eq!(o.fm_pass_cap, 32);
208        assert_eq!(o.max_imbalance, 0.05);
209        assert_eq!(o.seed, 0xDEAD_BEEF);
210    }
211
212    #[test]
213    fn stats_default_is_zeros() {
214        let s = ScotchStats::default();
215        assert_eq!(s.n_compressed_out, 0);
216        assert_eq!(s.n_levels, 0);
217        assert_eq!(s.n_components, 0);
218        assert_eq!(s.n_separator_vertices, 0);
219        assert_eq!(s.n_fm_passes, 0);
220        assert_eq!(s.n_amd_leaf_calls, 0);
221    }
222
223    #[test]
224    fn contract_version_matches_core() {
225        assert_eq!(CONTRACT_VERSION, feral_ordering_core::CONTRACT_VERSION);
226    }
227
228    #[test]
229    fn scotch_order_trivial_diagonal() {
230        let cp = vec![0i32, 1, 2, 3];
231        let ri = vec![0i32, 1, 2];
232        let pat = CscPattern::new(3, &cp, &ri).unwrap();
233        let perm = scotch_order(&pat).expect("trivial 3-vertex diagonal orders");
234        assert_eq!(perm.len(), 3);
235        let mut seen = [false; 3];
236        for &p in &perm {
237            assert!((0..3).contains(&p));
238            seen[p as usize] = true;
239        }
240        assert!(seen.iter().all(|&s| s));
241    }
242
243    #[test]
244    fn scotch_order_full_populates_time_us() {
245        let cp = vec![0i32, 1, 2, 3];
246        let ri = vec![0i32, 1, 2];
247        let pat = CscPattern::new(3, &cp, &ri).unwrap();
248        let (_perm, ostats, _sstats) =
249            scotch_order_full(&pat, &ScotchOptions::default()).expect("ok");
250        // time_us is populated; fill/flop remain None.
251        assert!(ostats.fill_estimate.is_none());
252        assert!(ostats.flop_estimate.is_none());
253    }
254
255    #[test]
256    fn scotch_order_rejects_malformed_col_ptr() {
257        // col_ptr length must equal n + 1. Construct a well-formed
258        // CscPattern for n = 3, then pass it to scotch_order_full
259        // with an options struct and a lying n via a fresh pattern
260        // that fails the upstream validator.
261        let cp = vec![0i32, 1];
262        let ri: Vec<i32> = Vec::new();
263        // CscPattern::new with n=2 and col_ptr of length 2 rejects at
264        // construction; go through the public API by constructing a
265        // valid n=0 pattern and mutating — since we don't have public
266        // mutation, simply verify that CscPattern::new rejects the
267        // malformed case (the scotch_order_full guard is a defence-
268        // in-depth and is covered by tests in node_nd).
269        assert!(CscPattern::new(2, &cp, &ri).is_none());
270    }
271}
feral_scotch/lib.rs

feral_scotch/
lib.rs
