use crate::error::OdeError;
pub(crate) const SPARSE_LU_MIN_N: usize = 64;
#[derive(Clone)]
pub struct CsrMatrix {
nrows: usize,
ncols: usize,
indptr: Vec<usize>,
indices: Vec<usize>,
data: Vec<f64>,
}
impl CsrMatrix {
#[must_use]
pub fn nrows(&self) -> usize {
self.nrows
}
#[must_use]
pub fn ncols(&self) -> usize {
self.ncols
}
#[must_use]
pub fn from_dense(dense: &[f64], nrows: usize, ncols: usize) -> Self {
debug_assert_eq!(dense.len(), nrows * ncols);
let mut indptr = vec![0usize; nrows + 1];
let mut indices = Vec::new();
let mut data = Vec::new();
for r in 0..nrows {
let row = &dense[r * ncols..(r + 1) * ncols];
for (c, &v) in row.iter().enumerate() {
if v != 0.0 {
indices.push(c);
data.push(v);
}
}
indptr[r + 1] = indices.len();
}
CsrMatrix {
nrows,
ncols,
indptr,
indices,
data,
}
}
#[must_use]
pub fn nnz(&self) -> usize {
self.data.len()
}
#[must_use]
pub fn get(&self, r: usize, c: usize) -> f64 {
let start = self.indptr[r];
let end = self.indptr[r + 1];
match self.indices[start..end].binary_search(&c) {
Ok(pos) => self.data[start + pos],
Err(_) => 0.0,
}
}
#[must_use]
pub fn mat_vec(&self, x: &[f64]) -> Vec<f64> {
assert_eq!(x.len(), self.ncols, "vector length must match ncols");
let mut y = vec![0.0; self.nrows];
for (r, yr) in y.iter_mut().enumerate() {
let mut s = 0.0;
for k in self.indptr[r]..self.indptr[r + 1] {
s += self.data[k] * x[self.indices[k]];
}
*yr = s;
}
y
}
#[must_use]
pub fn scaled_identity_minus_scaled(&self, diag: f64) -> CsrMatrix {
debug_assert_eq!(self.ncols, self.nrows);
let n = self.nrows;
let mut indptr = vec![0usize; n + 1];
let mut indices = Vec::new();
let mut data = Vec::new();
for r in 0..n {
let start = self.indptr[r];
let end = self.indptr[r + 1];
let mut k = start;
while k < end && self.indices[k] < r {
indices.push(self.indices[k]);
data.push(-diag * self.data[k]);
k += 1;
}
if k < end && self.indices[k] == r {
indices.push(r);
data.push(1.0 - diag * self.data[k]);
k += 1;
} else {
indices.push(r);
data.push(1.0);
}
while k < end {
indices.push(self.indices[k]);
data.push(-diag * self.data[k]);
k += 1;
}
indptr[r + 1] = indices.len();
}
CsrMatrix {
nrows: n,
ncols: n,
indptr,
indices,
data,
}
}
#[cfg(test)]
pub fn to_dense(&self) -> Vec<f64> {
let mut d = vec![0.0; self.nrows * self.ncols];
for r in 0..self.nrows {
for k in self.indptr[r]..self.indptr[r + 1] {
d[r * self.ncols + self.indices[k]] = self.data[k];
}
}
d
}
pub fn jacobian<F>(f: F, t: f64, y: &[f64], f0: &[f64], cols: Option<&[usize]>) -> CsrMatrix
where
F: Fn(f64, &[f64], &mut [f64]),
{
let n = y.len();
let sqrt_eps = f64::sqrt(f64::EPSILON);
let perturb: Vec<usize> = match cols {
Some(c) => c.to_vec(),
None => (0..n).collect(),
};
let mut rows = Vec::new();
let mut cols = Vec::new();
let mut vals = Vec::new();
for &col in &perturb {
let dy = sqrt_eps * y[col].abs().max(1.0);
let mut yp = y.to_vec();
yp[col] += dy;
let mut fp = vec![0.0; n];
f(t, &yp, &mut fp);
let inv = 1.0 / dy;
for row in 0..n {
let val = (fp[row] - f0[row]) * inv;
if val != 0.0 {
rows.push(row);
cols.push(col);
vals.push(val);
}
}
}
let mut order: Vec<usize> = (0..rows.len()).collect();
order.sort_by(|&a, &b| (rows[a], cols[a]).cmp(&(rows[b], cols[b])));
let mut indptr = vec![0usize; n + 1];
for &k in &order {
indptr[rows[k] + 1] += 1;
}
for r in 0..n {
indptr[r + 1] += indptr[r];
}
let mut indices = Vec::with_capacity(vals.len());
let mut data = Vec::with_capacity(vals.len());
for &k in &order {
indices.push(cols[k]);
data.push(vals[k]);
}
CsrMatrix {
nrows: n,
ncols: n,
indptr,
indices,
data,
}
}
#[must_use]
pub fn sparse_solve(&self, b: &[f64]) -> Option<Vec<f64>> {
let n = self.nrows;
if self.ncols != n || b.len() != n {
return None;
}
let mut lu = vec![0.0; n * n];
for r in 0..n {
for k in self.indptr[r]..self.indptr[r + 1] {
lu[r * n + self.indices[k]] = self.data[k];
}
}
let mut piv = (0..n).collect::<Vec<_>>();
for k in 0..n {
let mut p = k;
let mut max = lu[k * n + k].abs();
for i in (k + 1)..n {
let v = lu[i * n + k].abs();
if v > max {
max = v;
p = i;
}
}
if max < 1e-14 {
return None;
}
if p != k {
for j in 0..n {
lu.swap(k * n + j, p * n + j);
}
piv.swap(k, p);
}
let pivot = lu[k * n + k];
for i in (k + 1)..n {
let fac = lu[i * n + k] / pivot;
lu[i * n + k] = fac;
for j in (k + 1)..n {
lu[i * n + j] -= fac * lu[k * n + j];
}
}
}
let mut y = vec![0.0; n];
for i in 0..n {
let pi = piv[i];
let mut s = b[pi];
for j in 0..i {
s -= lu[i * n + j] * y[j];
}
y[i] = s;
}
let mut x = vec![0.0; n];
for i in (0..n).rev() {
let mut s = y[i];
for j in (i + 1)..n {
s -= lu[i * n + j] * x[j];
}
x[i] = s / lu[i * n + i];
}
Some(x)
}
}
pub(crate) fn sdirk_stage_sparse(
f: &dyn crate::RhsCallable,
t_stage: f64,
y_base: &[f64],
diag: f64,
k_guess: &[f64],
) -> Result<Vec<f64>, OdeError> {
let n = y_base.len();
let mut k = k_guess.to_vec();
for _iter in 0..50 {
let y_stage: Vec<f64> = y_base.iter().zip(&k).map(|(b, kk)| b + diag * kk).collect();
let mut fk = vec![0.0; n];
f.call(t_stage, &y_stage, &mut fk)
.expect("RHS evaluation must not fail for a well-formed problem");
let r: Vec<f64> = k.iter().zip(&fk).map(|(kk, fv)| kk - fv).collect();
let rnorm = r.iter().map(|x| x * x).sum::<f64>().sqrt();
if rnorm < 1e-12 {
return Ok(k);
}
let jac = CsrMatrix::jacobian(
|t, y, dydt| {
f.call(t, y, dydt)
.expect("RHS evaluation must not fail for a well-formed problem");
},
t_stage,
&y_stage,
&fk,
None,
);
let a = jac.scaled_identity_minus_scaled(diag);
let delta = a.sparse_solve(&r).ok_or(OdeError::Newton {
t: t_stage,
residual: rnorm,
})?;
for (ki, di) in k.iter_mut().zip(&delta) {
*ki -= di;
}
}
Ok(k)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn csr_mat_vec_matches_dense() {
let a = CsrMatrix::from_dense(&[2.0, 0.0, 1.0, 0.0, 3.0, 0.0, 1.0, 0.0, 4.0], 3, 3);
let y = a.mat_vec(&[1.0, 2.0, 3.0]);
assert!((y[0] - 5.0).abs() < 1e-12);
assert!((y[1] - 6.0).abs() < 1e-12);
assert!((y[2] - 13.0).abs() < 1e-12);
}
#[test]
fn sparse_solve_matches_dense_solve() {
let dense = [2.0, 1.0, 1.0, 1.0, 3.0, 2.0, 1.0, 0.0, 1.0];
let a = CsrMatrix::from_dense(&dense, 3, 3);
let b = [4.0, 6.0, 2.0];
let x = a.sparse_solve(&b).expect("non-singular");
assert!((x[0] - 1.0).abs() < 1e-12);
assert!((x[1] - 1.0).abs() < 1e-12);
assert!((x[2] - 1.0).abs() < 1e-12);
}
#[test]
fn sparse_solve_pivots_on_singular_offdiag() {
let a = CsrMatrix::from_dense(&[0.0, 1.0, 1.0, 0.0], 2, 2);
let x = a
.sparse_solve(&[3.0, 4.0])
.expect("non-singular after pivot");
assert!((x[0] - 4.0).abs() < 1e-12);
assert!((x[1] - 3.0).abs() < 1e-12);
}
#[test]
fn sparse_solve_detects_singular() {
let a = CsrMatrix::from_dense(&[1.0, 1.0, 2.0, 2.0], 2, 2);
assert!(a.sparse_solve(&[1.0, 1.0]).is_none());
}
#[test]
fn jacobian_csr_of_linear_system() {
let a = CsrMatrix::from_dense(&[0.0, 1.0, -2.0, -3.0], 2, 2);
let dense_j = a.to_dense();
let f = move |_t: f64, y: &[f64], dydt: &mut [f64]| {
let out = a.mat_vec(y);
dydt[0] = out[0];
dydt[1] = out[1];
};
let y = [0.7, -1.3];
let mut f0 = [0.0; 2];
f(0.0, &y, &mut f0);
let j = CsrMatrix::jacobian(&f, 0.0, &y, &f0, None);
assert!((j.get(0, 0) - 0.0).abs() < 1e-8);
assert!((j.get(0, 1) - 1.0).abs() < 1e-8);
assert!((j.get(1, 0) - (-2.0)).abs() < 1e-8);
assert!((j.get(1, 1) - (-3.0)).abs() < 1e-8);
let jac = CsrMatrix::from_dense(&dense_j, 2, 2);
let csr = jac.scaled_identity_minus_scaled(0.1);
let r = [1.5, -2.5];
let xs = csr.sparse_solve(&r).unwrap();
let mut dense_a = crate::linalg::DMat::identity(2);
for i in 0..2 {
for jj in 0..2 {
dense_a.set(i, jj, dense_a.get(i, jj) - 0.1 * dense_j[i * 2 + jj]);
}
}
let xd = dense_a.solve(&r).unwrap();
assert!((xs[0] - xd[0]).abs() < 1e-10);
assert!((xs[1] - xd[1]).abs() < 1e-10);
}
#[test]
fn bdf_sparse_path_solves_large_decoupled_system() {
const N: usize = 80;
let prob = crate::OdeProblem::new(
|_t, y, dydt| {
for (i, yi) in y.iter().enumerate() {
dydt[i] = -((i + 1) as f64) * yi;
}
},
vec![1.0; N],
0.0,
)
.unwrap();
let t = 0.5;
let y = prob.solve(crate::Method::Bdf, t).unwrap();
for (i, yi) in y.iter().enumerate() {
let expected = (-((i + 1) as f64) * t).exp();
assert!(
(yi - expected).abs() < 1e-6,
"component {i}: {yi} vs {expected}"
);
}
}
#[test]
fn scaled_identity_handles_missing_diagonal() {
let j = CsrMatrix::from_dense(&[0.0, 2.0, 0.0, 0.0], 2, 2);
let a = j.scaled_identity_minus_scaled(0.5);
assert!((a.get(0, 0) - 1.0).abs() < 1e-14);
assert!((a.get(0, 1) - (-1.0)).abs() < 1e-14);
assert!((a.get(1, 0) - 0.0).abs() < 1e-14);
assert!((a.get(1, 1) - 1.0).abs() < 1e-14);
let x = a.sparse_solve(&[1.0, 2.0]).unwrap();
assert!((x[0] - 3.0).abs() < 1e-12);
assert!((x[1] - 2.0).abs() < 1e-12);
}
#[test]
fn sparse_sdirk_stage_matches_dense_oracle_on_tridiagonal_system() {
const N: usize = 80;
let mut dense = vec![0.0; N * N];
for i in 0..N {
dense[i * N + i] = -2.0;
if i > 0 {
dense[i * N + i - 1] = 1.0;
}
if i + 1 < N {
dense[i * N + i + 1] = 1.0;
}
}
let a = CsrMatrix::from_dense(&dense, N, N);
let f = move |_t: f64, y: &[f64], dydt: &mut [f64]| {
let out = a.mat_vec(y);
dydt.copy_from_slice(&out);
};
let y: Vec<f64> = (0..N).map(|i| 0.1 * (i as f64).sin() + 0.2).collect();
let diag = 0.05;
let k = sdirk_stage_sparse(&f, 0.0, &y, diag, &vec![0.0; N]).unwrap();
let mut am = crate::linalg::DMat::new(N, N);
for i in 0..N {
for jj in 0..N {
am.set(i, jj, dense[i * N + jj]);
}
}
let ay = am.mat_vec(&y);
let mut m = crate::linalg::DMat::new(N, N);
for i in 0..N {
for jj in 0..N {
let v = if i == jj { 1.0 } else { 0.0 } - diag * dense[i * N + jj];
m.set(i, jj, v);
}
}
let expected = m.solve(&ay).unwrap();
for (i, (kv, ev)) in k.iter().zip(&expected).enumerate() {
assert!((kv - ev).abs() < 1e-8, "component {i}: {kv} vs {ev}");
}
}
}