use crate::fea::{PIVOT_TOL_BASE, SparseMatrix};
pub const MAX_DENSE_PROBE_DOF: usize = 500;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DiagnosticLimit {
SystemTooLarge,
NotSymmetric,
NotPositiveSemidefinite,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum StructuralDiagnostic {
Stable,
RigidBodyMode {
n_free: usize,
rank: usize,
rigid_modes: usize,
},
Mechanism {
n_free: usize,
rank: usize,
},
IllConditioned {
n_free: usize,
rank: usize,
},
Indeterminate {
n_free: usize,
reason: DiagnosticLimit,
},
}
impl StructuralDiagnostic {
pub fn is_stable(&self) -> bool {
matches!(self, Self::Stable)
}
pub fn is_mechanism(&self) -> bool {
matches!(self, Self::RigidBodyMode { .. } | Self::Mechanism { .. })
}
}
impl std::fmt::Display for StructuralDiagnostic {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Stable => {
write!(f, "stable (full structural rank, not numerically singular)")
}
Self::RigidBodyMode {
n_free,
rank,
rigid_modes,
} => write!(
f,
"rigid-body mechanism: {rigid_modes} unrestrained rigid-body mode(s) \
({n_free} free DOFs, system rank {rank}); restrain the remaining \
translations/rotation"
),
Self::Mechanism { n_free, rank } => write!(
f,
"structural mechanism: rank deficient by {} of {n_free} free DOFs \
(rank {rank}); the structure has an internal zero-energy mode",
n_free - rank
),
Self::IllConditioned { n_free, rank } => write!(
f,
"numerically ill-conditioned: structurally full rank ({rank} of \
{n_free} free DOFs) but the raw reduced system is singular to the \
probe's scale-relative tolerance"
),
Self::Indeterminate { n_free, reason } => match reason {
DiagnosticLimit::SystemTooLarge => write!(
f,
"indeterminate: {n_free} free DOFs exceed the bounded dense probe \
({MAX_DENSE_PROBE_DOF})"
),
DiagnosticLimit::NotSymmetric => {
write!(f, "indeterminate: reduced matrix is not symmetric")
}
DiagnosticLimit::NotPositiveSemidefinite => write!(
f,
"indeterminate: reduced matrix is not positive semi-definite"
),
},
}
}
}
pub fn diagnose_reduced(
k_ff: &SparseMatrix,
rigid_candidates: &[Vec<f64>],
) -> StructuralDiagnostic {
let n = k_ff.n;
if n == 0 {
return StructuralDiagnostic::Stable;
}
if n > MAX_DENSE_PROBE_DOF {
return StructuralDiagnostic::Indeterminate {
n_free: n,
reason: DiagnosticLimit::SystemTooLarge,
};
}
let mut probe = k_ff.clone();
probe.compress();
if !probe.is_symmetric(1e-12) {
return StructuralDiagnostic::Indeterminate {
n_free: n,
reason: DiagnosticLimit::NotSymmetric,
};
}
let a = match to_dense(&probe) {
Some(a) => a,
None => {
return StructuralDiagnostic::Indeterminate {
n_free: n,
reason: DiagnosticLimit::NotSymmetric,
};
}
};
let scale = max_abs(&a);
if scale.is_nan() {
return StructuralDiagnostic::Indeterminate {
n_free: n,
reason: DiagnosticLimit::NotSymmetric,
};
}
if scale <= 0.0 {
return StructuralDiagnostic::Mechanism { n_free: n, rank: 0 };
}
let (equilibrated, equilibrating) = equilibrate(&a);
let eq_scale = max_abs(&equilibrated);
let structural = match pivoted_cholesky(&equilibrated, eq_scale) {
Some(o) => o,
None => {
return StructuralDiagnostic::Indeterminate {
n_free: n,
reason: DiagnosticLimit::NotPositiveSemidefinite,
};
}
};
let nullity = n - structural.rank;
if nullity > 0 {
return if structural.residual > PIVOT_TOL_BASE * eq_scale {
StructuralDiagnostic::IllConditioned {
n_free: n,
rank: structural.rank,
}
} else {
let rigid = rigid_nullity(&equilibrated, &equilibrating, rigid_candidates);
if rigid >= nullity {
StructuralDiagnostic::RigidBodyMode {
n_free: n,
rank: structural.rank,
rigid_modes: rigid,
}
} else {
StructuralDiagnostic::Mechanism {
n_free: n,
rank: structural.rank,
}
}
};
}
match pivoted_cholesky(&a, scale) {
Some(raw) if raw.rank == n => StructuralDiagnostic::Stable,
Some(_) => StructuralDiagnostic::IllConditioned {
n_free: n,
rank: structural.rank,
},
None => StructuralDiagnostic::Indeterminate {
n_free: n,
reason: DiagnosticLimit::NotPositiveSemidefinite,
},
}
}
struct CholeskyOutcome {
rank: usize,
residual: f64,
}
fn to_dense(m: &SparseMatrix) -> Option<Vec<Vec<f64>>> {
let n = m.n;
let mut a = vec![vec![0.0f64; n]; n];
for (i, row) in a.iter_mut().enumerate() {
for k in m.row_ptr()[i]..m.row_ptr()[i + 1] {
row[m.csr_cols()[k]] = m.csr_vals()[k];
}
}
if a.iter().flatten().all(|v| v.is_finite()) {
Some(a)
} else {
None
}
}
fn max_abs(m: &[Vec<f64>]) -> f64 {
let mut s = 0.0f64;
for row in m {
for &v in row {
if !v.is_finite() {
return f64::NAN;
}
s = s.max(v.abs());
}
}
s
}
fn equilibrate(m: &[Vec<f64>]) -> (Vec<Vec<f64>>, Vec<f64>) {
let n = m.len();
let mut d = vec![0.0f64; n];
for (i, di) in d.iter_mut().enumerate() {
let dii = m[i][i];
if dii > 0.0 {
*di = 1.0 / dii.sqrt();
}
}
let mut out = vec![vec![0.0f64; n]; n];
for i in 0..n {
for j in 0..n {
out[i][j] = m[i][j] * d[i] * d[j];
}
}
(out, d)
}
fn pivoted_cholesky(m: &[Vec<f64>], scale: f64) -> Option<CholeskyOutcome> {
let n = m.len();
if !scale.is_finite() {
return None;
}
if scale <= 0.0 {
return Some(CholeskyOutcome {
rank: 0,
residual: 0.0,
});
}
let tol = n as f64 * f64::EPSILON * scale;
let mut a = m.to_vec();
for k in 0..n {
let mut p = k;
for i in (k + 1)..n {
if a[i][i] > a[p][p] {
p = i;
}
}
let pivot = a[p][p];
if pivot < -tol {
return None; }
if pivot <= tol {
return Some(CholeskyOutcome {
rank: k,
residual: pivot,
});
}
if p != k {
a.swap(k, p); for row in a.iter_mut() {
row.swap(k, p); }
}
for row in a.iter_mut().skip(k + 1) {
row[k] /= pivot;
}
let l: Vec<f64> = a[k + 1..].iter().map(|row| row[k]).collect();
for (offset, row) in a[k + 1..].iter_mut().enumerate() {
let lik = l[offset];
for (j, value) in row.iter_mut().enumerate().skip(k + 1) {
*value -= lik * l[j - k - 1] * pivot;
}
}
}
Some(CholeskyOutcome {
rank: n,
residual: 0.0,
})
}
fn rigid_nullity(equilibrated: &[Vec<f64>], d: &[f64], candidates: &[Vec<f64>]) -> usize {
let n = equilibrated.len();
if d.contains(&0.0) {
return 0;
}
let dependent_tol = n as f64 * f64::EPSILON;
let mut basis: Vec<Vec<f64>> = Vec::new();
for c in candidates {
if c.len() != n {
continue;
}
let mut y: Vec<f64> = (0..n).map(|i| c[i] / d[i]).collect();
let norm0 = norm(&y);
if norm0 <= 0.0 {
continue; }
for b in &basis {
let projection = dot(&y, b);
for i in 0..n {
y[i] -= projection * b[i];
}
}
let norm = norm(&y);
if norm <= dependent_tol * norm0 {
continue; }
for v in y.iter_mut() {
*v /= norm;
}
basis.push(y);
}
let m = basis.len();
if m == 0 {
return 0;
}
let mut energy = vec![vec![0.0f64; m]; m];
for p in 0..m {
for q in 0..m {
let mut s = 0.0f64;
for i in 0..n {
let mut row = 0.0f64;
for j in 0..n {
row += equilibrated[i][j] * basis[q][j];
}
s += basis[p][i] * row;
}
energy[p][q] = s;
}
}
let rank = pivoted_cholesky(&energy, 1.0).map(|o| o.rank).unwrap_or(m);
m - rank
}
fn dot(a: &[f64], b: &[f64]) -> f64 {
a.iter().zip(b.iter()).map(|(x, y)| x * y).sum()
}
fn norm(a: &[f64]) -> f64 {
dot(a, a).sqrt()
}