pub fn amd(n: usize, col_ptr: &[usize], row_idx: &[usize]) -> Vec<usize>Expand description
Approximate minimum degree ordering (Amestoy, Davis & Duff 1996) - the fill-reducing elimination order for a symmetric sparse matrix.
Returns order where order[k] is the original node eliminated k-th, ready for
SparseLdlt::factor_perm. Graph-symmetric input: only the upper triangle
(row <= col) is read, exactly like SparseLdlt::factor.
THE ALGORITHM: quotient-graph AMD, faithfully. Eliminated nodes become elements (their neighbour list, attached to surviving neighbours in O(1) - the structure that keeps the total update work proportional to the factor’s nonzero count instead of the filled graph’s). Degrees are AMD’s external degrees: the count of distinct live variables reachable through a node’s own adjacency plus its attached elements, recomputed only for the neighbours of each elimination (the only nodes whose degree changes). Aggressive absorption (AMD’s later refinement) is not implemented; on FE-sized problems the fill difference is small and the code stays auditable.
Inertia is INVARIANT under the resulting symmetric permutation (Sylvester’s law), so ordering changes cost, never eigenvalue counts.