Skip to main content

tpt_sci_ode/
sparse.rs

1//! In-crate sparse linear algebra for the implicit ODE solvers.
2//!
3//! A compressed-sparse-row ([`CsrMatrix`]) type plus a sparse LU decomposition
4//! with partial pivoting ([`CsrMatrix::sparse_solve`]). This complements the
5//! dense `DMat` (in the `linalg` module): for systems with at least 64 states
6//! (the `SPARSE_LU_MIN_N` threshold), the implicit SDIRK and BDF solvers build
7//! their Newton matrices in CSR storage and factor them with the sparse LU
8//! below, so the dense `n × n` matrix is never formed.
9//!
10//! The factorisation is left-looking (Gilbert–Peierls): each column is solved
11//! against the already-computed `L` restricted to its reachable pattern, so the
12//! work and fill follow the sparsity of the matrix rather than `n²`. Pivoting is
13//! partial (largest magnitude in the column among the not-yet-pivoted rows).
14//! No fill-reducing column ordering is applied, so heavy fill is possible for
15//! matrices with unfavourable structure.
16
17use crate::error::OdeError;
18use crate::linalg::{NEWTON_TOL, Tol};
19
20/// Minimum system size for the implicit solvers to route their Newton linear
21/// solves through the sparse CSR/LU path instead of the dense `DMat` path.
22/// Below this threshold the dense factorisation is faster (no CSR build
23/// overhead).
24pub(crate) const SPARSE_LU_MIN_N: usize = 64;
25
26/// Sentinel for "no value" in index arrays.
27const NONE: usize = usize::MAX;
28
29/// Compressed-sparse-row matrix.
30///
31/// Stores only the non-zero entries `data` together with their column indices
32/// `indices` (per row, in ascending column order) and the CSR row-pointer
33/// `indptr` (length `nrows + 1`). A zero entry must not be stored.
34#[derive(Clone)]
35pub struct CsrMatrix {
36    nrows: usize,
37    ncols: usize,
38    /// Row pointers: `indptr[r] .. indptr[r+1]` indexes the slice of row `r`'s
39    /// non-zeros in `data` / `indices`.
40    indptr: Vec<usize>,
41    /// Column index of each stored entry (ascending within a row).
42    indices: Vec<usize>,
43    /// Value of each stored entry.
44    data: Vec<f64>,
45}
46
47impl CsrMatrix {
48    /// Number of rows.
49    #[must_use]
50    pub fn nrows(&self) -> usize {
51        self.nrows
52    }
53
54    /// Number of columns.
55    #[must_use]
56    pub fn ncols(&self) -> usize {
57        self.ncols
58    }
59
60    /// Build a CSR matrix from a dense row-major slice (row length `ncols`).
61    /// Zero entries are dropped.
62    #[must_use]
63    pub fn from_dense(dense: &[f64], nrows: usize, ncols: usize) -> Self {
64        debug_assert_eq!(dense.len(), nrows * ncols);
65        let mut indptr = vec![0usize; nrows + 1];
66        let mut indices = Vec::new();
67        let mut data = Vec::new();
68        for r in 0..nrows {
69            let row = &dense[r * ncols..(r + 1) * ncols];
70            for (c, &v) in row.iter().enumerate() {
71                if v != 0.0 {
72                    indices.push(c);
73                    data.push(v);
74                }
75            }
76            indptr[r + 1] = indices.len();
77        }
78        CsrMatrix {
79            nrows,
80            ncols,
81            indptr,
82            indices,
83            data,
84        }
85    }
86
87    /// Number of explicitly stored non-zeros.
88    #[must_use]
89    pub fn nnz(&self) -> usize {
90        self.data.len()
91    }
92
93    /// Look up the stored value at `(r, c)`, or `0.0` if not present.
94    #[must_use]
95    pub fn get(&self, r: usize, c: usize) -> f64 {
96        let start = self.indptr[r];
97        let end = self.indptr[r + 1];
98        match self.indices[start..end].binary_search(&c) {
99            Ok(pos) => self.data[start + pos],
100            Err(_) => 0.0,
101        }
102    }
103
104    /// `y = A x`.
105    ///
106    /// # Panics
107    ///
108    /// Panics if `x.len() != self.ncols()`.
109    #[must_use]
110    pub fn mat_vec(&self, x: &[f64]) -> Vec<f64> {
111        assert_eq!(x.len(), self.ncols, "vector length must match ncols");
112        let mut y = vec![0.0; self.nrows];
113        for (r, yr) in y.iter_mut().enumerate() {
114            let mut s = 0.0;
115            for k in self.indptr[r]..self.indptr[r + 1] {
116                s += self.data[k] * x[self.indices[k]];
117            }
118            *yr = s;
119        }
120        y
121    }
122
123    /// Build the Newton matrix `A = I − diag·self` directly in CSR storage,
124    /// merging the unit diagonal with the scaled Jacobian entries per row
125    /// (both in ascending column order) without ever densifying.
126    #[must_use]
127    pub fn scaled_identity_minus_scaled(&self, diag: f64) -> CsrMatrix {
128        debug_assert_eq!(self.ncols, self.nrows);
129        let n = self.nrows;
130        let mut indptr = vec![0usize; n + 1];
131        let mut indices = Vec::new();
132        let mut data = Vec::new();
133        for r in 0..n {
134            let start = self.indptr[r];
135            let end = self.indptr[r + 1];
136            let mut k = start;
137            // Merge the unit diagonal with the scaled Jacobian row (both in
138            // ascending column order).
139            while k < end && self.indices[k] < r {
140                indices.push(self.indices[k]);
141                data.push(-diag * self.data[k]);
142                k += 1;
143            }
144            if k < end && self.indices[k] == r {
145                indices.push(r);
146                data.push(1.0 - diag * self.data[k]);
147                k += 1;
148            } else {
149                indices.push(r);
150                data.push(1.0);
151            }
152            while k < end {
153                indices.push(self.indices[k]);
154                data.push(-diag * self.data[k]);
155                k += 1;
156            }
157            indptr[r + 1] = indices.len();
158        }
159        CsrMatrix {
160            nrows: n,
161            ncols: n,
162            indptr,
163            indices,
164            data,
165        }
166    }
167
168    /// Convert to a dense row-major `Vec<f64>` (for testing / verification).
169    #[cfg(test)]
170    pub fn to_dense(&self) -> Vec<f64> {
171        let mut d = vec![0.0; self.nrows * self.ncols];
172        for r in 0..self.nrows {
173            for k in self.indptr[r]..self.indptr[r + 1] {
174                d[r * self.ncols + self.indices[k]] = self.data[k];
175            }
176        }
177        d
178    }
179
180    /// Build the full Jacobian `J = df/dy` at `(t, y)` via forward finite
181    /// differences, returned as a `CsrMatrix`. `f0` must be `f(t, y)` and `cols`
182    /// is the set of columns to perturb (a sparsity pattern, or `None` for the
183    /// full dense pattern). When `cols` is `None` every column is finite-
184    /// differenced, matching the dense `linalg::jacobian` helper but in
185    /// compressed storage (exact-zero entries are dropped).
186    ///
187    /// # Errors
188    ///
189    /// Propagates any error returned by the RHS `f`.
190    pub fn jacobian<F>(
191        f: F,
192        t: f64,
193        y: &[f64],
194        f0: &[f64],
195        cols: Option<&[usize]>,
196    ) -> Result<CsrMatrix, OdeError>
197    where
198        F: Fn(f64, &[f64], &mut [f64]) -> Result<(), OdeError>,
199    {
200        let n = y.len();
201        let sqrt_eps = f64::sqrt(f64::EPSILON);
202        let perturb: Vec<usize> = match cols {
203            Some(c) => c.to_vec(),
204            None => (0..n).collect(),
205        };
206        // Collect COO triplets (row, col, val). Perturbing column `j` yields the
207        // whole of Jacobian column `j`: `val = (f_row(y+dy·e_j) - f_row(y))/dy`.
208        let mut rows = Vec::new();
209        let mut cols = Vec::new();
210        let mut vals = Vec::new();
211        for &col in &perturb {
212            let dy = sqrt_eps * y[col].abs().max(1.0);
213            let mut yp = y.to_vec();
214            yp[col] += dy;
215            let mut fp = vec![0.0; n];
216            f(t, &yp, &mut fp)?;
217            let inv = 1.0 / dy;
218            for row in 0..n {
219                let val = (fp[row] - f0[row]) * inv;
220                if val != 0.0 {
221                    rows.push(row);
222                    cols.push(col);
223                    vals.push(val);
224                }
225            }
226        }
227        // Sort triplets by (row, col) so each row's entries are in ascending
228        // column order, then compress into CSR.
229        let mut order: Vec<usize> = (0..rows.len()).collect();
230        order.sort_by(|&a, &b| (rows[a], cols[a]).cmp(&(rows[b], cols[b])));
231        let mut indptr = vec![0usize; n + 1];
232        for &k in &order {
233            indptr[rows[k] + 1] += 1;
234        }
235        for r in 0..n {
236            indptr[r + 1] += indptr[r];
237        }
238        let mut indices = Vec::with_capacity(vals.len());
239        let mut data = Vec::with_capacity(vals.len());
240        for &k in &order {
241            indices.push(cols[k]);
242            data.push(vals[k]);
243        }
244        Ok(CsrMatrix {
245            nrows: n,
246            ncols: n,
247            indptr,
248            indices,
249            data,
250        })
251    }
252
253    /// Solve `A x = b` via sparse LU with partial pivoting.
254    ///
255    /// Returns `None` if the matrix is (numerically) singular or the dimensions
256    /// mismatch.
257    #[must_use]
258    pub fn sparse_solve(&self, b: &[f64]) -> Option<Vec<f64>> {
259        let n = self.nrows;
260        if self.ncols != n || b.len() != n {
261            return None;
262        }
263        let lu = SparseLu::factor(self)?;
264        Some(lu.solve(b))
265    }
266}
267
268/// Sparse LU factors of `P·A = L·U`, stored by column.
269///
270/// Pivot step `k` eliminates original row `prow[k]`. Column `k` of `L` holds the
271/// multipliers for the rows not yet pivoted at that step, and column `k` of `U`
272/// holds the entries above the diagonal, indexed by pivot step.
273struct SparseLu {
274    n: usize,
275    /// `prow[k]`: original row chosen as the pivot at step `k`.
276    prow: Vec<usize>,
277    /// Column `k` of `L` below the diagonal: `(original row, multiplier)`.
278    lcols: Vec<Vec<(usize, f64)>>,
279    /// Column `k` of `U` above the diagonal: `(step i < k, value)`.
280    ucols: Vec<Vec<(usize, f64)>>,
281    /// Diagonal of `U`.
282    udiag: Vec<f64>,
283}
284
285impl SparseLu {
286    /// Left-looking (Gilbert–Peierls) factorisation with partial pivoting.
287    /// Returns `None` if a column has no usable pivot.
288    fn factor(a: &CsrMatrix) -> Option<SparseLu> {
289        let n = a.nrows;
290        let nnz = a.data.len();
291
292        // Column-compressed copy of A, so each column can be scattered directly.
293        let mut col_ptr = vec![0usize; n + 1];
294        for &c in &a.indices {
295            col_ptr[c + 1] += 1;
296        }
297        for c in 0..n {
298            col_ptr[c + 1] += col_ptr[c];
299        }
300        let mut fill = col_ptr.clone();
301        let mut rows_csc = vec![0usize; nnz];
302        let mut vals_csc = vec![0.0; nnz];
303        for r in 0..n {
304            for k in a.indptr[r]..a.indptr[r + 1] {
305                let c = a.indices[k];
306                rows_csc[fill[c]] = r;
307                vals_csc[fill[c]] = a.data[k];
308                fill[c] += 1;
309            }
310        }
311
312        let scale = a.data.iter().fold(0.0_f64, |m, v| m.max(v.abs()));
313        let mut pinv = vec![NONE; n]; // original row -> pivot step
314        let mut prow = vec![NONE; n]; // pivot step -> original row
315        let mut lcols: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
316        let mut ucols: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
317        let mut udiag = vec![0.0; n];
318        let mut x = vec![0.0; n]; // dense work vector, indexed by original row
319        let mut mark = vec![NONE; n]; // DFS visit stamp, per column
320        let mut pattern: Vec<usize> = Vec::new(); // reached rows, in postorder
321        let mut stack: Vec<(usize, usize)> = Vec::new();
322
323        for k in 0..n {
324            pattern.clear();
325            for p in col_ptr[k]..col_ptr[k + 1] {
326                x[rows_csc[p]] = vals_csc[p];
327            }
328
329            // Reach of the column's nonzero rows through the pivoted part of L.
330            for &r0 in &rows_csc[col_ptr[k]..col_ptr[k + 1]] {
331                if mark[r0] == k {
332                    continue;
333                }
334                mark[r0] = k;
335                stack.push((r0, 0));
336                while let Some(top) = stack.last_mut() {
337                    let r = top.0;
338                    let children: &[(usize, f64)] = if pinv[r] == NONE {
339                        &[]
340                    } else {
341                        &lcols[pinv[r]]
342                    };
343                    if top.1 < children.len() {
344                        let child = children[top.1].0;
345                        top.1 += 1;
346                        if mark[child] != k {
347                            mark[child] = k;
348                            stack.push((child, 0));
349                        }
350                    } else {
351                        pattern.push(r);
352                        stack.pop();
353                    }
354                }
355            }
356
357            // Sparse triangular solve: apply the earlier pivots in topological
358            // order (reverse postorder), so each row is final before it is used.
359            for &r in pattern.iter().rev() {
360                let j = pinv[r];
361                if j == NONE {
362                    continue;
363                }
364                let xr = x[r];
365                if xr != 0.0 {
366                    for &(i, l) in &lcols[j] {
367                        x[i] -= l * xr;
368                    }
369                }
370            }
371
372            // Partial pivot among the rows not yet pivoted.
373            let mut piv_row = NONE;
374            let mut piv_mag = 0.0_f64;
375            for &r in &pattern {
376                if pinv[r] == NONE && x[r].abs() > piv_mag {
377                    piv_mag = x[r].abs();
378                    piv_row = r;
379                }
380            }
381            if piv_row == NONE || piv_mag <= 1e-14 * scale {
382                return None;
383            }
384
385            let pivot = x[piv_row];
386            udiag[k] = pivot;
387            prow[k] = piv_row;
388            pinv[piv_row] = k;
389            for &r in &pattern {
390                if r == piv_row || x[r] == 0.0 {
391                    continue;
392                }
393                if pinv[r] == NONE {
394                    lcols[k].push((r, x[r] / pivot));
395                } else {
396                    ucols[k].push((pinv[r], x[r]));
397                }
398            }
399            for &r in &pattern {
400                x[r] = 0.0;
401            }
402        }
403
404        Some(SparseLu {
405            n,
406            prow,
407            lcols,
408            ucols,
409            udiag,
410        })
411    }
412
413    /// Solve `A x = b` using the stored factors.
414    fn solve(&self, b: &[f64]) -> Vec<f64> {
415        let n = self.n;
416        // Forward substitution with L, in original row indices.
417        let mut y = b.to_vec();
418        for k in 0..n {
419            let yk = y[self.prow[k]];
420            if yk != 0.0 {
421                for &(i, l) in &self.lcols[k] {
422                    y[i] -= l * yk;
423                }
424            }
425        }
426        // Back substitution with U, column-oriented, in pivot-step indices.
427        let mut z: Vec<f64> = (0..n).map(|k| y[self.prow[k]]).collect();
428        let mut x = vec![0.0; n];
429        for k in (0..n).rev() {
430            x[k] = z[k] / self.udiag[k];
431            for &(i, u) in &self.ucols[k] {
432                z[i] -= u * x[k];
433            }
434        }
435        x
436    }
437}
438
439/// Solve one SDIRK stage `k = f(t_stage, y_base + diag·k)` with the Newton
440/// linear solves routed through the sparse CSR/LU path. Called by
441/// [`sdirk_stage`](crate::linalg::sdirk_stage) whenever the system has at
442/// least [`SPARSE_LU_MIN_N`] states, so the finite-difference Jacobian is
443/// built directly in compressed storage and never densified.
444pub(crate) fn sdirk_stage_sparse(
445    f: &dyn crate::RhsCallable,
446    t_stage: f64,
447    y_base: &[f64],
448    diag: f64,
449    k_guess: &[f64],
450    tol: Tol,
451    jac: Option<&JacobianPattern>,
452) -> Result<Vec<f64>, OdeError> {
453    let n = y_base.len();
454    let mut k = k_guess.to_vec();
455    let mut corr = f64::INFINITY;
456    for _iter in 0..50 {
457        let y_stage: Vec<f64> = y_base.iter().zip(&k).map(|(b, kk)| b + diag * kk).collect();
458        let mut fk = vec![0.0; n];
459        f.call(t_stage, &y_stage, &mut fk)?;
460        let r: Vec<f64> = k.iter().zip(&fk).map(|(kk, fv)| kk - fv).collect();
461        let rnorm = r.iter().map(|x| x * x).sum::<f64>().sqrt();
462        let jmat = match jac {
463            Some(pattern) => CsrMatrix::jacobian_colored(
464                |t, y, dydt| f.call(t, y, dydt),
465                t_stage,
466                &y_stage,
467                &fk,
468                pattern,
469            )?,
470            None => CsrMatrix::jacobian(
471                |t, y, dydt| f.call(t, y, dydt),
472                t_stage,
473                &y_stage,
474                &fk,
475                None,
476            )?,
477        };
478        // Newton matrix A = I - diag·J (sparse, since J is sparse).
479        let a = jmat.scaled_identity_minus_scaled(diag);
480        let delta = a.sparse_solve(&r).ok_or(OdeError::Newton {
481            t: t_stage,
482            residual: rnorm,
483        })?;
484        for (ki, di) in k.iter_mut().zip(&delta) {
485            *ki -= di;
486        }
487        // The stage variable is a derivative; its effect on the state is diag·Δk.
488        let state_step: Vec<f64> = delta.iter().map(|d| diag * d).collect();
489        corr = tol.wrms(&state_step, &y_stage);
490        if corr < NEWTON_TOL {
491            return Ok(k);
492        }
493    }
494    // Budget exhausted without convergence: report failure so the driver shrinks
495    // the step instead of accepting an unconverged stage.
496    Err(OdeError::Newton {
497        t: t_stage,
498        residual: corr,
499    })
500}
501
502/// Structural sparsity of a Jacobian: for each row, the columns that may be
503/// nonzero.
504///
505/// Supplying the pattern lets [`CsrMatrix::jacobian_colored`] differentiate
506/// several structurally independent columns with a single RHS call, so the cost
507/// of a Jacobian drops from `n` evaluations to the number of colors.
508#[derive(Debug, Clone, PartialEq, Eq)]
509pub struct JacobianPattern {
510    n: usize,
511    /// `rows[i]` is the sorted list of columns that can be nonzero in row `i`.
512    rows: Vec<Vec<usize>>,
513}
514
515impl JacobianPattern {
516    /// Build a pattern from per-row column lists. Each list is sorted and
517    /// deduplicated.
518    ///
519    /// # Errors
520    ///
521    /// Returns [`OdeError::Invalid`] if any column index is out of range for
522    /// `rows.len()` states.
523    pub fn new(mut rows: Vec<Vec<usize>>) -> Result<Self, OdeError> {
524        let n = rows.len();
525        for row in &mut rows {
526            row.sort_unstable();
527            row.dedup();
528            if let Some(&bad) = row.iter().find(|&&c| c >= n) {
529                return Err(OdeError::invalid(format!(
530                    "pattern column {bad} out of range for {n} states"
531                )));
532            }
533        }
534        Ok(Self { n, rows })
535    }
536
537    /// The fully dense pattern (every entry may be nonzero) for `n` states.
538    #[must_use]
539    pub fn dense(n: usize) -> Self {
540        Self {
541            n,
542            rows: (0..n).map(|_| (0..n).collect()).collect(),
543        }
544    }
545
546    /// Detect the pattern by probing `f`: column `j` is perturbed and every row
547    /// whose value changes gets an entry. Costs `n + 1` RHS evaluations.
548    ///
549    /// Detection is exact for entries whose dependence is visible at `y`. An
550    /// entry that is zero at this particular point (for example the product
551    /// `x·y` when `x = 0`) is missed, so probe at a generic state when in doubt.
552    ///
553    /// # Errors
554    ///
555    /// Propagates any error returned by the RHS `f`.
556    pub fn detect<F>(f: F, t: f64, y: &[f64]) -> Result<Self, OdeError>
557    where
558        F: Fn(f64, &[f64], &mut [f64]) -> Result<(), OdeError>,
559    {
560        let n = y.len();
561        let mut f0 = vec![0.0; n];
562        f(t, y, &mut f0)?;
563        let mut rows: Vec<Vec<usize>> = vec![Vec::new(); n];
564        let sqrt_eps = f64::sqrt(f64::EPSILON);
565        for col in 0..n {
566            let dy = sqrt_eps * y[col].abs().max(1.0);
567            let mut yp = y.to_vec();
568            yp[col] += dy;
569            let mut fp = vec![0.0; n];
570            f(t, &yp, &mut fp)?;
571            for (row, (a, b)) in fp.iter().zip(&f0).enumerate() {
572                if a != b {
573                    rows[row].push(col);
574                }
575            }
576        }
577        Self::new(rows)
578    }
579
580    /// Number of states.
581    #[must_use]
582    pub fn n(&self) -> usize {
583        self.n
584    }
585
586    /// Number of structurally nonzero entries.
587    #[must_use]
588    pub fn nnz(&self) -> usize {
589        self.rows.iter().map(Vec::len).sum()
590    }
591
592    /// Columns that may be nonzero in row `i`.
593    #[must_use]
594    pub fn row(&self, i: usize) -> &[usize] {
595        &self.rows[i]
596    }
597
598    /// Greedy column coloring: two columns get different colors whenever they
599    /// share a row, so each color class can be perturbed together without the
600    /// contributions colliding in any row.
601    ///
602    /// Returns `(colors, n_colors)`, where `colors[j]` is column `j`'s color.
603    #[must_use]
604    pub fn column_coloring(&self) -> (Vec<usize>, usize) {
605        let mut conflicts: Vec<Vec<usize>> = vec![Vec::new(); self.n];
606        for row in &self.rows {
607            for &a in row {
608                for &b in row {
609                    if a != b {
610                        conflicts[a].push(b);
611                    }
612                }
613            }
614        }
615        let mut colors = vec![usize::MAX; self.n];
616        let mut n_colors = 0usize;
617        for j in 0..self.n {
618            let mut used = vec![false; n_colors + 1];
619            for &k in &conflicts[j] {
620                if colors[k] != usize::MAX {
621                    used[colors[k]] = true;
622                }
623            }
624            let c = used.iter().position(|&u| !u).unwrap_or(n_colors);
625            colors[j] = c;
626            n_colors = n_colors.max(c + 1);
627        }
628        (colors, n_colors)
629    }
630}
631
632impl CsrMatrix {
633    /// Jacobian `J = df/dy` by forward differences, with one RHS call per color
634    /// instead of one per column.
635    ///
636    /// Columns are grouped with [`JacobianPattern::column_coloring`]. All columns
637    /// of a color are perturbed together, and each row's entry is recovered from
638    /// the single column of that color that the row's pattern contains. The
639    /// result equals [`CsrMatrix::jacobian`] when `pattern` covers the true
640    /// structure.
641    ///
642    /// # Errors
643    ///
644    /// Propagates any error returned by the RHS `f`, or returns
645    /// [`OdeError::Invalid`] if the pattern size does not match `y`.
646    pub fn jacobian_colored<F>(
647        f: F,
648        t: f64,
649        y: &[f64],
650        f0: &[f64],
651        pattern: &JacobianPattern,
652    ) -> Result<CsrMatrix, OdeError>
653    where
654        F: Fn(f64, &[f64], &mut [f64]) -> Result<(), OdeError>,
655    {
656        let n = y.len();
657        if pattern.n() != n {
658            return Err(OdeError::invalid(format!(
659                "pattern is for {} states, state has {n}",
660                pattern.n()
661            )));
662        }
663        let sqrt_eps = f64::sqrt(f64::EPSILON);
664        let (colors, n_colors) = pattern.column_coloring();
665        let mut members: Vec<Vec<usize>> = vec![Vec::new(); n_colors];
666        for (j, &c) in colors.iter().enumerate() {
667            members[c].push(j);
668        }
669        let mut dy = vec![0.0; n];
670        let (mut rows, mut cols, mut vals) = (Vec::new(), Vec::new(), Vec::new());
671        for (color, group) in members.iter().enumerate() {
672            let mut yp = y.to_vec();
673            for &j in group {
674                dy[j] = sqrt_eps * y[j].abs().max(1.0);
675                yp[j] += dy[j];
676            }
677            let mut fp = vec![0.0; n];
678            f(t, &yp, &mut fp)?;
679            for row in 0..n {
680                // Conflict-freeness guarantees at most one column of this color
681                // in each row's pattern.
682                let hit = pattern
683                    .row(row)
684                    .iter()
685                    .copied()
686                    .find(|&j| colors[j] == color);
687                if let Some(j) = hit {
688                    let val = (fp[row] - f0[row]) / dy[j];
689                    if val != 0.0 {
690                        rows.push(row);
691                        cols.push(j);
692                        vals.push(val);
693                    }
694                }
695            }
696            for &j in group {
697                dy[j] = 0.0;
698            }
699        }
700        Ok(CsrMatrix::from_triplets(n, rows, cols, vals))
701    }
702
703    /// Compress `(row, col, value)` triplets into CSR, with each row's entries in
704    /// ascending column order.
705    fn from_triplets(n: usize, rows: Vec<usize>, cols: Vec<usize>, vals: Vec<f64>) -> CsrMatrix {
706        let mut order: Vec<usize> = (0..rows.len()).collect();
707        order.sort_by(|&a, &b| (rows[a], cols[a]).cmp(&(rows[b], cols[b])));
708        let mut indptr = vec![0usize; n + 1];
709        for &k in &order {
710            indptr[rows[k] + 1] += 1;
711        }
712        for r in 0..n {
713            indptr[r + 1] += indptr[r];
714        }
715        let mut indices = Vec::with_capacity(vals.len());
716        let mut data = Vec::with_capacity(vals.len());
717        for &k in &order {
718            indices.push(cols[k]);
719            data.push(vals[k]);
720        }
721        CsrMatrix {
722            nrows: n,
723            ncols: n,
724            indptr,
725            indices,
726            data,
727        }
728    }
729}
730
731#[cfg(test)]
732mod tests {
733    use super::*;
734
735    #[test]
736    fn csr_mat_vec_matches_dense() {
737        // A = [[2, 0, 1], [0, 3, 0], [1, 0, 4]]  (sparse, diagonally dominant)
738        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);
739        let y = a.mat_vec(&[1.0, 2.0, 3.0]);
740        assert!((y[0] - 5.0).abs() < 1e-12);
741        assert!((y[1] - 6.0).abs() < 1e-12);
742        assert!((y[2] - 13.0).abs() < 1e-12);
743    }
744
745    #[test]
746    fn sparse_solve_matches_dense_solve() {
747        // Same matrix as the dense LU test in linalg.rs.
748        let dense = [2.0, 1.0, 1.0, 1.0, 3.0, 2.0, 1.0, 0.0, 1.0];
749        let a = CsrMatrix::from_dense(&dense, 3, 3);
750        let b = [4.0, 6.0, 2.0];
751        let x = a.sparse_solve(&b).expect("non-singular");
752        assert!((x[0] - 1.0).abs() < 1e-12);
753        assert!((x[1] - 1.0).abs() < 1e-12);
754        assert!((x[2] - 1.0).abs() < 1e-12);
755    }
756
757    #[test]
758    fn sparse_solve_pivots_on_singular_offdiag() {
759        // [0 1; 1 0] — pivot required at k=0.
760        let a = CsrMatrix::from_dense(&[0.0, 1.0, 1.0, 0.0], 2, 2);
761        let x = a
762            .sparse_solve(&[3.0, 4.0])
763            .expect("non-singular after pivot");
764        assert!((x[0] - 4.0).abs() < 1e-12);
765        assert!((x[1] - 3.0).abs() < 1e-12);
766    }
767
768    #[test]
769    fn sparse_solve_detects_singular() {
770        let a = CsrMatrix::from_dense(&[1.0, 1.0, 2.0, 2.0], 2, 2);
771        assert!(a.sparse_solve(&[1.0, 1.0]).is_none());
772        // An all-zero column has no pivot.
773        let z = CsrMatrix::from_dense(&[1.0, 0.0, 2.0, 0.0], 2, 2);
774        assert!(z.sparse_solve(&[1.0, 1.0]).is_none());
775    }
776
777    #[test]
778    fn sparse_lu_matches_dense_on_banded_system_with_fill() {
779        // A banded, non-symmetric system with a few long-range entries. The
780        // long-range entries force fill and off-diagonal pivoting.
781        const N: usize = 150;
782        let mut dense = vec![0.0; N * N];
783        for i in 0..N {
784            dense[i * N + i] = 4.0 + (i % 7) as f64 * 0.25;
785            for d in 1..=3usize {
786                if i + d < N {
787                    dense[i * N + i + d] = -1.0 + 0.1 * d as f64;
788                }
789                if i >= d {
790                    dense[i * N + i - d] = 0.7 - 0.2 * d as f64;
791                }
792            }
793        }
794        dense[3 * N + 140] = 0.9;
795        dense[140 * N + 3] = -1.1;
796        dense[77 * N + 2] = 2.5; // large off-diagonal, pivoting needed
797        let a = CsrMatrix::from_dense(&dense, N, N);
798        let b: Vec<f64> = (0..N).map(|i| (i as f64 * 0.37).sin() + 0.5).collect();
799
800        let x = a.sparse_solve(&b).expect("non-singular");
801        let mut dm = crate::linalg::DMat::new(N, N);
802        dm.data.copy_from_slice(&dense);
803        let xd = dm.solve(&b).expect("non-singular");
804        for (i, (xs, xdv)) in x.iter().zip(&xd).enumerate() {
805            assert!((xs - xdv).abs() < 1e-9, "component {i}: {xs} vs {xdv}");
806        }
807        // Residual check, independent of the dense oracle.
808        let ax = a.mat_vec(&x);
809        for (axi, bi) in ax.iter().zip(&b) {
810            assert!((axi - bi).abs() < 1e-9);
811        }
812    }
813
814    #[test]
815    fn jacobian_csr_of_linear_system() {
816        let a = CsrMatrix::from_dense(&[0.0, 1.0, -2.0, -3.0], 2, 2);
817        let dense_j = a.to_dense();
818        let f = move |_t: f64, y: &[f64], dydt: &mut [f64]| {
819            let out = a.mat_vec(y);
820            dydt[0] = out[0];
821            dydt[1] = out[1];
822            Ok(())
823        };
824        let y = [0.7, -1.3];
825        let mut f0 = [0.0; 2];
826        f(0.0, &y, &mut f0).unwrap();
827        let j = CsrMatrix::jacobian(&f, 0.0, &y, &f0, None).unwrap();
828        assert!((j.get(0, 0) - 0.0).abs() < 1e-8);
829        assert!((j.get(0, 1) - 1.0).abs() < 1e-8);
830        assert!((j.get(1, 0) - (-2.0)).abs() < 1e-8);
831        assert!((j.get(1, 1) - (-3.0)).abs() < 1e-8);
832        // The CSR Newton matrix of (I - 0.1 J) must match the dense DMat path.
833        let jac = CsrMatrix::from_dense(&dense_j, 2, 2);
834        let csr = jac.scaled_identity_minus_scaled(0.1);
835        let r = [1.5, -2.5];
836        let xs = csr.sparse_solve(&r).unwrap();
837        // Dense oracle: A = I - 0.1 J.
838        let mut dense_a = crate::linalg::DMat::identity(2);
839        for i in 0..2 {
840            for jj in 0..2 {
841                dense_a.set(i, jj, dense_a.get(i, jj) - 0.1 * dense_j[i * 2 + jj]);
842            }
843        }
844        let xd = dense_a.solve(&r).unwrap();
845        assert!((xs[0] - xd[0]).abs() < 1e-10);
846        assert!((xs[1] - xd[1]).abs() < 1e-10);
847    }
848
849    #[test]
850    fn bdf_sparse_path_solves_large_decoupled_system() {
851        // n = 80 ≥ SPARSE_LU_MIN_N: `step_bdf` routes its Newton solves
852        // through the sparse CSR/LU path. Decoupled decays have the closed
853        // form y_i(t) = exp(-(i+1)·t).
854        const N: usize = 80;
855        let prob = crate::OdeProblem::new(
856            |_t, y, dydt| {
857                for (i, yi) in y.iter().enumerate() {
858                    dydt[i] = -((i + 1) as f64) * yi;
859                }
860            },
861            vec![1.0; N],
862            0.0,
863        )
864        .unwrap();
865        let t = 0.5;
866        let y = prob.solve(crate::Method::Bdf, t).unwrap();
867        for (i, yi) in y.iter().enumerate() {
868            let expected = (-((i + 1) as f64) * t).exp();
869            assert!(
870                (yi - expected).abs() < 1e-6,
871                "component {i}: {yi} vs {expected}"
872            );
873        }
874    }
875
876    #[test]
877    fn scaled_identity_handles_missing_diagonal() {
878        // J with a structural zero on the diagonal: A = I - diag·J must still
879        // carry the unit diagonal entry there.
880        let j = CsrMatrix::from_dense(&[0.0, 2.0, 0.0, 0.0], 2, 2);
881        let a = j.scaled_identity_minus_scaled(0.5);
882        assert!((a.get(0, 0) - 1.0).abs() < 1e-14);
883        assert!((a.get(0, 1) - (-1.0)).abs() < 1e-14);
884        assert!((a.get(1, 0) - 0.0).abs() < 1e-14);
885        assert!((a.get(1, 1) - 1.0).abs() < 1e-14);
886        let x = a.sparse_solve(&[1.0, 2.0]).unwrap();
887        // x0 - x1 = 1, x1 = 2  ->  x = [3, 2].
888        assert!((x[0] - 3.0).abs() < 1e-12);
889        assert!((x[1] - 2.0).abs() < 1e-12);
890    }
891
892    #[test]
893    fn sparse_sdirk_stage_matches_dense_oracle_on_tridiagonal_system() {
894        // f(y) = A y with a tridiagonal A (n = 80 ≥ SPARSE_LU_MIN_N): the
895        // stage equation k = A(y + diag·k) has the closed form
896        // k = (I - diag·A)⁻¹ A y, computable with the dense DMat oracle.
897        const N: usize = 80;
898        const TOL: Tol = Tol {
899            rtol: 1e-6,
900            atol: 1e-6,
901        };
902        let mut dense = vec![0.0; N * N];
903        for i in 0..N {
904            dense[i * N + i] = -2.0;
905            if i > 0 {
906                dense[i * N + i - 1] = 1.0;
907            }
908            if i + 1 < N {
909                dense[i * N + i + 1] = 1.0;
910            }
911        }
912        let a = CsrMatrix::from_dense(&dense, N, N);
913        let f = move |_t: f64, y: &[f64], dydt: &mut [f64]| {
914            let out = a.mat_vec(y);
915            dydt.copy_from_slice(&out);
916        };
917        let y: Vec<f64> = (0..N).map(|i| 0.1 * (i as f64).sin() + 0.2).collect();
918        let diag = 0.05;
919        let k = sdirk_stage_sparse(&f, 0.0, &y, diag, &vec![0.0; N], TOL, None).unwrap();
920        // Dense oracle.
921        let mut am = crate::linalg::DMat::new(N, N);
922        for i in 0..N {
923            for jj in 0..N {
924                am.set(i, jj, dense[i * N + jj]);
925            }
926        }
927        let ay = am.mat_vec(&y);
928        // (I - diag·A) as a fresh dense matrix.
929        let mut m = crate::linalg::DMat::new(N, N);
930        for i in 0..N {
931            for jj in 0..N {
932                let v = if i == jj { 1.0 } else { 0.0 } - diag * dense[i * N + jj];
933                m.set(i, jj, v);
934            }
935        }
936        let expected = m.solve(&ay).unwrap();
937        for (i, (kv, ev)) in k.iter().zip(&expected).enumerate() {
938            assert!((kv - ev).abs() < 1e-8, "component {i}: {kv} vs {ev}");
939        }
940    }
941}