Struct MetisOptions 

pub struct MetisOptions {
    pub seed: u64,
    pub niparts: u32,
    pub coarsen_floor: u32,
    pub nd_to_amd_switch: u32,
    pub two_hop_ratio_threshold: f64,
    pub max_imbalance: f64,
    pub fm_passes: u32,
    pub node_refine: bool,
    pub dense_quotient_enabled: bool,
    pub dense_quotient_threshold: Option<usize>,
}

Tunable parameters for METIS nested-dissection ordering.

Defaults mirror METIS 5.2.0’s METIS_NodeND defaults as documented in dev/plans/ordering-metis.md audit (MUMPS uses stock METIS defaults for KKT problems: METIS_OPTION_NUMBERING = 1, all other options at library default).

Fields

seed: u64

Deterministic RNG seed. Defaults to 1. Two runs with the same seed on the same input must produce the same permutation.

niparts: u32

Number of initial-bisection trials at the coarsest level (METIS 5.2.0 default: 7). Each trial alternates GGP and random BFS and is scored on its post-FM cut.

coarsen_floor: u32

Stop coarsening when the graph has fewer than this many vertices (METIS 5.2.0 default: 120).

nd_to_amd_switch: u32

Switch from recursive ND to AMD on uncoarsened subproblems of at most this many vertices (METIS 5.2.0 default: 200).

two_hop_ratio_threshold: f64

Reduction-ratio threshold below which SHEM falls back to 2-hop matching (METIS 5.2.0 default: 0.85).

max_imbalance: f64

Maximum partition imbalance factor (ufactor in METIS terms, encoded as a fraction here). METIS 5.2.0 uses 200, which corresponds to 1.20 load balance tolerance; expressed as the fractional deviation 0.20.

fm_passes: u32

Number of FM passes at each uncoarsening level (METIS 5.2.0 default: 10).

node_refine: bool

Carry the node separator through uncoarsening and refine it with FM at every level (METIS’s Refine2WayNode / FM_2WayNodeRefine1Sided), instead of refining the edge cut through uncoarsening and converting to a separator once at the finest level.

Default: true. The two paths share coarsening and initial bisection; they differ only in what the uncoarsening loop optimises. Measured against MA57’s bundled real METIS as the oracle (dev/research/feral-metis-node-separator-fm-2026-09-17.md), on the six matrices in this repo large enough for nested dissection to engage, node_refine cuts the elimination flop count by 2.4-3.5x on collocation KKTs. It is not a uniform win: measured in wall-clock on grid Laplacians (min over 3 runs of 5 pairs each, non-overlapping), a 40^3 grid factors 12.8% faster while a 300x300 grid factors 5.8% slower despite 10.3% less fill — one more case of fill not predicting speed. On every other matrix measured (seven real IPM families up to n=607,500, and 37 of 38 parity matrices) the permutation is bit-identical, so there is nothing to win or lose.

Set to false to recover the pre-2026-09-17 edge-cut behaviour.

dense_quotient_enabled: bool

Pull near-dense columns out of the ND graph before recursive bisection and append them at the end of the returned permutation.

Default: false. The technique was implemented to mimic what we believed MUMPS’s ICNTL(6) and SSIDS did, but expert review of the MUMPS and SPRAL sources (2026-04-27) found: (a) ICNTL(6) is MC64 matching, not dense-row removal; (b) MUMPS handles dense rows inside its AMD/AMF (MUMPS_QAMD in ana_orderings.F:5226+ with the THRESM parameter and HEAD(N) quasi-dense list); and (c) SSIDS does not special-case dense rows at all — it relies on METIS placing them in the top separator and supernodal amalgamation collapsing the resulting chain into one dense BLAS-3 root frontal. Neither solver pre-strips the graph. Empirically, on ORBIT2_0000 (n=4795, one column of off-degree 1794) Fix A increased nnz_L from 1.54M to 2.25M because removing the dense column destroys the structural signal that makes it the natural top separator. The opt-in path is kept for diagnostic experimentation; the correct fix lives in feral-amd (a QAMD-style deferral, future work).

References (kept for the opt-in code path):

• Davis & Hager, “Dynamic supernodes in sparse Cholesky update/downdate and triangular solves” (2009), §3.2.
• Davis (1996) AMD paper, §5 (“dense rows / Alpha parameter”).
• MUMPS source: ana_orderings.F:5226-5650 (QAMD).

dense_quotient_threshold: Option<usize>

Override the off-diagonal-degree threshold above which a column is treated as quasi-dense.

When None (the default) the threshold is computed as max(40, ceil(10 * sqrt(n))) per Davis & Hager / AMD §5. Set to Some(usize::MAX) to effectively disable the quotient without flipping dense_quotient_enabled (useful for regression sweeps).

Trait Implementations

impl Clone for MetisOptions

fn clone(&self) -> MetisOptions

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MetisOptions

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for MetisOptions

fn default() -> Self

Returns the “default value” for a type.