use crate::error::{BarracudaError, Result};
#[derive(Debug, Clone)]
pub struct LuDecomposition {
pub lu: Vec<f64>,
pub perm: Vec<usize>,
pub n: usize,
pub num_swaps: usize,
}
impl LuDecomposition {
#[must_use]
pub fn l(&self) -> Vec<f64> {
let mut l = vec![0.0; self.n * self.n];
for i in 0..self.n {
l[i * self.n + i] = 1.0; for j in 0..i {
l[i * self.n + j] = self.lu[i * self.n + j];
}
}
l
}
#[must_use]
pub fn u(&self) -> Vec<f64> {
let mut u = vec![0.0; self.n * self.n];
for i in 0..self.n {
for j in i..self.n {
u[i * self.n + j] = self.lu[i * self.n + j];
}
}
u
}
#[must_use]
pub fn p(&self) -> Vec<f64> {
let mut p = vec![0.0; self.n * self.n];
for i in 0..self.n {
p[i * self.n + self.perm[i]] = 1.0;
}
p
}
#[expect(
clippy::manual_is_multiple_of,
reason = "is_multiple_of is nightly-only"
)]
#[must_use]
pub fn det(&self) -> f64 {
let mut det = if self.num_swaps % 2 == 0 { 1.0 } else { -1.0 };
for i in 0..self.n {
det *= self.lu[i * self.n + i];
}
det
}
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 {
y[i] = b[self.perm[i]];
}
for i in 1..self.n {
for j in 0..i {
y[i] = self.lu[i * self.n + j].mul_add(-y[j], y[i]);
}
}
let mut x = y;
for i in (0..self.n).rev() {
for j in (i + 1)..self.n {
x[i] = self.lu[i * self.n + j].mul_add(-x[j], x[i]);
}
if self.lu[i * self.n + i].abs() < 1e-14 {
return Err(BarracudaError::Numerical {
message: "Matrix is singular".to_string(),
});
}
x[i] /= self.lu[i * self.n + i];
}
Ok(x)
}
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 lu_decompose(a: &[f64], n: usize) -> Result<LuDecomposition> {
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 lu = a.to_vec();
let mut perm: Vec<usize> = (0..n).collect();
let mut num_swaps = 0;
for k in 0..n {
let mut max_val = lu[k * n + k].abs();
let mut max_row = k;
for i in (k + 1)..n {
let val = lu[i * n + k].abs();
if val > max_val {
max_val = val;
max_row = i;
}
}
if max_row != k {
for j in 0..n {
lu.swap(k * n + j, max_row * n + j);
}
perm.swap(k, max_row);
num_swaps += 1;
}
let pivot = lu[k * n + k];
if pivot.abs() < 1e-14 {
}
for i in (k + 1)..n {
if pivot.abs() > 1e-14 {
lu[i * n + k] /= pivot;
}
for j in (k + 1)..n {
lu[i * n + j] = lu[i * n + k].mul_add(-lu[k * n + j], lu[i * n + j]);
}
}
}
Ok(LuDecomposition {
lu,
perm,
n,
num_swaps,
})
}
pub fn lu_solve(a: &[f64], n: usize, b: &[f64]) -> Result<Vec<f64>> {
let lu = lu_decompose(a, n)?;
lu.solve(b)
}
pub fn lu_det(a: &[f64], n: usize) -> Result<f64> {
let lu = lu_decompose(a, n)?;
Ok(lu.det())
}
pub fn lu_inverse(a: &[f64], n: usize) -> Result<Vec<f64>> {
let lu = lu_decompose(a, n)?;
lu.inverse()
}
#[cfg(test)]
mod tests {
use super::*;
fn approx_eq(a: f64, b: f64, tol: f64) -> bool {
(a - b).abs() < tol
}
#[test]
fn test_lu_2x2() {
let a = vec![4.0, 3.0, 6.0, 3.0];
let lu = lu_decompose(&a, 2).unwrap();
assert!(approx_eq(lu.det(), -6.0, 1e-10));
}
#[test]
fn test_lu_solve_2x2() {
let a = vec![4.0, 3.0, 6.0, 3.0];
let b = vec![10.0, 12.0];
let x = lu_solve(&a, 2, &b).unwrap();
let ax0 = 4.0f64.mul_add(x[0], 3.0 * x[1]);
let ax1 = 6.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_lu_solve_3x3() {
let a = vec![2.0, -1.0, 0.0, -1.0, 2.0, -1.0, 0.0, -1.0, 2.0];
let b = vec![1.0, 0.0, 1.0];
let x = lu_solve(&a, 3, &b).unwrap();
let ax0 = 2.0f64.mul_add(x[0], -x[1]);
let ax1 = 2.0f64.mul_add(x[1], -x[0]) - x[2];
let ax2 = 2.0f64.mul_add(x[2], -x[1]);
assert!(approx_eq(ax0, b[0], 1e-10));
assert!(approx_eq(ax1, b[1], 1e-10));
assert!(approx_eq(ax2, b[2], 1e-10));
}
#[test]
fn test_lu_det_3x3() {
let a = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 10.0];
let det = lu_det(&a, 3).unwrap();
assert!(approx_eq(det, -3.0, 1e-10));
}
#[test]
fn test_lu_inverse_2x2() {
let a = vec![4.0, 7.0, 2.0, 6.0];
let inv = lu_inverse(&a, 2).unwrap();
let i00 = a[0].mul_add(inv[0], a[1] * inv[2]);
let i01 = a[0].mul_add(inv[1], a[1] * inv[3]);
let i10 = a[2].mul_add(inv[0], a[3] * inv[2]);
let i11 = a[2].mul_add(inv[1], a[3] * inv[3]);
assert!(approx_eq(i00, 1.0, 1e-10));
assert!(approx_eq(i01, 0.0, 1e-10));
assert!(approx_eq(i10, 0.0, 1e-10));
assert!(approx_eq(i11, 1.0, 1e-10));
}
#[test]
fn test_lu_identity() {
let a = vec![1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0];
let lu = lu_decompose(&a, 3).unwrap();
assert!(approx_eq(lu.det(), 1.0, 1e-10));
let l = lu.l();
let u = lu.u();
for i in 0..3 {
for j in 0..3 {
let expected = if i == j { 1.0 } else { 0.0 };
assert!(approx_eq(l[i * 3 + j], expected, 1e-10));
}
}
for i in 0..3 {
for j in 0..3 {
let expected = if i == j { 1.0 } else { 0.0 };
assert!(approx_eq(u[i * 3 + j], expected, 1e-10));
}
}
}
#[test]
fn test_lu_needs_pivoting() {
let a = vec![0.0, 1.0, 1.0, 1.0];
let lu = lu_decompose(&a, 2).unwrap();
assert!(approx_eq(lu.det(), -1.0, 1e-10));
let x = lu.solve(&[3.0, 4.0]).unwrap();
let ax0 = 0.0f64.mul_add(x[0], 1.0 * x[1]);
let ax1 = 1.0f64.mul_add(x[0], 1.0 * x[1]);
assert!(approx_eq(ax0, 3.0, 1e-10));
assert!(approx_eq(ax1, 4.0, 1e-10));
}
#[test]
fn test_lu_empty_error() {
assert!(lu_decompose(&[], 0).is_err());
}
#[test]
fn test_lu_size_mismatch_error() {
assert!(lu_decompose(&[1.0, 2.0, 3.0], 2).is_err());
}
}