use crate::device::WgpuDevice;
use crate::error::{BarracudaError, Result};
use std::sync::Arc;
#[derive(Debug, Clone)]
pub struct CholeskyDecomposition {
pub l: Vec<f64>,
pub n: usize,
}
impl CholeskyDecomposition {
pub fn solve(&self, b: &[f64]) -> Result<Vec<f64>> {
if b.len() != self.n {
return Err(BarracudaError::InvalidInput {
message: format!("b has length {}, expected {}", b.len(), self.n),
});
}
let mut y = vec![0.0; self.n];
for i in 0..self.n {
let mut sum = b[i];
for (j, &y_j) in y.iter().enumerate().take(i) {
sum = self.l[i * self.n + j].mul_add(-y_j, sum);
}
let diag = self.l[i * self.n + i];
if diag.abs() < 1e-14 {
return Err(BarracudaError::Numerical {
message: "Matrix is singular or not positive definite".to_string(),
});
}
y[i] = sum / diag;
}
let mut x = vec![0.0; self.n];
for i in (0..self.n).rev() {
let mut sum = y[i];
for (j, &x_j) in x.iter().enumerate().skip(i + 1) {
sum = self.l[j * self.n + i].mul_add(-x_j, sum);
}
x[i] = sum / self.l[i * self.n + i];
}
Ok(x)
}
#[must_use]
pub fn det(&self) -> f64 {
let mut det_l = 1.0;
for i in 0..self.n {
det_l *= self.l[i * self.n + i];
}
det_l * det_l
}
#[must_use]
pub fn log_det(&self) -> f64 {
let mut log_det = 0.0;
for i in 0..self.n {
log_det += self.l[i * self.n + i].ln();
}
2.0 * log_det
}
pub fn inverse(&self) -> Result<Vec<f64>> {
let mut inv = vec![0.0; self.n * self.n];
for j in 0..self.n {
let mut e = vec![0.0; self.n];
e[j] = 1.0;
let col = self.solve(&e)?;
for i in 0..self.n {
inv[i * self.n + j] = col[i];
}
}
Ok(inv)
}
}
pub fn cholesky_f64(device: Arc<WgpuDevice>, a: &[f64], n: usize) -> Result<CholeskyDecomposition> {
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 l = crate::ops::linalg::cholesky::CholeskyF64::execute(device, a, n)?;
for i in 0..n {
let diag = l[i * n + i];
if diag.is_nan() || diag <= 0.0 {
return Err(BarracudaError::InvalidInput {
message: format!("Matrix is not positive definite (L[{i},{i}] = {diag})"),
});
}
}
Ok(CholeskyDecomposition { l, n })
}
#[cfg(any(test, feature = "benchmarks"))]
pub fn cholesky_f64_cpu(a: &[f64], n: usize) -> Result<CholeskyDecomposition> {
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 mut l = vec![0.0_f64; n * n];
for i in 0..n {
for j in 0..=i {
let mut sum = a[i * n + j];
for k in 0..j {
sum = l[i * n + k].mul_add(-l[j * n + k], sum);
}
if i == j {
if sum <= 0.0 {
return Err(BarracudaError::Numerical {
message: format!(
"Matrix is not positive definite: L[{i},{i}]² = {sum} ≤ 0"
),
});
}
l[i * n + j] = sum.sqrt();
} else {
l[i * n + j] = sum / l[j * n + j];
}
}
}
Ok(CholeskyDecomposition { l, n })
}
#[cfg(test)]
mod tests {
use super::*;
fn approx_eq(a: f64, b: f64, tol: f64) -> bool {
(a - b).abs() < tol
}
#[test]
fn test_cholesky_2x2() {
let a = vec![4.0, 2.0, 2.0, 3.0];
let chol = cholesky_f64_cpu(&a, 2).unwrap();
assert!(approx_eq(chol.l[0], 2.0, 1e-10)); assert!(approx_eq(chol.l[1], 0.0, 1e-10)); assert!(approx_eq(chol.l[2], 1.0, 1e-10)); assert!(approx_eq(chol.l[3], std::f64::consts::SQRT_2, 1e-10)); }
#[test]
fn test_cholesky_solve() {
let a = vec![4.0, 2.0, 2.0, 3.0];
let b = vec![10.0, 8.0];
let chol = cholesky_f64_cpu(&a, 2).unwrap();
let x = chol.solve(&b).unwrap();
let ax0 = 4.0f64.mul_add(x[0], 2.0 * x[1]);
let ax1 = 2.0f64.mul_add(x[0], 3.0 * x[1]);
assert!(approx_eq(ax0, b[0], 1e-10));
assert!(approx_eq(ax1, b[1], 1e-10));
}
#[test]
fn test_cholesky_det() {
let a = vec![4.0, 2.0, 2.0, 3.0];
let chol = cholesky_f64_cpu(&a, 2).unwrap();
assert!(approx_eq(chol.det(), 8.0, 1e-10));
}
#[test]
fn test_cholesky_identity() {
let a = vec![1.0, 0.0, 0.0, 1.0];
let chol = cholesky_f64_cpu(&a, 2).unwrap();
assert!(approx_eq(chol.l[0], 1.0, 1e-10));
assert!(approx_eq(chol.l[1], 0.0, 1e-10));
assert!(approx_eq(chol.l[2], 0.0, 1e-10));
assert!(approx_eq(chol.l[3], 1.0, 1e-10));
}
#[test]
fn test_cholesky_3x3() {
let a = vec![4.0, 2.0, 1.0, 2.0, 3.0, 1.0, 1.0, 1.0, 3.0];
let chol = cholesky_f64_cpu(&a, 3).unwrap();
let mut llt = [0.0; 9];
for i in 0..3 {
for j in 0..3 {
for k in 0..3 {
llt[i * 3 + j] = chol.l[i * 3 + k].mul_add(chol.l[j * 3 + k], llt[i * 3 + j]);
}
}
}
for i in 0..9 {
assert!(
approx_eq(llt[i], a[i], 1e-10),
"L·Lᵀ[{}] = {}, A = {}",
i,
llt[i],
a[i]
);
}
}
#[test]
fn test_cholesky_inverse() {
let a = vec![4.0, 2.0, 2.0, 3.0];
let chol = cholesky_f64_cpu(&a, 2).unwrap();
let inv = chol.inverse().unwrap();
let mut aa_inv = [0.0; 4];
for i in 0..2 {
for j in 0..2 {
for k in 0..2 {
aa_inv[i * 2 + j] = a[i * 2 + k].mul_add(inv[k * 2 + j], aa_inv[i * 2 + j]);
}
}
}
assert!(approx_eq(aa_inv[0], 1.0, 1e-10));
assert!(approx_eq(aa_inv[1], 0.0, 1e-10));
assert!(approx_eq(aa_inv[2], 0.0, 1e-10));
assert!(approx_eq(aa_inv[3], 1.0, 1e-10));
}
#[test]
fn test_cholesky_not_positive_definite() {
let a = vec![1.0, 2.0, 2.0, 1.0];
assert!(cholesky_f64_cpu(&a, 2).is_err());
}
#[test]
fn test_cholesky_log_det() {
let a = vec![4.0, 2.0, 2.0, 3.0];
let chol = cholesky_f64_cpu(&a, 2).unwrap();
let expected = 8.0_f64.ln();
assert!(approx_eq(chol.log_det(), expected, 1e-10));
}
#[test]
fn test_cholesky_errors() {
assert!(cholesky_f64_cpu(&[], 0).is_err());
assert!(cholesky_f64_cpu(&[1.0, 2.0, 3.0], 2).is_err());
}
}