use crate::error::{BarracudaError, Result};
use crate::linalg::cholesky::{CholeskyDecomposition, cholesky_f64};
use crate::linalg::eigh::eigh_f64;
use std::sync::Arc;
use crate::device::WgpuDevice;
#[derive(Debug, Clone)]
pub struct GenEighDecomposition {
pub eigenvalues: Vec<f64>,
pub eigenvectors: Vec<f64>,
pub n: usize,
}
impl GenEighDecomposition {
#[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 indices: Vec<usize> = (0..n).collect();
indices.sort_by(|&a, &b| {
self.eigenvalues[b]
.partial_cmp(&self.eigenvalues[a])
.unwrap_or(std::cmp::Ordering::Equal)
});
let old_eigenvalues = self.eigenvalues.clone();
let old_eigenvectors = self.eigenvectors.clone();
for (new_idx, &old_idx) in indices.iter().enumerate() {
self.eigenvalues[new_idx] = old_eigenvalues[old_idx];
for row in 0..n {
self.eigenvectors[row * n + new_idx] = old_eigenvectors[row * n + old_idx];
}
}
}
#[must_use]
pub fn verify(&self, a: &[f64], b: &[f64]) -> f64 {
let n = self.n;
let mut max_residual: f64 = 0.0;
for i in 0..n {
let lambda = self.eigenvalues[i];
let x: Vec<f64> = (0..n).map(|row| self.eigenvectors[row * n + i]).collect();
let mut ax = vec![0.0; n];
for row in 0..n {
for col in 0..n {
ax[row] = a[row * n + col].mul_add(x[col], ax[row]);
}
}
let mut lbx = vec![0.0; n];
for row in 0..n {
for col in 0..n {
lbx[row] = (lambda * b[row * n + col]).mul_add(x[col], lbx[row]);
}
}
let residual_norm: f64 = ax
.iter()
.zip(lbx.iter())
.map(|(a, b)| (a - b).powi(2))
.sum::<f64>()
.sqrt();
let x_norm: f64 = x.iter().map(|v| v.powi(2)).sum::<f64>().sqrt();
let relative_residual = residual_norm / x_norm.max(1e-15);
max_residual = max_residual.max(relative_residual);
}
max_residual
}
#[must_use]
pub fn trace(&self) -> f64 {
self.eigenvalues.iter().sum()
}
}
pub fn gen_eigh_f64(
device: Arc<WgpuDevice>,
a: &[f64],
b: &[f64],
n: usize,
) -> Result<GenEighDecomposition> {
if a.len() != n * n {
return Err(BarracudaError::InvalidInput {
message: format!(
"Matrix A has wrong size: expected {}, got {}",
n * n,
a.len()
),
});
}
if b.len() != n * n {
return Err(BarracudaError::InvalidInput {
message: format!(
"Matrix B has wrong size: expected {}, got {}",
n * n,
b.len()
),
});
}
let chol = cholesky_f64(device, b, n)?;
let l_inv_a = solve_lower_triangular_matrix(&chol, a, n)?;
let c = compute_symmetric_transform(&chol, &l_inv_a, n)?;
let std_eigh = eigh_f64(&c, n)?;
let eigenvectors = back_transform_eigenvectors(&chol, &std_eigh.eigenvectors, n)?;
Ok(GenEighDecomposition {
eigenvalues: std_eigh.eigenvalues,
eigenvectors,
n,
})
}
fn solve_lower_triangular_matrix(
chol: &CholeskyDecomposition,
a: &[f64],
n: usize,
) -> Result<Vec<f64>> {
let l = &chol.l;
let mut result = vec![0.0; n * n];
for col in 0..n {
let mut y = vec![0.0; n];
for row in 0..n {
y[row] = a[row * n + col];
}
for i in 0..n {
let mut sum = y[i];
for j in 0..i {
sum = l[i * n + j].mul_add(-y[j], sum);
}
y[i] = sum / l[i * n + i];
}
for row in 0..n {
result[row * n + col] = y[row];
}
}
Ok(result)
}
fn compute_symmetric_transform(
chol: &CholeskyDecomposition,
l_inv_a: &[f64],
n: usize,
) -> Result<Vec<f64>> {
let l = &chol.l;
let mut c = vec![0.0; n * n];
let mut l_inv = vec![0.0; n * n];
for i in 0..n {
let mut x = vec![0.0; n];
x[i] = 1.0;
for row in 0..n {
let mut sum = if row == i { 1.0 } else { 0.0 };
for k in 0..row {
sum = l[row * n + k].mul_add(-x[k], sum);
}
x[row] = sum / l[row * n + row];
}
for row in 0..n {
l_inv[row * n + i] = x[row];
}
}
for i in 0..n {
for j in 0..n {
let mut sum = 0.0;
for k in 0..n {
sum = l_inv_a[i * n + k].mul_add(l_inv[j * n + k], sum);
}
c[i * n + j] = sum;
}
}
for i in 0..n {
for j in i + 1..n {
let avg = 0.5 * (c[i * n + j] + c[j * n + i]);
c[i * n + j] = avg;
c[j * n + i] = avg;
}
}
Ok(c)
}
fn back_transform_eigenvectors(
chol: &CholeskyDecomposition,
y: &[f64],
n: usize,
) -> Result<Vec<f64>> {
let l = &chol.l;
let mut x = vec![0.0; n * n];
for j in 0..n {
let mut xi = vec![0.0; n];
for i in 0..n {
xi[i] = y[i * n + j];
}
for i in (0..n).rev() {
let mut sum = xi[i];
for k in i + 1..n {
sum = l[k * n + i].mul_add(-xi[k], sum);
}
xi[i] = sum / l[i * n + i];
}
for i in 0..n {
x[i * n + j] = xi[i];
}
}
Ok(x)
}
pub fn gen_eigh_identity_b(a: &[f64], n: usize) -> Result<GenEighDecomposition> {
let eigh = eigh_f64(a, n)?;
Ok(GenEighDecomposition {
eigenvalues: eigh.eigenvalues,
eigenvectors: eigh.eigenvectors,
n,
})
}
#[cfg(test)]
mod tests {
use super::*;
use crate::device::test_pool::get_test_device_if_f64_gpu_available_sync;
#[test]
fn test_gen_eigh_identity_b() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![4.0, 1.0, 1.0, 3.0];
let b = vec![1.0, 0.0, 0.0, 1.0];
let result = gen_eigh_f64(device, &a, &b, 2).unwrap();
let expected_min = (7.0 - 5.0_f64.sqrt()) / 2.0;
let expected_max = f64::midpoint(7.0, 5.0_f64.sqrt());
assert!(
(result.eigenvalues[0] - expected_min).abs() < 1e-10,
"Expected λ₀ ≈ {}, got {}",
expected_min,
result.eigenvalues[0]
);
assert!(
(result.eigenvalues[1] - expected_max).abs() < 1e-10,
"Expected λ₁ ≈ {}, got {}",
expected_max,
result.eigenvalues[1]
);
}
#[test]
fn test_gen_eigh_scaled_b() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![4.0, 0.0, 0.0, 6.0];
let b = vec![2.0, 0.0, 0.0, 2.0];
let result = gen_eigh_f64(device, &a, &b, 2).unwrap();
assert!(
(result.eigenvalues[0] - 2.0).abs() < 1e-10,
"Expected λ₀ = 2, got {}",
result.eigenvalues[0]
);
assert!(
(result.eigenvalues[1] - 3.0).abs() < 1e-10,
"Expected λ₁ = 3, got {}",
result.eigenvalues[1]
);
}
#[test]
fn test_gen_eigh_verify() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![5.0, 2.0, 2.0, 3.0];
let b = vec![2.0, 1.0, 1.0, 2.0];
let result = gen_eigh_f64(device, &a, &b, 2).unwrap();
let residual = result.verify(&a, &b);
assert!(residual < 1e-10, "Residual too large: {residual}");
}
#[test]
fn test_gen_eigh_3x3() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
#[rustfmt::skip]
let a = vec![
6.0, 2.0, 1.0,
2.0, 5.0, 2.0,
1.0, 2.0, 4.0,
];
#[rustfmt::skip]
let b = vec![
2.0, 0.5, 0.0,
0.5, 2.0, 0.5,
0.0, 0.5, 2.0,
];
let result = gen_eigh_f64(device, &a, &b, 3).unwrap();
let residual = result.verify(&a, &b);
assert!(residual < 1e-9, "Residual too large: {residual}");
}
#[test]
fn test_gen_eigh_eigenvector_access() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![2.0, 1.0, 1.0, 2.0];
let b = vec![1.0, 0.0, 0.0, 1.0];
let result = gen_eigh_f64(device, &a, &b, 2).unwrap();
let v0 = result.eigenvector(0).unwrap();
let v1 = result.eigenvector(1).unwrap();
assert_eq!(v0.len(), 2);
assert_eq!(v1.len(), 2);
assert!(result.eigenvector(2).is_none());
}
#[test]
fn test_gen_eigh_sort_descending() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![1.0, 0.0, 0.0, 3.0];
let b = vec![1.0, 0.0, 0.0, 1.0];
let mut result = gen_eigh_f64(device, &a, &b, 2).unwrap();
assert!(result.eigenvalues[0] < result.eigenvalues[1]);
result.sort_descending();
assert!(result.eigenvalues[0] > result.eigenvalues[1]);
assert!((result.eigenvalues[0] - 3.0).abs() < 1e-10);
assert!((result.eigenvalues[1] - 1.0).abs() < 1e-10);
}
#[test]
fn test_gen_eigh_non_spd_b_error() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![1.0, 0.0, 0.0, 1.0];
let b = vec![1.0, 2.0, 2.0, 1.0];
let result = gen_eigh_f64(device, &a, &b, 2);
assert!(result.is_err());
}
#[test]
fn test_gen_eigh_dimension_mismatch() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![1.0, 0.0, 0.0, 1.0];
let b = vec![1.0, 0.0, 0.0];
let result = gen_eigh_f64(device, &a, &b, 2);
assert!(result.is_err());
}
#[test]
fn test_gen_eigh_trace() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let a = vec![3.0, 1.0, 1.0, 3.0];
let b = vec![1.0, 0.0, 0.0, 1.0];
let result = gen_eigh_f64(device, &a, &b, 2).unwrap();
let trace = result.trace();
assert!((trace - 6.0).abs() < 1e-10, "Expected trace 6, got {trace}");
}
#[test]
fn test_gen_eigh_larger_matrix() {
let Some(device) = get_test_device_if_f64_gpu_available_sync() else {
return;
};
let n = 5;
let mut a = vec![0.0; n * n];
let mut b = vec![0.0; n * n];
for i in 0..n {
for j in 0..n {
a[i * n + j] = if i == j { 5.0 } else { 0.5 };
b[i * n + j] = if i == j { 2.0 } else { 0.1 };
}
}
let result = gen_eigh_f64(device, &a, &b, n).unwrap();
let residual = result.verify(&a, &b);
assert!(residual < 1e-8, "Residual too large for 5×5: {residual}");
}
}