Skip to main content

finalize_step

Function finalize_step 

Source
pub fn finalize_step(
    ws: &mut Workspace,
    me: usize,
    pme1: usize,
    pme2_excl: usize,
    nvpiv: i32,
    degme: usize,
    elenme: i32,
    aggressive: bool,
) -> StepFlops
Expand description

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].

Does, in order:

  1. Pass-1 w-seeding (faer amd.rs:366-385). For each variable i in the new element, walk its element list and lazily seed w[e]: first touch sets w[e] = degree[e] + (wflg - nvi), subsequent touches do w[e] -= nvi.
  2. Pass-2 approximate external degree (amd.rs:386-462). For each variable i in the new element: walk its element list computing dext = w[e] - wflg, then its variable list accumulating nv[j] for live neighbours. Under aggressive, dead elements (dext == 0) are absorbed on the spot. The updated degree is clamped by min(degree[i], deg) (“monotone cap”). The element list is re-ordered so me sits at position p1.
  3. Mass elimination (amd.rs:436-444). A member i whose only remaining element is me (elen[i] == 1) and whose surviving variable neighbourhood is empty (p3 == pn) will pivot concurrently with me. Fold its supervariable count into nvpiv / nel and deduct from degme.
  4. Hash-bucket insertion (amd.rs:452-460): each still- marked member is placed into a hash bucket threaded through head/next/last via sign-bit encoding.
  5. Bump degree[me] = degme, lemax = max(lemax, degme), wflg += lemax, wflg = clear_flag(...).
  6. Supervariable detection (amd.rs:467-515): for each hash chain whose anchor is still marked, walk the chain and merge indistinguishable followers into the head.
  7. Re-insert (amd.rs:516-537): each surviving variable’s updated degree is pushed back onto head[deg] LIFO and mindeg is lowered if needed.
  8. Me bookkeeping (amd.rs:538-546): restore nv[me] = nvpiv, compact me’s var list to [pme1, p), trim pfree.
  9. Flop counters (amd.rs:547-557).