Crate feral_scotch 

SCOTCH-style nested-dissection fill-reducing ordering.

Clean-room pure-Rust implementation of the algorithms described in Pellegrini, “SCOTCH: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs” (HPCN Europe, 1996), §3. This crate provides an alternative to feral_metis with:

• Graph compression (supervariable merging before partitioning).
• Direct vertex-separator FM (tighter separators than edge-cut conversion on structured meshes).
• Adaptive refinement (boundary / halo FM). A band-FM refiner (band_fm) is implemented and unit-tested but is not yet wired into the default ND driver.

The public surface conforms to the FERAL ordering-crate contract (dev/plans/ordering-crate-contract.md): CscPattern, OrderingStats, OrderingError, and CONTRACT_VERSION are re-exported from feral-ordering-core.

Status: S1–S5 complete. scotch_order and scotch_order_full run the full pipeline — graph compression, connected-component split, multilevel coarsening, best-of- n_sep_trials initial bisection, halo-FM uncoarsening, direct vertex separator, and recursive ND with an AMD leaf fallback.

Clean-room provenance

No code is copied or paraphrased from SCOTCH’s C source (libscotch/, CeCILL-C). Algorithms are reconstructed from Pellegrini 1996 §3 and the research notes under dev/research/. Constants, data layouts, and hash choices are independently justified and documented per-module.

Structs

CscPattern

Borrowed symmetric sparsity pattern in CSC form.

OrderingStats

Diagnostic counters shared by every ordering producer.

ScotchOptions

Tunable parameters for SCOTCH nested-dissection ordering.

ScotchStats

Crate-specific diagnostic counters for SCOTCH nested dissection.

Enums

OrderingError

Shared error shape for the ordering-crate contract.

Constants

CONTRACT_VERSION

Version of the shared ordering-crate contract.

Functions

scotch_order

Compute a fill-reducing SCOTCH nested-dissection ordering.

scotch_order_full

Contract-conforming ordering producer.