pub fn finalize_step(
ws: &mut Workspace,
me: usize,
pme1: usize,
pme2_excl: usize,
nvpiv: i32,
degme: usize,
elenme: i32,
aggressive: bool,
) -> StepFlopsExpand 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:
- Pass-1 w-seeding (faer
amd.rs:366-385). For each variableiin the new element, walk its element list and lazily seedw[e]: first touch setsw[e] = degree[e] + (wflg - nvi), subsequent touches dow[e] -= nvi. - Pass-2 approximate external degree (
amd.rs:386-462). For each variableiin the new element: walk its element list computingdext = w[e] - wflg, then its variable list accumulatingnv[j]for live neighbours. Underaggressive, dead elements (dext == 0) are absorbed on the spot. The updated degree is clamped bymin(degree[i], deg)(“monotone cap”). The element list is re-ordered somesits at positionp1. - Mass elimination (
amd.rs:436-444). A memberiwhose only remaining element isme(elen[i] == 1) and whose surviving variable neighbourhood is empty (p3 == pn) will pivot concurrently withme. Fold its supervariable count intonvpiv/neland deduct fromdegme. - Hash-bucket insertion (
amd.rs:452-460): each still- marked member is placed into a hash bucket threaded throughhead/next/lastvia sign-bit encoding. - Bump
degree[me] = degme,lemax = max(lemax, degme),wflg += lemax,wflg = clear_flag(...). - 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. - Re-insert (
amd.rs:516-537): each surviving variable’s updated degree is pushed back ontohead[deg]LIFO andmindegis lowered if needed. - Me bookkeeping (
amd.rs:538-546): restorenv[me] = nvpiv, compactme’s var list to[pme1, p), trimpfree. - Flop counters (
amd.rs:547-557).