use crate::error::{BarracudaError, Result};
#[derive(Debug, Clone)]
pub struct SvdDecomposition {
pub u: Vec<f64>,
pub s: Vec<f64>,
pub vt: Vec<f64>,
pub m: usize,
pub n: usize,
}
impl SvdDecomposition {
#[must_use]
pub fn pseudoinverse(&self, tol: f64) -> Vec<f64> {
let k = self.s.len();
let s_inv: Vec<f64> = self
.s
.iter()
.map(|&s| if s > tol { 1.0 / s } else { 0.0 })
.collect();
let mut pinv = vec![0.0; self.n * self.m];
for i in 0..self.n {
for j in 0..self.m {
let sum: f64 = self
.vt
.iter()
.skip(i)
.step_by(self.n)
.take(k)
.zip(&s_inv)
.zip(&self.u[j * self.m..j * self.m + k])
.map(|((&vt_li, &s_l), &u_jl)| vt_li * s_l * u_jl)
.sum();
pinv[i * self.m + j] = sum;
}
}
pinv
}
pub fn solve(&self, b: &[f64], tol: f64) -> Result<Vec<f64>> {
if b.len() != self.m {
return Err(BarracudaError::InvalidInput {
message: format!("b has length {}, expected {}", b.len(), self.m),
});
}
let pinv = self.pseudoinverse(tol);
let mut x = vec![0.0; self.n];
for i in 0..self.n {
for j in 0..self.m {
x[i] = pinv[i * self.m + j].mul_add(b[j], x[i]);
}
}
Ok(x)
}
#[must_use]
pub fn rank(&self, tol: f64) -> usize {
self.s.iter().filter(|&&s| s > tol).count()
}
#[must_use]
pub fn condition_number(&self) -> f64 {
if self.s.is_empty() {
return f64::INFINITY;
}
let s_max = self.s[0];
let Some(&s_min) = self.s.last() else {
return f64::INFINITY;
};
if s_min < 1e-14 {
f64::INFINITY
} else {
s_max / s_min
}
}
#[must_use]
pub fn low_rank_approx(&self, k: usize) -> Vec<f64> {
let k = k.min(self.s.len());
let mut approx = vec![0.0; self.m * self.n];
for r in 0..k {
let sigma = self.s[r];
for i in 0..self.m {
for j in 0..self.n {
approx[i * self.n + j] = (sigma * self.u[i * self.m + r])
.mul_add(self.vt[r * self.n + j], approx[i * self.n + j]);
}
}
}
approx
}
}
pub fn svd_decompose(a: &[f64], m: usize, n: usize) -> Result<SvdDecomposition> {
if a.len() != m * n {
return Err(BarracudaError::InvalidInput {
message: format!("Matrix has {} elements, expected {}×{}", a.len(), m, n),
});
}
if m == 0 || n == 0 {
return Err(BarracudaError::InvalidInput {
message: "Matrix dimensions must be positive".to_string(),
});
}
let mut ata = vec![0.0; n * n];
for i in 0..n {
for j in 0..n {
let mut sum = 0.0;
for k in 0..m {
sum = a[k * n + i].mul_add(a[k * n + j], sum);
}
ata[i * n + j] = sum;
}
}
let (eigenvalues, eigenvectors) = jacobi_eigen(&ata, n, 100)?;
let mut indexed: Vec<(usize, f64)> = eigenvalues
.iter()
.enumerate()
.map(|(i, &e)| (i, e.max(0.0).sqrt()))
.collect();
indexed.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
let k = n.min(m); let s: Vec<f64> = indexed.iter().take(k).map(|(_, v)| *v).collect();
let mut vt = vec![0.0; n * n];
for i in 0..n {
let orig_idx = indexed[i].0;
for j in 0..n {
vt[i * n + j] = eigenvectors[j * n + orig_idx];
}
}
let mut u = vec![0.0; m * m];
let mut av = vec![0.0; m * n];
for i in 0..m {
for j in 0..n {
let mut sum = 0.0;
for l in 0..n {
sum = a[i * n + l].mul_add(vt[j * n + l], sum);
}
av[i * n + j] = sum;
}
}
for j in 0..k {
if s[j] > 1e-14 {
for i in 0..m {
u[i * m + j] = av[i * n + j] / s[j];
}
}
}
for j in k..m {
let mut col = vec![0.0; m];
col[j % m] = 1.0;
for prev in 0..j {
let mut dot = 0.0;
for i in 0..m {
dot = u[i * m + prev].mul_add(col[i], dot);
}
for i in 0..m {
col[i] -= dot * u[i * m + prev];
}
}
let mut norm = 0.0;
for &c in &col {
norm = c.mul_add(c, norm);
}
norm = norm.sqrt();
if norm > 1e-14 {
for i in 0..m {
u[i * m + j] = col[i] / norm;
}
}
}
Ok(SvdDecomposition { u, s, vt, m, n })
}
fn jacobi_eigen(a: &[f64], n: usize, max_iter: usize) -> Result<(Vec<f64>, Vec<f64>)> {
let mut a = a.to_vec();
let mut v = vec![0.0; n * n];
for i in 0..n {
v[i * n + i] = 1.0;
}
for _ in 0..max_iter {
let mut max_val = 0.0;
let mut p = 0;
let mut q = 0;
for i in 0..n {
for j in (i + 1)..n {
let val = a[i * n + j].abs();
if val > max_val {
max_val = val;
p = i;
q = j;
}
}
}
if max_val < 1e-14 {
break;
}
let app = a[p * n + p];
let aqq = a[q * n + q];
let apq = a[p * n + q];
let theta = if (aqq - app).abs() < 1e-14 {
std::f64::consts::FRAC_PI_4 * apq.signum()
} else {
0.5 * (2.0 * apq / (aqq - app)).atan()
};
let c = theta.cos();
let s = theta.sin();
for i in 0..n {
if i != p && i != q {
let aip = a[i * n + p];
let aiq = a[i * n + q];
a[i * n + p] = c * aip - s * aiq;
a[p * n + i] = a[i * n + p];
a[i * n + q] = s * aip + c * aiq;
a[q * n + i] = a[i * n + q];
}
}
a[p * n + p] = (s * s).mul_add(aqq, (c * c).mul_add(app, -(2.0 * c * s * apq)));
a[q * n + q] = (c * c).mul_add(aqq, (s * s).mul_add(app, 2.0 * c * s * apq));
a[p * n + q] = 0.0;
a[q * n + p] = 0.0;
for i in 0..n {
let vip = v[i * n + p];
let viq = v[i * n + q];
v[i * n + p] = c * vip - s * viq;
v[i * n + q] = s * vip + c * viq;
}
}
let eigenvalues: Vec<f64> = (0..n).map(|i| a[i * n + i]).collect();
Ok((eigenvalues, v))
}
pub fn svd_values(a: &[f64], m: usize, n: usize) -> Result<Vec<f64>> {
let svd = svd_decompose(a, m, n)?;
Ok(svd.s)
}
pub fn svd_pinv(a: &[f64], m: usize, n: usize, tol: f64) -> Result<Vec<f64>> {
let svd = svd_decompose(a, m, n)?;
Ok(svd.pseudoinverse(tol))
}
#[cfg(test)]
mod tests {
use super::*;
fn approx_eq(a: f64, b: f64, tol: f64) -> bool {
(a - b).abs() < tol
}
#[test]
fn test_svd_2x2() {
let a = vec![3.0, 2.0, 2.0, 3.0];
let svd = svd_decompose(&a, 2, 2).unwrap();
assert!(approx_eq(svd.s[0], 5.0, 1e-10), "s[0] = {}", svd.s[0]);
assert!(approx_eq(svd.s[1], 1.0, 1e-10), "s[1] = {}", svd.s[1]);
for i in 0..2 {
for j in 0..2 {
let mut val = 0.0;
for k in 0..2 {
val = (svd.u[i * 2 + k] * svd.s[k]).mul_add(svd.vt[k * 2 + j], val);
}
assert!(
approx_eq(val, a[i * 2 + j], 1e-10),
"UΣV^T[{},{}] = {}, A = {}",
i,
j,
val,
a[i * 2 + j]
);
}
}
}
#[test]
fn test_svd_rank_deficient() {
let a = vec![1.0, 2.0, 2.0, 4.0];
let svd = svd_decompose(&a, 2, 2).unwrap();
assert!(svd.s[1] < 1e-7, "s[1] = {}", svd.s[1]);
assert_eq!(svd.rank(1e-7), 1);
}
#[test]
fn test_svd_3x2() {
let a = vec![1.0, 0.0, 0.0, 1.0, 1.0, 1.0];
let svd = svd_decompose(&a, 3, 2).unwrap();
assert_eq!(svd.s.len(), 2);
assert!(svd.s[0] > 0.0);
assert!(svd.s[1] > 0.0);
let approx = svd.low_rank_approx(2);
for i in 0..6 {
assert!(
approx_eq(approx[i], a[i], 1e-10),
"approx[{}] = {}, a = {}",
i,
approx[i],
a[i]
);
}
}
#[test]
fn test_svd_pseudoinverse() {
let a = vec![1.0, 2.0, 3.0, 4.0];
let svd = svd_decompose(&a, 2, 2).unwrap();
let pinv = svd.pseudoinverse(1e-10);
let mut aa_pinv = [0.0; 4];
for i in 0..2 {
for j in 0..2 {
for k in 0..2 {
aa_pinv[i * 2 + j] = a[i * 2 + k].mul_add(pinv[k * 2 + j], aa_pinv[i * 2 + j]);
}
}
}
let mut result = [0.0; 4];
for i in 0..2 {
for j in 0..2 {
for k in 0..2 {
result[i * 2 + j] = aa_pinv[i * 2 + k].mul_add(a[k * 2 + j], result[i * 2 + j]);
}
}
}
for i in 0..4 {
assert!(
approx_eq(result[i], a[i], 1e-10),
"A*A⁺*A[{}] = {}, A = {}",
i,
result[i],
a[i]
);
}
}
#[test]
fn test_svd_condition_number() {
let a = vec![1.0, 0.0, 0.0, 1.0];
let svd = svd_decompose(&a, 2, 2).unwrap();
assert!(approx_eq(svd.condition_number(), 1.0, 1e-10));
let b = vec![1.0, 0.0, 0.0, 1e-10];
let svd_b = svd_decompose(&b, 2, 2).unwrap();
assert!(svd_b.condition_number() > 1e9);
}
#[test]
fn test_svd_low_rank_approx() {
let a = vec![1.0, 2.0, 3.0, 2.0, 4.0, 6.0, 3.0, 6.0, 9.0];
let svd = svd_decompose(&a, 3, 3).unwrap();
let approx1 = svd.low_rank_approx(1);
for i in 0..9 {
assert!(
approx_eq(approx1[i], a[i], 1e-10),
"approx1[{}] = {}, a = {}",
i,
approx1[i],
a[i]
);
}
}
#[test]
fn test_svd_solve() {
let a = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
let b = vec![1.0, 2.0, 3.0];
let svd = svd_decompose(&a, 3, 2).unwrap();
let x = svd.solve(&b, 1e-10).unwrap();
let mut ax = [0.0; 3];
for i in 0..3 {
for j in 0..2 {
ax[i] = a[i * 2 + j].mul_add(x[j], ax[i]);
}
}
let r: Vec<f64> = (0..3).map(|i| b[i] - ax[i]).collect();
let mut atr = [0.0; 2];
for j in 0..2 {
for i in 0..3 {
atr[j] = a[i * 2 + j].mul_add(r[i], atr[j]);
}
}
for (j, &val) in atr.iter().enumerate() {
assert!(val.abs() < 1e-10, "A^T r[{j}] = {val}");
}
}
#[test]
fn test_svd_errors() {
assert!(svd_decompose(&[], 0, 0).is_err());
assert!(svd_decompose(&[1.0, 2.0, 3.0], 2, 2).is_err());
}
}