use crate::grid::{Boundary, UniformGrid1D, UniformGrid2D, UniformGrid3D};
use crate::operator::laplacian_3d_rows;
#[derive(Debug, Clone)]
pub struct CsrMatrix {
nrows: usize,
ncols: usize,
pub row_ptr: Vec<usize>,
pub col_ind: Vec<usize>,
pub values: 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(m: &tpt_math_linalg::tpt_math_linalg_dense::DMatrix<f64>) -> Self {
let nrows = m.nrows();
let ncols = m.ncols();
let mut row_ptr = Vec::with_capacity(nrows + 1);
let mut col_ind = Vec::new();
let mut values = Vec::new();
let mut offset = 0;
row_ptr.push(0);
for i in 0..nrows {
for j in 0..ncols {
let v = m[(i, j)];
if v != 0.0 {
col_ind.push(j);
values.push(v);
offset += 1;
}
}
row_ptr.push(offset);
}
Self {
nrows,
ncols,
row_ptr,
col_ind,
values,
}
}
#[must_use]
pub fn from_rows(nrows: usize, ncols: usize, rows: &[Vec<(usize, f64)>]) -> Self {
pack_csr(nrows, ncols, rows)
}
#[must_use]
pub fn mul_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 (i, slot) in y.iter_mut().enumerate() {
let start = self.row_ptr[i];
let end = self.row_ptr[i + 1];
let mut acc = 0.0;
for k in start..end {
acc += self.values[k] * x[self.col_ind[k]];
}
*slot = acc;
}
y
}
}
#[must_use]
pub fn laplacian_1d_sparse(grid: &UniformGrid1D, bc: Boundary) -> CsrMatrix {
let n = grid.n();
let dx2 = grid.dx() * grid.dx();
let is_boundary = |k: usize| k == 0 || k == n - 1;
let mut rows: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
for (i, row) in rows.iter_mut().enumerate() {
if bc == Boundary::Dirichlet && is_boundary(i) {
row.push((i, 1.0));
continue;
}
if bc == Boundary::Neumann && i == 0 {
row.push((0, -2.0 / dx2));
row.push((1, 2.0 / dx2));
continue;
}
if bc == Boundary::Neumann && i == n - 1 {
row.push((n - 1, -2.0 / dx2));
row.push((n - 2, 2.0 / dx2));
continue;
}
if i > 0 {
let left = i - 1;
if !(bc == Boundary::Dirichlet && is_boundary(left)) {
row.push((left, 1.0 / dx2));
}
}
row.push((i, -2.0 / dx2));
if i + 1 < n {
let right = i + 1;
if !(bc == Boundary::Dirichlet && is_boundary(right)) {
row.push((right, 1.0 / dx2));
}
}
}
pack_csr(n, n, &rows)
}
#[must_use]
pub fn laplacian_2d_sparse(grid: &UniformGrid2D, bc: Boundary) -> CsrMatrix {
let nx = grid.nx();
let ny = grid.ny();
let n = nx * ny;
let dx2 = grid.dx() * grid.dx();
let dy2 = grid.dy() * grid.dy();
let idx = |ix: usize, iy: usize| ix + iy * nx;
let mut rows: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
for iy in 0..ny {
for ix in 0..nx {
let i = idx(ix, iy);
let on_boundary = ix == 0 || ix == nx - 1 || iy == 0 || iy == ny - 1;
if bc == Boundary::Dirichlet && on_boundary {
rows[i].push((i, 1.0));
continue;
}
let xm = if ix > 0 { ix - 1 } else { ix };
let xp = if ix + 1 < nx { ix + 1 } else { ix };
if bc == Boundary::Neumann || ix > 0 {
rows[i].push((idx(xm, iy), 1.0 / dx2));
}
rows[i].push((i, -2.0 / dx2));
if bc == Boundary::Neumann || ix + 1 < nx {
rows[i].push((idx(xp, iy), 1.0 / dx2));
}
let ym = if iy > 0 { iy - 1 } else { iy };
let yp = if iy + 1 < ny { iy + 1 } else { iy };
if bc == Boundary::Neumann || iy > 0 {
rows[i].push((idx(ix, ym), 1.0 / dy2));
}
rows[i].push((i, -2.0 / dy2));
if bc == Boundary::Neumann || iy + 1 < ny {
rows[i].push((idx(ix, yp), 1.0 / dy2));
}
}
}
pack_csr(n, n, &rows)
}
#[must_use]
pub fn laplacian_3d_sparse(grid: &UniformGrid3D, bc: Boundary) -> CsrMatrix {
let rows = laplacian_3d_rows(grid, bc);
let n = grid.len();
pack_csr(n, n, &rows)
}
#[must_use]
pub fn diffuse_step(u: &[f64], laplacian: &CsrMatrix, dt: f64, diffusion: f64) -> Vec<f64> {
let lap = laplacian.mul_vec(u);
u.iter()
.zip(&lap)
.map(|(u_i, lap_i)| u_i + dt * diffusion * lap_i)
.collect()
}
#[must_use]
pub fn conjugate_gradient(
a: &CsrMatrix,
b: &[f64],
x0: Option<&[f64]>,
tol: f64,
max_iter: usize,
) -> Vec<f64> {
let n = a.nrows();
let mut x = match x0 {
Some(v) => v.to_vec(),
None => vec![0.0; n],
};
let mut r = {
let ax = a.mul_vec(&x);
b.iter()
.zip(&ax)
.map(|(bi, axi)| bi - axi)
.collect::<Vec<f64>>()
};
let mut p = r.clone();
let mut rsold = r.iter().zip(&r).map(|(a, b)| a * b).sum::<f64>();
let bnrm = b.iter().map(|v| v * v).sum::<f64>().sqrt();
let threshold = if bnrm > 0.0 { tol * bnrm } else { tol };
let rnorm = rsold.sqrt();
if rnorm < threshold {
return x;
}
for _ in 0..max_iter {
let ap = a.mul_vec(&p);
let p_ap = p.iter().zip(&ap).map(|(a, b)| a * b).sum::<f64>();
let alpha = rsold / p_ap;
for i in 0..n {
x[i] += alpha * p[i];
}
for (ri, api) in r.iter_mut().zip(&ap) {
*ri -= alpha * api;
}
let rsnew = r.iter().zip(&r).map(|(a, b)| a * b).sum::<f64>();
if rsnew.sqrt() < threshold {
return x;
}
let beta = rsnew / rsold;
for (pi, ri) in p.iter_mut().zip(&r) {
*pi = *ri + beta * *pi;
}
rsold = rsnew;
}
x
}
fn pack_csr(nrows: usize, ncols: usize, rows: &[Vec<(usize, f64)>]) -> CsrMatrix {
let mut row_ptr = Vec::with_capacity(nrows + 1);
let mut col_ind = Vec::new();
let mut values = Vec::new();
let mut offset = 0;
row_ptr.push(0);
for r in rows {
let mut entries = r.clone();
entries.sort_by_key(|&(c, _)| c);
let mut i = 0;
while i < entries.len() {
let (c, mut v) = entries[i];
let mut j = i + 1;
while j < entries.len() && entries[j].0 == c {
v += entries[j].1;
j += 1;
}
col_ind.push(c);
values.push(v);
offset += 1;
i = j;
}
row_ptr.push(offset);
}
CsrMatrix {
nrows,
ncols,
row_ptr,
col_ind,
values,
}
}
#[cfg(test)]
mod tests {
use super::*;
use approx::assert_abs_diff_eq;
use tpt_math_linalg::tpt_math_linalg_dense::DVector;
#[test]
fn sparse_1d_matches_dense_laplacian() {
let g = UniformGrid1D::new(21, 0.0, 1.0).unwrap();
let sparse = laplacian_1d_sparse(&g, Boundary::Dirichlet);
let dense = crate::laplacian_1d(&g, Boundary::Dirichlet);
for i in 0..g.n() {
let start = sparse.row_ptr[i];
let end = sparse.row_ptr[i + 1];
for k in start..end {
assert_abs_diff_eq!(
sparse.values[k],
dense[(i, sparse.col_ind[k])],
epsilon = 1e-12
);
}
}
}
#[test]
fn sparse_mul_vec_matches_dense() {
let g = UniformGrid1D::new(11, 0.0, 1.0).unwrap();
let sparse = laplacian_1d_sparse(&g, Boundary::Dirichlet);
let dense = crate::laplacian_1d(&g, Boundary::Dirichlet);
let u: Vec<f64> = (0..g.n()).map(|i| i as f64 * 0.1).collect();
let y_sparse = sparse.mul_vec(&u);
let y_dense = dense * DVector::from_vec(u);
for i in 0..g.n() {
assert_abs_diff_eq!(y_sparse[i], y_dense[i], epsilon = 1e-12);
}
}
#[test]
fn sparse_2d_laplacian_of_quadratic() {
let g = UniformGrid2D::new(41, 0.0, 1.0, 41, 0.0, 1.0).unwrap();
let l = laplacian_2d_sparse(&g, Boundary::Dirichlet);
let xs = g.x_coordinates();
let ys = g.y_coordinates();
let u: Vec<f64> = (0..g.len())
.map(|k| {
let ix = k % g.nx();
let iy = k / g.nx();
(xs[ix] * (1.0 - xs[ix]) + ys[iy] * (1.0 - ys[iy])) / 4.0
})
.collect();
let lu = l.mul_vec(&u);
let mid = g.len() / 2;
assert_abs_diff_eq!(lu[mid], -1.0, epsilon = 2e-2);
}
#[test]
fn diffuse_step_reduces_gradient() {
let g = UniformGrid1D::new(51, 0.0, 1.0).unwrap();
let l = laplacian_1d_sparse(&g, Boundary::Dirichlet);
let u: Vec<f64> = g.coordinates().iter().map(|&x| x * (1.0 - x)).collect();
let u1 = diffuse_step(&u, &l, 0.0005, 1.0);
let grad0: f64 = u.windows(2).map(|w| (w[1] - w[0]).abs()).sum();
let grad1: f64 = u1.windows(2).map(|w| (w[1] - w[0]).abs()).sum();
assert!(grad1 < grad0, "diffusion should smooth the parabola");
}
#[test]
fn sparse_3d_matches_dense_laplacian() {
let g = UniformGrid3D::new(9, 0.0, 1.0, 9, 0.0, 1.0, 9, 0.0, 1.0).unwrap();
let sparse = laplacian_3d_sparse(&g, Boundary::Dirichlet);
let dense = crate::laplacian_3d(&g, Boundary::Dirichlet);
assert_eq!(sparse.nrows(), dense.nrows());
assert_eq!(sparse.ncols(), dense.ncols());
for i in 0..sparse.nrows() {
let start = sparse.row_ptr[i];
let end = sparse.row_ptr[i + 1];
for k in start..end {
assert_abs_diff_eq!(
sparse.values[k],
dense[(i, sparse.col_ind[k])],
epsilon = 1e-12
);
}
}
}
#[test]
fn sparse_3d_laplacian_of_quadratic() {
let g = UniformGrid3D::new(15, 0.0, 1.0, 15, 0.0, 1.0, 15, 0.0, 1.0).unwrap();
let l = laplacian_3d_sparse(&g, Boundary::Dirichlet);
let xs = g.x_coordinates();
let ys = g.y_coordinates();
let zs = g.z_coordinates();
let u: Vec<f64> = (0..g.len())
.map(|k| {
let ix = k % g.nx();
let iy = (k / g.nx()) % g.ny();
let iz = k / (g.nx() * g.ny());
(xs[ix] * (1.0 - xs[ix]) + ys[iy] * (1.0 - ys[iy]) + zs[iz] * (1.0 - zs[iz])) / 6.0
})
.collect();
let lu = l.mul_vec(&u);
let mid = g.len() / 2;
assert_abs_diff_eq!(lu[mid], -1.0, epsilon = 5e-2);
}
#[test]
fn conjugate_gradient_solves_poisson() {
let g = UniformGrid1D::new(81, 0.0, 1.0).unwrap();
let a = laplacian_1d_sparse(&g, Boundary::Dirichlet);
let xs = g.coordinates();
let u: Vec<f64> = xs
.iter()
.map(|&x| (std::f64::consts::PI * x).sin())
.collect();
let f: Vec<f64> = a.mul_vec(&u);
let x = conjugate_gradient(&a, &f, None, 1e-12, 1000);
for i in 1..g.n() - 1 {
assert_abs_diff_eq!(x[i], u[i], epsilon = 1e-6);
}
}
}