use crate::errors::linear_error::LinearError;
use crate::traits::matrix_build::MatrixBuild;
use crate::traits::row_ops::RowOps;
use alloc::vec::Vec;
use deep_causality_algebra::{Field, Normed, NormedScalar, Real};
use deep_causality_num::{One, Zero};
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Reduced {
rank: usize,
pivot_columns: Vec<usize>,
}
impl Reduced {
pub fn rank(&self) -> usize {
self.rank
}
pub fn pivot_columns(&self) -> &[usize] {
&self.pivot_columns
}
}
fn reduce<M, P>(m: &mut M, mut choose_pivot: P) -> Result<Reduced, LinearError>
where
M: RowOps,
M::Scalar: Field,
P: FnMut(&M, usize, usize) -> Option<usize>,
{
let (rows, cols) = (m.rows(), m.cols());
let mut pivot_columns = Vec::new();
let mut row = 0usize;
for col in 0..cols {
if row >= rows {
break;
}
let Some(p) = choose_pivot(m, col, row) else {
continue;
};
m.swap_rows(row, p)?;
let head = m.get(row, col)?;
let inv = M::Scalar::one() / head;
m.scale_row(row, &inv, col)?;
for other in 0..rows {
if other == row {
continue;
}
let factor = m.get(other, col)?;
if factor.is_zero() {
continue;
}
let neg = M::Scalar::zero() - factor;
m.axpy_rows(other, row, &neg, col)?;
}
pivot_columns.push(col);
row += 1;
}
Ok(Reduced {
rank: pivot_columns.len(),
pivot_columns,
})
}
fn pivot_exact<M>(m: &M, col: usize, from_row: usize) -> Option<usize>
where
M: RowOps,
M::Scalar: Field,
{
m.pivot_in_column(col, from_row)
}
fn negligible_below<M>(m: &M) -> <M::Scalar as Normed>::Real
where
M: RowOps,
M::Scalar: NormedScalar,
{
let mut scale = <M::Scalar as Normed>::Real::zero();
for r in 0..m.rows() {
for c in 0..m.cols() {
if let Ok(v) = m.get(r, c) {
let mag = v.modulus_squared();
if mag > scale {
scale = mag;
}
}
}
}
let n = m.rows().max(m.cols()).max(1);
let mut n_real = <M::Scalar as Normed>::Real::zero();
for _ in 0..n {
n_real += <M::Scalar as Normed>::Real::one();
}
let eps = <M::Scalar as Normed>::Real::epsilon();
let rel = eps * n_real;
scale * rel * rel
}
fn pivot_stable_with<M>(
m: &M,
col: usize,
from_row: usize,
floor: <M::Scalar as Normed>::Real,
) -> Option<usize>
where
M: RowOps,
M::Scalar: NormedScalar,
{
let mut best: Option<(usize, <M::Scalar as Normed>::Real)> = None;
for r in from_row..m.rows() {
let Ok(v) = m.get(r, col) else { continue };
let mag = v.modulus_squared();
if mag <= floor {
continue;
}
match &best {
Some((_, b)) if *b >= mag => {}
_ => best = Some((r, mag)),
}
}
best.map(|(r, _)| r)
}
pub fn rref<M>(m: &mut M) -> Result<Reduced, LinearError>
where
M: RowOps,
M::Scalar: Field,
{
reduce(m, pivot_exact)
}
pub fn rref_stable<M>(m: &mut M) -> Result<Reduced, LinearError>
where
M: RowOps,
M::Scalar: NormedScalar,
{
let floor = negligible_below(m);
reduce(m, move |mm, col, row| {
pivot_stable_with(mm, col, row, floor)
})
}
pub fn rank<M>(m: &M) -> Result<usize, LinearError>
where
M: RowOps + Clone,
M::Scalar: Field,
{
let mut work = m.clone();
Ok(rref(&mut work)?.rank())
}
pub fn rank_stable<M>(m: &M) -> Result<usize, LinearError>
where
M: RowOps + Clone,
M::Scalar: NormedScalar,
{
let mut work = m.clone();
Ok(rref_stable(&mut work)?.rank())
}
pub fn kernel_basis<M, B>(m: &M) -> Result<B, LinearError>
where
M: RowOps + Clone,
M::Scalar: Field,
B: MatrixBuild<Scalar = M::Scalar>,
{
let cols = m.cols();
let mut work = m.clone();
let reduced = rref(&mut work)?;
let pivots = reduced.pivot_columns().to_vec();
let free: Vec<usize> = (0..cols).filter(|c| !pivots.contains(c)).collect();
let mut basis = B::zeros(cols, free.len());
for (k, &f) in free.iter().enumerate() {
basis.set(f, k, M::Scalar::one())?;
for (row, &p) in pivots.iter().enumerate() {
let coeff = work.get(row, f)?;
if !coeff.is_zero() {
basis.set(p, k, M::Scalar::zero() - coeff)?;
}
}
}
Ok(basis)
}
pub fn image_basis<M, B>(m: &M) -> Result<B, LinearError>
where
M: RowOps + Clone,
M::Scalar: Field,
B: MatrixBuild<Scalar = M::Scalar>,
{
let rows = m.rows();
let mut work = m.clone();
let reduced = rref(&mut work)?;
let pivots = reduced.pivot_columns().to_vec();
let mut basis = B::zeros(rows, pivots.len());
for (k, &p) in pivots.iter().enumerate() {
for i in 0..rows {
basis.set(i, k, m.get(i, p)?)?;
}
}
Ok(basis)
}
pub fn determinant<M>(m: &M) -> Result<M::Scalar, LinearError>
where
M: RowOps + Clone,
M::Scalar: NormedScalar,
{
let (rows, cols) = (m.rows(), m.cols());
if rows != cols {
return Err(LinearError::NotSquare((rows, cols)));
}
if rows == 0 {
return Ok(M::Scalar::one());
}
match rows {
1 => return m.get(0, 0),
2 => {
let (a, b, c, d) = (m.get(0, 0)?, m.get(0, 1)?, m.get(1, 0)?, m.get(1, 1)?);
return Ok(a * d - b * c);
}
3 => {
let g = |i, j| m.get(i, j);
let (a, b, c) = (g(0, 0)?, g(0, 1)?, g(0, 2)?);
let (d, e, f) = (g(1, 0)?, g(1, 1)?, g(1, 2)?);
let (h, i, j) = (g(2, 0)?, g(2, 1)?, g(2, 2)?);
return Ok(a * (e * j - f * i) - b * (d * j - f * h) + c * (d * i - e * h));
}
_ => {}
}
let mut work = m.clone();
let floor = negligible_below(&work);
let mut det = M::Scalar::one();
for col in 0..cols {
let Some(p) = pivot_stable_with(&work, col, col, floor) else {
return Ok(M::Scalar::zero());
};
if p != col {
work.swap_rows(col, p)?;
det = M::Scalar::zero() - det;
}
let head = work.get(col, col)?;
det = det * head;
let inv = M::Scalar::one() / head;
for other in (col + 1)..rows {
let factor = work.get(other, col)?;
if factor.is_zero() {
continue;
}
let neg = M::Scalar::zero() - factor * inv;
work.axpy_rows(other, col, &neg, col)?;
}
}
Ok(det)
}