use crate::error::{BarracudaError, Result};
#[derive(Debug, Clone)]
pub struct EighDecomposition {
pub eigenvalues: Vec<f64>,
pub eigenvectors: Vec<f64>,
pub n: usize,
}
impl EighDecomposition {
#[must_use]
pub fn eigenvector(&self, i: usize) -> Option<Vec<f64>> {
if i >= self.n {
return None;
}
let mut v = vec![0.0; self.n];
for (row, v_row) in v.iter_mut().enumerate() {
*v_row = self.eigenvectors[row * self.n + i];
}
Some(v)
}
pub fn sort_descending(&mut self) {
let n = self.n;
let mut perm: Vec<usize> = (0..n).collect();
perm.sort_by(|&a, &b| {
self.eigenvalues[b]
.partial_cmp(&self.eigenvalues[a])
.unwrap_or(std::cmp::Ordering::Equal)
});
let new_vals: Vec<f64> = perm.iter().map(|&i| self.eigenvalues[i]).collect();
let mut new_vecs = vec![0.0; n * n];
for (new_col, &old_col) in perm.iter().enumerate() {
for row in 0..n {
new_vecs[row * n + new_col] = self.eigenvectors[row * n + old_col];
}
}
self.eigenvalues = new_vals;
self.eigenvectors = new_vecs;
}
#[must_use]
pub fn reconstruct(&self) -> Vec<f64> {
let mut a = vec![0.0; self.n * self.n];
for i in 0..self.n {
for j in 0..self.n {
let mut sum = 0.0;
for k in 0..self.n {
let vik = self.eigenvectors[i * self.n + k];
let vjk = self.eigenvectors[j * self.n + k];
sum = (vik * self.eigenvalues[k]).mul_add(vjk, sum);
}
a[i * self.n + j] = sum;
}
}
a
}
#[must_use]
pub fn trace(&self) -> f64 {
self.eigenvalues.iter().sum()
}
#[must_use]
pub fn det(&self) -> f64 {
self.eigenvalues.iter().product()
}
}
pub fn eigh_f64(a: &[f64], n: usize) -> Result<EighDecomposition> {
if a.len() != n * n {
return Err(BarracudaError::InvalidInput {
message: format!("Matrix has {} elements, expected {}×{}", a.len(), n, n),
});
}
if n == 0 {
return Err(BarracudaError::InvalidInput {
message: "Matrix dimension must be positive".to_string(),
});
}
let sym_tol = 1e-10 * a.iter().fold(0.0_f64, |mx, &v| mx.max(v.abs())).max(1e-15);
for i in 0..n {
for j in (i + 1)..n {
let diff = (a[i * n + j] - a[j * n + i]).abs();
if diff > sym_tol {
return Err(BarracudaError::InvalidInput {
message: format!(
"Matrix is not symmetric: A[{i},{j}]={} vs A[{j},{i}]={} (diff={diff:.2e})",
a[i * n + j],
a[j * n + i],
),
});
}
}
}
if n == 1 {
return Ok(EighDecomposition {
eigenvalues: vec![a[0]],
eigenvectors: vec![1.0],
n: 1,
});
}
let mut d = a.to_vec();
let mut v = vec![0.0; n * n];
for i in 0..n {
v[i * n + i] = 1.0;
}
const MAX_SWEEPS: usize = 50;
const TOL: f64 = 1e-14;
for _ in 0..MAX_SWEEPS {
let mut max_off = 0.0;
let mut p = 0;
let mut q = 0;
for i in 0..n {
for j in (i + 1)..n {
let val = d[i * n + j].abs();
if val > max_off {
max_off = val;
p = i;
q = j;
}
}
}
if max_off < TOL {
break;
}
let app = d[p * n + p];
let aqq = d[q * n + q];
let apq = d[p * n + q];
let (c, s) = if (aqq - app).abs() < TOL {
let c = std::f64::consts::FRAC_1_SQRT_2;
let s = c * apq.signum();
(c, s)
} else {
let tau = (aqq - app) / (2.0 * apq);
let t = if tau >= 0.0 {
1.0 / (tau + (1.0 + tau * tau).sqrt())
} else {
1.0 / (tau - (1.0 + tau * tau).sqrt())
};
let c = 1.0 / (1.0 + t * t).sqrt();
let s = t * c;
(c, s)
};
for k in 0..n {
if k != p && k != q {
let dkp = d[k * n + p];
let dkq = d[k * n + q];
d[k * n + p] = c.mul_add(dkp, -(s * dkq));
d[p * n + k] = d[k * n + p];
d[k * n + q] = s.mul_add(dkp, c * dkq);
d[q * n + k] = d[k * n + q];
}
}
let new_pp = (s * s).mul_add(aqq, (c * c).mul_add(app, -(2.0 * c * s * apq)));
let new_qq = (c * c).mul_add(aqq, (s * s).mul_add(app, 2.0 * c * s * apq));
d[p * n + p] = new_pp;
d[q * n + q] = new_qq;
d[p * n + q] = 0.0;
d[q * n + p] = 0.0;
for k in 0..n {
let vkp = v[k * n + p];
let vkq = v[k * n + q];
v[k * n + p] = c.mul_add(vkp, -(s * vkq));
v[k * n + q] = s.mul_add(vkp, c * vkq);
}
}
let mut eigenvalues: Vec<f64> = (0..n).map(|i| d[i * n + i]).collect();
let mut indexed: Vec<(usize, f64)> = eigenvalues.iter().copied().enumerate().collect();
indexed.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
let sorted_vals: Vec<f64> = indexed.iter().map(|(_, val)| *val).collect();
let mut sorted_vecs = vec![0.0; n * n];
for (new_idx, (old_idx, _)) in indexed.iter().enumerate() {
for row in 0..n {
sorted_vecs[row * n + new_idx] = v[row * n + old_idx];
}
}
eigenvalues = sorted_vals;
Ok(EighDecomposition {
eigenvalues,
eigenvectors: sorted_vecs,
n,
})
}
#[cfg(test)]
mod tests {
use super::*;
fn approx_eq(a: f64, b: f64, tol: f64) -> bool {
(a - b).abs() < tol
}
#[test]
fn test_eigh_2x2_simple() {
let a = vec![3.0, 1.0, 1.0, 3.0];
let eig = eigh_f64(&a, 2).unwrap();
assert!(approx_eq(eig.eigenvalues[0], 2.0, 1e-10));
assert!(approx_eq(eig.eigenvalues[1], 4.0, 1e-10));
assert!(approx_eq(eig.trace(), 6.0, 1e-10));
assert!(approx_eq(eig.det(), 8.0, 1e-10));
}
#[test]
fn test_eigh_identity() {
let a = vec![1.0, 0.0, 0.0, 1.0];
let eig = eigh_f64(&a, 2).unwrap();
assert!(approx_eq(eig.eigenvalues[0], 1.0, 1e-10));
assert!(approx_eq(eig.eigenvalues[1], 1.0, 1e-10));
}
#[test]
fn test_eigh_diagonal() {
let a = vec![5.0, 0.0, 0.0, 3.0];
let eig = eigh_f64(&a, 2).unwrap();
assert!(approx_eq(eig.eigenvalues[0], 3.0, 1e-10));
assert!(approx_eq(eig.eigenvalues[1], 5.0, 1e-10));
}
#[test]
fn test_eigh_3x3() {
let a = vec![2.0, -1.0, 0.0, -1.0, 2.0, -1.0, 0.0, -1.0, 2.0];
let eig = eigh_f64(&a, 3).unwrap();
let expected = [
2.0 - std::f64::consts::SQRT_2,
2.0,
2.0 + std::f64::consts::SQRT_2,
];
for (i, &exp) in expected.iter().enumerate() {
assert!(
approx_eq(eig.eigenvalues[i], exp, 1e-10),
"eigenvalue[{}] = {}, expected {}",
i,
eig.eigenvalues[i],
exp
);
}
assert!(approx_eq(eig.trace(), 6.0, 1e-10));
}
#[test]
fn test_eigh_reconstruction() {
let a = vec![4.0, 2.0, 2.0, 3.0];
let eig = eigh_f64(&a, 2).unwrap();
let recon = eig.reconstruct();
for i in 0..4 {
assert!(
approx_eq(recon[i], a[i], 1e-10),
"recon[{}] = {}, a = {}",
i,
recon[i],
a[i]
);
}
}
#[test]
fn test_eigh_orthogonality() {
let a = vec![4.0, 2.0, 2.0, 3.0];
let eig = eigh_f64(&a, 2).unwrap();
let mut vtv = [0.0; 4];
for i in 0..2 {
for j in 0..2 {
for k in 0..2 {
vtv[i * 2 + j] = eig.eigenvectors[k * 2 + i]
.mul_add(eig.eigenvectors[k * 2 + j], vtv[i * 2 + j]);
}
}
}
assert!(approx_eq(vtv[0], 1.0, 1e-10));
assert!(approx_eq(vtv[1], 0.0, 1e-10));
assert!(approx_eq(vtv[2], 0.0, 1e-10));
assert!(approx_eq(vtv[3], 1.0, 1e-10));
}
#[test]
fn test_eigh_sort_descending() {
let a = vec![1.0, 0.0, 0.0, 5.0];
let mut eig = eigh_f64(&a, 2).unwrap();
assert!(approx_eq(eig.eigenvalues[0], 1.0, 1e-10));
assert!(approx_eq(eig.eigenvalues[1], 5.0, 1e-10));
eig.sort_descending();
assert!(approx_eq(eig.eigenvalues[0], 5.0, 1e-10));
assert!(approx_eq(eig.eigenvalues[1], 1.0, 1e-10));
}
#[test]
fn test_eigh_eigenvector() {
let a = vec![3.0, 1.0, 1.0, 3.0];
let eig = eigh_f64(&a, 2).unwrap();
let v0 = eig.eigenvector(0).unwrap();
let v1 = eig.eigenvector(1).unwrap();
let dot: f64 = v0.iter().zip(v1.iter()).map(|(a, b)| a * b).sum();
assert!(approx_eq(dot, 0.0, 1e-10));
let norm0: f64 = v0.iter().map(|x| x * x).sum::<f64>().sqrt();
let norm1: f64 = v1.iter().map(|x| x * x).sum::<f64>().sqrt();
assert!(approx_eq(norm0, 1.0, 1e-10));
assert!(approx_eq(norm1, 1.0, 1e-10));
}
#[test]
fn test_eigh_1x1() {
let a = vec![7.0];
let eig = eigh_f64(&a, 1).unwrap();
assert_eq!(eig.eigenvalues.len(), 1);
assert!(approx_eq(eig.eigenvalues[0], 7.0, 1e-10));
}
#[test]
fn test_eigh_negative_eigenvalues() {
let a = vec![0.0, 1.0, 1.0, 0.0];
let eig = eigh_f64(&a, 2).unwrap();
assert!(approx_eq(eig.eigenvalues[0], -1.0, 1e-10));
assert!(approx_eq(eig.eigenvalues[1], 1.0, 1e-10));
}
#[test]
fn test_eigh_errors() {
assert!(eigh_f64(&[], 0).is_err());
assert!(eigh_f64(&[1.0, 2.0, 3.0], 2).is_err());
}
}