Module quotient_graph 

Shared quotient-graph machinery for AMD-family bottom-up orderings.

This module hosts the workspace, elimination loop, and assembly- tree postorder used by feral-amd and (planned) feral-amf. Both orderings share the quotient-graph data structures (PE / IW / LEN / NV / ELEN), the standard / aggressive element absorption logic, the mass-elimination fast path, the supervariable hash bucket detection, and the inline garbage collector. They differ only in the selection metric — approximate degree (AMD) vs approximate fill (AMF) — which is abstracted behind the Metric trait. Phase A shipped the trait plus the AMD-specialised MinDegree impl; Phase B.2 added MinFill driving the parallel run_elimination_amf / create_element_amf / select_pivot_amf / finalize_step_amf family in algo.rs. The duplicated inner loops trade LoC for a zero-risk AMD bit-parity contract.

Reference: Amestoy, Davis, Duff (1996) “An approximate minimum degree ordering algorithm,” SIAM J. Matrix Analysis 17:886-905; Amestoy (1999) habilitation thesis (AMF metric).

Structs

MinDegree

Minimum-degree metric — the AMD selection rule of Amestoy, Davis, Duff (1996).

MinFill

Approximate Minimum Fill metric (HAMF4) — Amestoy 1999 thesis.

OrderDiagnostics

Diagnostic counters extracted from a completed Workspace.

StepFlops

Flop-counter deltas produced by a single elimination step. Matches faer’s amd.rs:547-557 accounting so AmdStats can accumulate consistent ndiv / nms_ldl / nms_lu totals.

Workspace

In-memory workspace for one AMD run.

WorkspaceOptions

Tunable parameters for the shared quotient-graph workspace.

Constants

NONE

Sentinel for “no index” in the i32 arrays.

Traits

Metric

Selection metric for an AMD-family bottom-up ordering.

Functions

clear_flag

Reset the generation counter wflg without visiting iw.

create_element

Build the new element me by merging the (variable) tail of me’s list with every element e already in me’s list.

create_element_amf

AMF analogue of create_element. Identical structure; differs only in the bucket-index used when unlinking absorbed neighbours from their degree lists. AMD reads degree[i] (which doubles as the bucket index because AMD’s bucket is identity); AMF computes amf_bucket_of(wf[i], n) because the AMF score and running degree are stored in distinct fields (wf vs degree).

finalize_permutation

Consume the post-elimination state and produce the final permutation.

finalize_step

Finish the elimination step whose create-element phase produced (pme1, pme2_excl, nvpiv, degme) and left nv[me] = -nvpiv and nv[i] = -nv[i] for every variable i ∈ iw[pme1..pme2_excl].

finalize_step_amf

AMF analogue of finalize_step. The Pass-1 element seeding, hash-bucket detection, and supervariable-merge structure mirror AMD; the per-iteration accumulator carries the AMF triple (deg, wf3, wf4) (Amestoy 1999 thesis), and the re-insertion computes the quantized RMF score and inserts at head[amf_bucket_of(wf[i], n)].

flip

Sentinel encoding used by the quotient graph: flip(x) = -2 - x. Used to mark absorbed elements (pe[e] < 0 ⇒ flip(parent)) and as a tag on elen for freshly eliminated zero-degree variables.

order

Run a metric-driven AMD-family ordering on a full-symmetric pattern, returning the permutation plus diagnostic counters.

run_elimination

Run the main AMD elimination loop until every live supervariable has been either pivoted or dense-deferred. Returns the accumulated flop counts.

run_elimination_amf

AMF analogue of run_elimination.

select_pivot

Scan head from ws.mindeg upward and return the first non-empty degree-list head. Unlink the chosen variable. Returns None if no bucket in [ws.mindeg, ws.n) is non-empty (i.e. all remaining supervariables have been dense-deferred and the main loop should stop).

select_pivot_amf

AMF analogue of select_pivot. Linear-scans coarse buckets (idx > n) for the entry with the smallest exact score; takes the head for fine buckets.