use super::amd::amd_order;
use super::lu_sparse::OrderingStrategy;
use super::CscMatrix;
use crate::domain::scalar::Scalar;
#[derive(Debug, Clone)]
#[must_use = "SymbolicLu carries the static L/U pattern consumed by factor_numeric"]
pub struct SymbolicLu {
pub n: usize,
pub l_col_ptr: Vec<usize>,
pub l_row_indices: Vec<usize>,
pub u_col_ptr: Vec<usize>,
pub u_row_indices: Vec<usize>,
pub amd_col_perm: Option<Vec<usize>>,
}
impl SymbolicLu {
#[must_use]
#[inline]
pub fn n(&self) -> usize {
self.n
}
#[must_use]
#[inline]
pub fn l_nnz(&self) -> usize {
self.l_row_indices.len()
}
#[must_use]
#[inline]
pub fn u_nnz(&self) -> usize {
self.u_row_indices.len()
}
}
pub fn factor_symbolic<T: Scalar>(csc: &CscMatrix<T>) -> SymbolicLu {
let (nrows, ncols) = csc.shape();
debug_assert_eq!(nrows, ncols, "sparse LU requires a square matrix");
let n = nrows;
let col_ptr = csc.col_ptr();
let row_indices = csc.row_indices();
let mut marked: Vec<bool> = vec![false; n]; let mut reach: Vec<usize> = Vec::with_capacity(n); let mut sweep: Vec<usize> = Vec::with_capacity(n);
let mut u_col_ptr = Vec::with_capacity(n + 1);
let mut u_row_indices: Vec<usize> = Vec::new();
let mut l_col_ptr = Vec::with_capacity(n + 1);
let mut l_row_indices: Vec<usize> = Vec::new();
u_col_ptr.push(0);
l_col_ptr.push(0);
for j in 0..n {
reach.clear();
sweep.clear();
for &r in row_indices.iter().take(col_ptr[j + 1]).skip(col_ptr[j]) {
if !marked[r] {
marked[r] = true;
reach.push(r);
}
}
if !marked[j] {
marked[j] = true;
reach.push(j);
}
let mut head = 0usize;
while head < reach.len() {
let k = reach[head];
head += 1;
if k >= j {
continue; }
for &r in l_row_indices
.iter()
.take(l_col_ptr[k + 1])
.skip(l_col_ptr[k])
{
if !marked[r] {
marked[r] = true;
reach.push(r);
}
}
}
sweep.extend_from_slice(&reach);
sweep.sort_unstable();
for &r in &sweep {
if r <= j {
u_row_indices.push(r);
} else {
l_row_indices.push(r);
}
}
u_col_ptr.push(u_row_indices.len());
l_col_ptr.push(l_row_indices.len());
for &r in &reach {
marked[r] = false;
}
debug_assert!(
marked.iter().all(|&m| !m),
"mark array not fully cleared at column {j}"
);
}
SymbolicLu {
n,
l_col_ptr,
l_row_indices,
u_col_ptr,
u_row_indices,
amd_col_perm: None,
}
}
#[must_use = "factor_symbolic_with_ordering carries the L/U pattern consumed by factor_numeric"]
pub fn factor_symbolic_with_ordering<T: Scalar>(
csc: &CscMatrix<T>,
strategy: OrderingStrategy,
) -> SymbolicLu {
match strategy {
OrderingStrategy::Natural => factor_symbolic(csc),
OrderingStrategy::AmdApproxMinDegree => {
let perm = amd_order(csc);
let permuted_csc = apply_symmetric_perm(csc, &perm);
let mut symbolic = factor_symbolic(&permuted_csc);
symbolic.amd_col_perm = Some(perm);
symbolic
}
}
}
pub(super) fn apply_symmetric_perm<T: Scalar>(csc: &CscMatrix<T>, perm: &[usize]) -> CscMatrix<T> {
let n = csc.nrows();
debug_assert_eq!(csc.ncols(), n);
debug_assert_eq!(perm.len(), n);
let mut inv = vec![0usize; n];
for (slot, &orig) in perm.iter().enumerate() {
inv[orig] = slot;
}
let col_ptr = csc.col_ptr();
let row_indices = csc.row_indices();
let values = csc.values();
let mut coo = super::CooMatrix::new(n, n);
for j in 0..n {
for p in col_ptr[j]..col_ptr[j + 1] {
let i = row_indices[p];
coo.push(inv[i], inv[j], values[p]);
}
}
coo.to_csc()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::application::sparse::{CooMatrix, OrderingStrategy};
fn csc2(entries: &[(usize, usize, f64)]) -> CscMatrix<f64> {
let n = 2;
let mut coo = CooMatrix::new(n, n);
for &(i, j, v) in entries {
coo.push(i, j, v);
}
coo.to_csc()
}
fn csc3(entries: &[(usize, usize, f64)]) -> CscMatrix<f64> {
let mut coo = CooMatrix::new(3, 3);
for &(i, j, v) in entries {
coo.push(i, j, v);
}
coo.to_csc()
}
#[test]
fn storage_convention_holds_for_a_full_column() {
let csc = csc3(&[(0, 0, 2.0), (1, 0, 3.0), (2, 0, 5.0)]);
let sym = factor_symbolic(&csc);
assert_eq!(sym.n(), 3);
assert_eq!(sym.u_row_indices, vec![0, 1, 2]);
assert_eq!(sym.l_row_indices, vec![1, 2]);
assert_eq!(sym.u_col_ptr, vec![0, 1, 2, 3]);
assert_eq!(sym.l_col_ptr, vec![0, 2, 2, 2]);
}
#[test]
fn diagonal_is_always_structurally_present_in_u() {
let csc = csc2(&[(1, 0, 4.0)]);
let sym = factor_symbolic(&csc);
assert_eq!(sym.u_row_indices, vec![0, 1]);
assert_eq!(sym.l_row_indices, vec![1]);
assert_eq!(sym.u_col_ptr, vec![0, 1, 2]);
assert_eq!(sym.l_col_ptr, vec![0, 1, 1]);
assert_eq!(sym.u_nnz(), 2);
assert_eq!(sym.l_nnz(), 1);
}
#[test]
fn identity_has_no_l_fill() {
let csc = csc3(&[(0, 0, 1.0), (1, 1, 1.0), (2, 2, 1.0)]);
let sym = factor_symbolic(&csc);
assert_eq!(sym.u_nnz(), 3);
assert_eq!(sym.l_nnz(), 0);
assert_eq!(sym.u_row_indices, vec![0, 1, 2]);
}
#[test]
fn fill_upper_bound_on_dense_2x2() {
let csc = csc2(&[(0, 1, 1.0), (1, 0, 1.0)]);
let sym = factor_symbolic(&csc);
assert_eq!(sym.u_row_indices, vec![0, 0, 1]);
assert_eq!(sym.l_row_indices, vec![1]);
assert_eq!(sym.u_nnz(), 3);
assert_eq!(sym.l_nnz(), 1);
}
#[test]
fn symmetric_perm_preserves_identity_pattern() {
let csc = csc3(&[(0, 0, 1.0), (1, 1, 1.0), (2, 2, 1.0)]);
let perm = vec![2usize, 0, 1];
let permuted = apply_symmetric_perm(&csc, &perm);
let sym = factor_symbolic(&permuted);
assert_eq!(sym.u_nnz(), 3);
assert_eq!(sym.l_nnz(), 0);
}
#[test]
fn amd_ordering_produces_valid_permuted_pattern() {
let csc = csc3(&[(0, 2, 1.0), (2, 0, 1.0), (1, 1, 1.0)]);
let sym = factor_symbolic_with_ordering(&csc, OrderingStrategy::AmdApproxMinDegree);
let perm = sym.amd_col_perm.as_ref().expect("AMD yields a perm");
assert_eq!(perm.len(), 3);
let mut seen = [false; 3];
for &p in perm {
assert!(!seen[p], "AMD permutation must be a bijection");
seen[p] = true;
}
for j in 0..sym.n() {
let u = &sym.u_row_indices[sym.u_col_ptr[j]..sym.u_col_ptr[j + 1]];
let l = &sym.l_row_indices[sym.l_col_ptr[j]..sym.l_col_ptr[j + 1]];
assert!(u.iter().all(|&r| r <= j), "U col {j} rows must be ≤ {j}");
assert!(l.iter().all(|&r| r > j), "L col {j} rows must be > {j}");
assert!(u.iter().is_sorted(), "U col {j} rows must be ascending");
assert!(l.iter().is_sorted(), "L col {j} rows must be ascending");
}
}
#[test]
fn natural_ordering_has_no_col_perm() {
let csc = csc2(&[(0, 1, 1.0), (1, 0, 1.0)]);
let sym = factor_symbolic_with_ordering(&csc, OrderingStrategy::Natural);
assert!(sym.amd_col_perm.is_none());
}
}