use crate::application::matrix::matmul_accumulate;
use crate::domain::real::RealScalar;
use crate::infrastructure::cache::{
cached_cache_geometry, working_set_spills_llc_for_geometry, CacheGeometry,
};
use leto::{
Array1, Array2, ArrayView1, ArrayView2, ArrayViewMut1, ArrayViewMut2, Layout, LetoError,
Result, Storage,
};
const LU_PANEL_WIDTH: usize = 64;
pub(crate) fn lu_uses_blocked_path(
geometry: CacheGeometry,
n: usize,
element_bytes: usize,
) -> bool {
let working_set = n.saturating_mul(n).saturating_mul(element_bytes);
working_set_spills_llc_for_geometry(geometry, working_set)
}
#[derive(Debug, Clone)]
pub struct LuDecomposition<T> {
factors: Array2<T>,
pivots: Vec<usize>,
sign: i8,
}
pub fn lu_decompose<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<LuDecomposition<T>> {
let [rows, cols] = matrix.shape();
if rows != cols {
return Err(LetoError::ShapeMismatch {
lhs: vec![rows, cols],
rhs: vec![rows, rows],
});
}
let n = rows;
let mut a = matrix.to_contiguous().into_storage().into_inner();
if !a.iter().all(|value| value.is_finite()) {
return Err(LetoError::StorageError {
reason: "LU input contains a non-finite value".to_string(),
});
}
let mut pivots: Vec<usize> = (0..n).collect();
let mut sign = 1i8;
if lu_uses_blocked_path(cached_cache_geometry(), n, core::mem::size_of::<T>()) {
lu_eliminate_blocked(&mut a, n, &mut pivots, &mut sign)?;
} else {
for k in 0..n {
lu_eliminate_step(&mut a, n, k, n, &mut pivots, &mut sign)?;
}
}
Ok(LuDecomposition {
factors: Array2::from_shape_vec([n, n], a).expect("square factor storage"),
pivots,
sign,
})
}
fn lu_eliminate_step<T: RealScalar>(
a: &mut [T],
n: usize,
k: usize,
update_end: usize,
pivots: &mut [usize],
sign: &mut i8,
) -> Result<()> {
let mut pivot_row = k;
let mut pivot_mag = a[k * n + k].abs();
for r in (k + 1)..n {
let mag = a[r * n + k].abs();
if mag > pivot_mag {
pivot_mag = mag;
pivot_row = r;
}
}
if pivot_mag == T::ZERO {
return Err(LetoError::StorageError {
reason: format!("LU pivot column {k} is exactly zero: matrix is singular"),
});
}
if pivot_row != k {
for c in 0..n {
a.swap(k * n + c, pivot_row * n + c);
}
pivots.swap(k, pivot_row);
*sign = -*sign;
}
let pivot = a[k * n + k];
let (head, tail) = a.split_at_mut((k + 1) * n);
let pivot_row = &head[k * n + (k + 1)..k * n + update_end];
for r in (k + 1)..n {
let base = (r - (k + 1)) * n;
let factor = tail[base + k].div(pivot);
tail[base + k] = factor;
let target = &mut tail[base + (k + 1)..base + update_end];
T::axpy_slice(T::ZERO.sub(factor), pivot_row, target);
}
Ok(())
}
fn lu_eliminate_blocked<T: RealScalar>(
a: &mut [T],
n: usize,
pivots: &mut [usize],
sign: &mut i8,
) -> Result<()> {
let mut neg_l21 = vec![T::ZERO; n * LU_PANEL_WIDTH];
let mut u12 = vec![T::ZERO; n * LU_PANEL_WIDTH];
let mut k = 0;
while k < n {
let nb = (n - k).min(LU_PANEL_WIDTH);
let panel_end = k + nb;
for j in k..panel_end {
lu_eliminate_step(a, n, j, panel_end, pivots, sign)?;
}
if panel_end < n {
let m = n - panel_end;
for c in panel_end..n {
for r in k..panel_end {
let mut dot = T::ZERO;
for t in k..r {
dot = dot.add(a[r * n + t].mul(a[t * n + c]));
}
a[r * n + c] = a[r * n + c].sub(dot);
}
}
for (i, row) in (panel_end..n).enumerate() {
for (j, col) in (k..panel_end).enumerate() {
neg_l21[i * nb + j] = T::ZERO.sub(a[row * n + col]);
}
}
for (i, row) in (k..panel_end).enumerate() {
for (j, col) in (panel_end..n).enumerate() {
u12[i * m + j] = a[row * n + col];
}
}
let lhs: ArrayView2<'_, T> =
ArrayView2::try_new(Layout::c_contiguous([m, nb])?, &neg_l21[..m * nb])?;
let rhs: ArrayView2<'_, T> =
ArrayView2::try_new(Layout::c_contiguous([nb, m])?, &u12[..nb * m])?;
let stride = isize::try_from(n)
.expect("LU dimension fits a view stride: n² elements are allocated");
let mut trailing: ArrayViewMut2<'_, T> = ArrayViewMut2::try_new(
Layout::try_new([m, m], [stride, 1], panel_end * n + panel_end)?,
&mut *a,
)?;
matmul_accumulate(&lhs, &rhs, &mut trailing)?;
}
k = panel_end;
}
Ok(())
}
impl<T: RealScalar> LuDecomposition<T> {
#[must_use]
#[inline]
pub fn from_raw_parts(factors: Array2<T>, pivots: Vec<usize>, sign: i8) -> Self {
Self {
factors,
pivots,
sign,
}
}
#[must_use]
#[inline]
pub fn dim(&self) -> usize {
self.pivots.len()
}
#[must_use]
#[inline]
pub fn factors(&self) -> &Array2<T> {
&self.factors
}
#[must_use]
#[inline]
pub fn pivots(&self) -> &[usize] {
&self.pivots
}
#[must_use]
pub fn det(&self) -> T {
let n = self.dim();
let mut det = if self.sign >= 0 {
T::ONE
} else {
T::ZERO.sub(T::ONE)
};
for k in 0..n {
det = det.mul(*self.factors.get([k, k]).expect("diagonal in bounds"));
}
det
}
#[allow(clippy::needless_range_loop)]
pub fn solve_into(
&self,
rhs: &ArrayView1<'_, T>,
out: &mut ArrayViewMut1<'_, T>,
) -> Result<()> {
let n = self.dim();
if rhs.shape() != [n] {
return Err(LetoError::ShapeMismatch {
lhs: rhs.shape().to_vec(),
rhs: vec![n],
});
}
if out.shape() != [n] {
return Err(LetoError::ShapeMismatch {
lhs: out.shape().to_vec(),
rhs: vec![n],
});
}
if let Some(out_slice) = out.as_mut_slice() {
if let Some(rhs_slice) = rhs.as_slice() {
for k in 0..n {
out_slice[k] = rhs_slice[self.pivots[k]];
}
} else {
for k in 0..n {
out_slice[k] = *rhs.get([self.pivots[k]])?;
}
}
self.solve_in_place(out_slice);
} else {
if let Some(rhs_slice) = rhs.as_slice() {
for k in 0..n {
*out.get_mut([k])? = rhs_slice[self.pivots[k]];
}
} else {
for k in 0..n {
*out.get_mut([k])? = *rhs.get([self.pivots[k]])?;
}
}
let f = self.factors.storage().as_slice();
for r in 1..n {
let mut dot = T::ZERO;
for c in 0..r {
let f_rc = f[r * n + c];
let x_c = *out.get([c])?;
dot = dot.add(f_rc.mul(x_c));
}
let out_r = out.get_mut([r])?;
*out_r = out_r.sub(dot);
}
for r in (0..n).rev() {
let mut dot = T::ZERO;
for c in (r + 1)..n {
let f_rc = f[r * n + c];
let x_c = *out.get([c])?;
dot = dot.add(f_rc.mul(x_c));
}
let out_r = out.get_mut([r])?;
*out_r = out_r.sub(dot).div(f[r * n + r]);
}
}
Ok(())
}
pub fn solve(&self, rhs: &ArrayView1<'_, T>) -> Result<Array1<T>> {
let n = self.dim();
let mut out = Array1::from_elem([n], T::ZERO);
self.solve_into(rhs, &mut out.view_mut())?;
Ok(out)
}
pub fn inv(&self) -> Result<Array2<T>> {
let n = self.dim();
let mut out = vec![T::ZERO; n * n];
let mut column = vec![T::ZERO; n];
for j in 0..n {
for (k, slot) in column.iter_mut().enumerate() {
*slot = if self.pivots[k] == j { T::ONE } else { T::ZERO };
}
self.solve_in_place(&mut column);
for r in 0..n {
out[r * n + j] = column[r];
}
}
Array2::from_shape_vec([n, n], out)
}
fn solve_in_place(&self, x: &mut [T]) {
let n = self.dim();
let f = self.factors.storage().as_slice();
for r in 1..n {
let dot = T::dot_slice(&f[r * n..r * n + r], &x[..r]);
x[r] = x[r].sub(dot);
}
for r in (0..n).rev() {
let dot = T::dot_slice(&f[r * n + r + 1..r * n + n], &x[r + 1..n]);
x[r] = x[r].sub(dot).div(f[r * n + r]);
}
}
}
#[inline]
pub fn solve<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
rhs: &ArrayView1<'_, T>,
) -> Result<Array1<T>> {
lu_decompose(matrix)?.solve(rhs)
}
pub fn det<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<T> {
match lu_decompose(matrix) {
Ok(decomposition) => Ok(decomposition.det()),
Err(LetoError::StorageError { reason }) if reason.contains("singular") => Ok(T::ZERO),
Err(other) => Err(other),
}
}
#[inline]
pub fn inv<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<Array2<T>> {
lu_decompose(matrix)?.inv()
}
#[cfg(test)]
mod tests {
use super::*;
fn diagonally_dominant(n: usize) -> Vec<f64> {
let mut data = vec![0.0f64; n * n];
for i in 0..n {
for j in 0..n {
data[i * n + j] = ((i * 7 + j * 13) % 17) as f64 * 0.01 - 0.08;
}
data[i * n + i] += n as f64;
}
data
}
fn eliminate_unblocked(a: &mut [f64], n: usize, pivots: &mut [usize], sign: &mut i8) {
for k in 0..n {
lu_eliminate_step(a, n, k, n, pivots, sign).expect("fixture is nonsingular");
}
}
fn max_abs_diff(a: &[f64], b: &[f64]) -> f64 {
assert_eq!(a.len(), b.len());
a.iter()
.zip(b)
.map(|(x, y)| (x - y).abs())
.fold(0.0f64, f64::max)
}
#[test]
fn blocked_path_matches_unblocked_within_rounding() {
let n = 100usize;
let data = diagonally_dominant(n);
let mut blocked = data.clone();
let mut blocked_pivots: Vec<usize> = (0..n).collect();
let mut blocked_sign = 1i8;
lu_eliminate_blocked(&mut blocked, n, &mut blocked_pivots, &mut blocked_sign)
.expect("fixture is nonsingular");
let mut plain = data.clone();
let mut plain_pivots: Vec<usize> = (0..n).collect();
let mut plain_sign = 1i8;
eliminate_unblocked(&mut plain, n, &mut plain_pivots, &mut plain_sign);
assert_eq!(blocked_pivots, plain_pivots);
assert_eq!(blocked_sign, plain_sign);
let err = max_abs_diff(&blocked, &plain);
assert!(err < 1e-9, "blocked-vs-unblocked max factor diff {err}");
}
#[test]
fn blocked_path_matches_unblocked_for_reduced_width_scalar() {
let n = 100usize;
let data: Vec<f32> = diagonally_dominant(n).iter().map(|&v| v as f32).collect();
let mut blocked = data.clone();
let mut blocked_pivots: Vec<usize> = (0..n).collect();
let mut blocked_sign = 1i8;
lu_eliminate_blocked(&mut blocked, n, &mut blocked_pivots, &mut blocked_sign)
.expect("fixture is nonsingular");
let mut plain = data.clone();
let mut plain_pivots: Vec<usize> = (0..n).collect();
let mut plain_sign = 1i8;
for k in 0..n {
lu_eliminate_step(&mut plain, n, k, n, &mut plain_pivots, &mut plain_sign)
.expect("fixture is nonsingular");
}
assert_eq!(blocked_pivots, plain_pivots);
assert_eq!(blocked_sign, plain_sign);
let err: f32 = blocked
.iter()
.zip(&plain)
.map(|(x, y)| (x - y).abs())
.fold(0.0f32, f32::max);
assert!(err < 1e-2, "blocked-vs-unblocked max factor diff {err}");
}
#[test]
fn sub_panel_orders_are_bitwise_identical_to_unblocked() {
for n in [1usize, 2, 63, 64] {
let data = diagonally_dominant(n);
let mut blocked = data.clone();
let mut blocked_pivots: Vec<usize> = (0..n).collect();
let mut blocked_sign = 1i8;
lu_eliminate_blocked(&mut blocked, n, &mut blocked_pivots, &mut blocked_sign)
.expect("fixture is nonsingular");
let mut plain = data.clone();
let mut plain_pivots: Vec<usize> = (0..n).collect();
let mut plain_sign = 1i8;
eliminate_unblocked(&mut plain, n, &mut plain_pivots, &mut plain_sign);
assert_eq!(blocked, plain, "factors differ at n = {n}");
assert_eq!(blocked_pivots, plain_pivots, "pivots differ at n = {n}");
assert_eq!(blocked_sign, plain_sign, "sign differs at n = {n}");
}
}
#[test]
fn partial_second_panel_matches_unblocked() {
let n = 65usize;
let data = diagonally_dominant(n);
let mut blocked = data.clone();
let mut blocked_pivots: Vec<usize> = (0..n).collect();
let mut blocked_sign = 1i8;
lu_eliminate_blocked(&mut blocked, n, &mut blocked_pivots, &mut blocked_sign)
.expect("fixture is nonsingular");
let mut plain = data.clone();
let mut plain_pivots: Vec<usize> = (0..n).collect();
let mut plain_sign = 1i8;
eliminate_unblocked(&mut plain, n, &mut plain_pivots, &mut plain_sign);
assert_eq!(blocked_pivots, plain_pivots);
assert_eq!(blocked_sign, plain_sign);
let err = max_abs_diff(&blocked, &plain);
assert!(err < 1e-9, "blocked-vs-unblocked max factor diff {err}");
}
#[test]
fn blocked_path_rejects_singular_like_unblocked() {
let mut blocked = vec![1.0f64, 2.0, 3.0, 2.0, 4.0, 6.0, 1.0, 0.0, 1.0];
let mut pivots: Vec<usize> = (0..3).collect();
let mut sign = 1i8;
let blocked_err = lu_eliminate_blocked(&mut blocked, 3, &mut pivots, &mut sign)
.expect_err("singular matrix must fail");
assert!(
format!("{blocked_err:?}").contains("singular"),
"unexpected error: {blocked_err:?}"
);
let mut plain = vec![1.0f64, 2.0, 3.0, 2.0, 4.0, 6.0, 1.0, 0.0, 1.0];
let mut pivots: Vec<usize> = (0..3).collect();
let mut sign = 1i8;
let plain_err = (0..3)
.try_for_each(|k| lu_eliminate_step(&mut plain, 3, k, 3, &mut pivots, &mut sign))
.expect_err("singular matrix must fail");
assert!(
format!("{plain_err:?}").contains("singular"),
"unexpected error: {plain_err:?}"
);
}
#[test]
fn gate_pins_the_spill_boundary() {
let fallback = CacheGeometry::fallback();
assert!(!lu_uses_blocked_path(fallback, 1024, 8));
assert!(lu_uses_blocked_path(fallback, 1025, 8));
assert!(!lu_uses_blocked_path(fallback, 1448, 4));
assert!(lu_uses_blocked_path(fallback, 1449, 4));
assert!(!lu_uses_blocked_path(fallback, 0, 8));
assert!(lu_uses_blocked_path(fallback, usize::MAX, 8));
}
}