1use crate::error::OdeError;
18use crate::linalg::{NEWTON_TOL, Tol};
19
20pub(crate) const SPARSE_LU_MIN_N: usize = 64;
25
26const NONE: usize = usize::MAX;
28
29#[derive(Clone)]
35pub struct CsrMatrix {
36 nrows: usize,
37 ncols: usize,
38 indptr: Vec<usize>,
41 indices: Vec<usize>,
43 data: Vec<f64>,
45}
46
47impl CsrMatrix {
48 #[must_use]
50 pub fn nrows(&self) -> usize {
51 self.nrows
52 }
53
54 #[must_use]
56 pub fn ncols(&self) -> usize {
57 self.ncols
58 }
59
60 #[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 #[must_use]
89 pub fn nnz(&self) -> usize {
90 self.data.len()
91 }
92
93 #[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 #[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 #[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 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 #[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 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 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 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 #[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
268struct SparseLu {
274 n: usize,
275 prow: Vec<usize>,
277 lcols: Vec<Vec<(usize, f64)>>,
279 ucols: Vec<Vec<(usize, f64)>>,
281 udiag: Vec<f64>,
283}
284
285impl SparseLu {
286 fn factor(a: &CsrMatrix) -> Option<SparseLu> {
289 let n = a.nrows;
290 let nnz = a.data.len();
291
292 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]; let mut prow = vec![NONE; n]; 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]; let mut mark = vec![NONE; n]; let mut pattern: Vec<usize> = Vec::new(); 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 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 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 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 fn solve(&self, b: &[f64]) -> Vec<f64> {
415 let n = self.n;
416 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 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
439pub(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 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 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 Err(OdeError::Newton {
497 t: t_stage,
498 residual: corr,
499 })
500}
501
502#[derive(Debug, Clone, PartialEq, Eq)]
509pub struct JacobianPattern {
510 n: usize,
511 rows: Vec<Vec<usize>>,
513}
514
515impl JacobianPattern {
516 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 #[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 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 #[must_use]
582 pub fn n(&self) -> usize {
583 self.n
584 }
585
586 #[must_use]
588 pub fn nnz(&self) -> usize {
589 self.rows.iter().map(Vec::len).sum()
590 }
591
592 #[must_use]
594 pub fn row(&self, i: usize) -> &[usize] {
595 &self.rows[i]
596 }
597
598 #[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 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 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 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 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 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 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 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 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; 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 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 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 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 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 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 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 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 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 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}