use super::CscMatrix;
use crate::domain::scalar::Scalar;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
#[must_use = "amd_order returns the fill-reducing permutation; ignoring it discards the analysis"]
pub fn amd_order<T: Scalar>(csc: &CscMatrix<T>) -> Vec<usize> {
let (nrows, ncols) = csc.shape();
debug_assert_eq!(nrows, ncols, "AMD requires a square matrix");
let n = nrows;
if n == 0 {
return Vec::new();
}
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
let col_ptr = csc.col_ptr();
let row_indices = csc.row_indices();
for j in 0..n {
for &i in &row_indices[col_ptr[j]..col_ptr[j + 1]] {
if i == j {
continue; }
adj[i].push(j);
adj[j].push(i);
}
}
for neighbors in &mut adj {
neighbors.sort_unstable();
neighbors.dedup();
}
let mut deg: Vec<usize> = adj.iter().map(Vec::len).collect();
let mut eliminated = vec![false; n];
let mut perm: Vec<usize> = Vec::with_capacity(n);
let mut heap: BinaryHeap<Reverse<(usize, usize)>> = BinaryHeap::with_capacity(n);
for (v, °ree) in deg.iter().enumerate() {
heap.push(Reverse((degree, v)));
}
while perm.len() < n {
let v = loop {
let Reverse((d, vertex)) = heap
.pop()
.expect("invariant: heap only drains when all n vertices are eliminated");
if eliminated[vertex] {
continue;
}
if deg[vertex] != d {
heap.push(Reverse((deg[vertex], vertex)));
continue;
}
break vertex;
};
eliminated[v] = true;
deg[v] = 0;
perm.push(v);
let neighbors_v: Vec<usize> = adj[v]
.iter()
.copied()
.filter(|&u| !eliminated[u])
.collect::<Vec<_>>();
for idx in 0..neighbors_v.len() {
let u = neighbors_v[idx];
for &w in neighbors_v.iter().skip(idx + 1) {
if !exists(&adj[u], w) {
insert_sorted(&mut adj[u], w);
insert_sorted(&mut adj[w], u);
deg[u] += 1;
deg[w] += 1;
}
}
}
for &u in &neighbors_v {
if !eliminated[u] {
heap.push(Reverse((deg[u], u)));
}
}
}
perm
}
fn exists(sorted: &[usize], target: usize) -> bool {
sorted.binary_search(&target).is_ok()
}
fn insert_sorted(sorted: &mut Vec<usize>, value: usize) {
match sorted.binary_search(&value) {
Ok(_) => {} Err(idx) => sorted.insert(idx, value),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::application::sparse::lu_symbolic::apply_symmetric_perm;
use crate::application::sparse::CooMatrix;
fn poisson_2d_csc(k: usize) -> CscMatrix<f64> {
let n = k * k;
let mut coo = CooMatrix::new(n, n);
let at = |i: i64, j: i64| (i * k as i64 + j) as usize;
for di in 0..k as i64 {
for dj in 0..k as i64 {
let idx = at(di, dj);
coo.push(idx, idx, 4.0);
if di > 0 {
coo.push(idx, at(di - 1, dj), -1.0);
}
if di + 1 < k as i64 {
coo.push(idx, at(di + 1, dj), -1.0);
}
if dj > 0 {
coo.push(idx, at(di, dj - 1), -1.0);
}
if dj + 1 < k as i64 {
coo.push(idx, at(di, dj + 1), -1.0);
}
}
}
coo.to_csc()
}
#[test]
fn amd_returns_permutation() {
for n in [1, 2, 4, 7, 16, 32, 100] {
let mut coo = CooMatrix::new(n, n);
for i in 0..n {
coo.push(i, i, 1.0_f64);
}
let csc = coo.to_csc();
let perm = amd_order(&csc);
assert_eq!(perm.len(), n, "len mismatch at n={n}");
let mut sorted = perm.clone();
sorted.sort_unstable();
let expected: Vec<usize> = (0..n).collect();
assert_eq!(sorted, expected, "not a permutation at n={n}: {perm:?}");
}
}
#[test]
fn amd_returns_identity_on_diagonal() {
let n = 8;
let mut coo = CooMatrix::new(n, n);
for i in 0..n {
coo.push(i, i, 1.0_f64);
}
let csc = coo.to_csc();
let perm = amd_order(&csc);
let expected: Vec<usize> = (0..n).collect();
assert_eq!(perm, expected, "diagonal should yield identity: {perm:?}");
}
#[test]
fn amd_reduces_fill_on_poisson_32() {
let k = 6usize; let csc = poisson_2d_csc(k);
let n = csc.nrows();
assert_eq!(n, 36, "6×6 grid must flatten to n=36");
let symbolic_natural = crate::application::sparse::lu_symbolic::factor_symbolic(&csc);
let natural_fill = symbolic_natural.l_nnz() + symbolic_natural.u_nnz();
let perm = amd_order(&csc);
{
let mut sorted = perm.clone();
sorted.sort_unstable();
assert_eq!(sorted, (0..n).collect::<Vec<_>>(), "amd perm invalid");
}
let permuted_csc = apply_symmetric_perm(&csc, &perm);
let symbolic_amd = crate::application::sparse::lu_symbolic::factor_symbolic(&permuted_csc);
let amd_fill = symbolic_amd.l_nnz() + symbolic_amd.u_nnz();
let reduction_ratio = (natural_fill as f64 - amd_fill as f64) / natural_fill as f64;
assert!(
amd_fill < natural_fill,
"AMD fill-SPEC: amd_fill ({amd_fill}) must be < natural_fill ({natural_fill}) \
for n=36 Poisson 5-point stencil; got reduction = {reduction_ratio:.3}"
);
assert!(
reduction_ratio >= 0.10,
"AMD reduction {reduction_ratio:.3} below the 10%-non-trivial floor \
(natural_fill={natural_fill}, amd_fill={amd_fill})"
);
}
#[test]
fn amd_reduces_fill_on_tridiagonal_64() {
let n = 64usize;
let mut coo = CooMatrix::new(n, n);
for i in 0..n {
coo.push(i, i, 2.0_f64);
if i + 1 < n {
coo.push(i, i + 1, -1.0_f64);
coo.push(i + 1, i, -1.0_f64);
}
}
let csc = coo.to_csc();
let symbolic_natural = crate::application::sparse::lu_symbolic::factor_symbolic(&csc);
let natural_fill = symbolic_natural.l_nnz() + symbolic_natural.u_nnz();
let perm = amd_order(&csc);
let permuted_csc = apply_symmetric_perm(&csc, &perm);
let symbolic_amd = crate::application::sparse::lu_symbolic::factor_symbolic(&permuted_csc);
let amd_fill = symbolic_amd.l_nnz() + symbolic_amd.u_nnz();
assert!(
amd_fill <= natural_fill,
"tridiagonal n=64: amd_fill ({amd_fill}) must not exceed natural_fill ({natural_fill})"
);
}
#[test]
fn exists_and_insert_sorted_round_trip() {
let mut s: Vec<usize> = vec![];
insert_sorted(&mut s, 3);
insert_sorted(&mut s, 1);
insert_sorted(&mut s, 5);
insert_sorted(&mut s, 1); assert_eq!(s, vec![1, 3, 5]);
assert!(exists(&s, 3));
assert!(!exists(&s, 4));
}
}