1#![no_std]
2#![forbid(unsafe_code)]
3extern crate alloc;
48
49#[cfg(feature = "alloc")]
50mod operator;
51#[cfg(feature = "alloc")]
52pub use operator::{
53 arnoldi, bicgstab_op, conjugate_gradient_op, gmres_op, lanczos, matrix_free, ArnoldiRitz,
54 LanczosEigenpairs, LinearOperator, MatrixFree, Which,
55};
56#[cfg(feature = "alloc")]
57mod ordering;
58#[cfg(feature = "alloc")]
59pub use ordering::{
60 minimum_degree_ordering, permute_symmetric, reverse_cuthill_mckee, FillOrdering,
61 ReorderedCholesky, ReorderedLu,
62};
63
64use alloc::vec::Vec;
65
66#[cfg(feature = "alloc")]
67use alloc::vec;
68#[cfg(feature = "alloc")]
69use tpt_math_linalg_dense::DVector;
70use tpt_math_numeric::Scalar;
71#[cfg(feature = "alloc")]
72use tpt_math_numeric::{SolveReport, SolveStatus};
73
74#[derive(Debug, Clone, PartialEq, Eq)]
76#[non_exhaustive]
77pub enum SparseError {
78 DimensionMismatch {
81 what: &'static str,
83 },
84 NotConverged {
87 iterations: usize,
89 },
90 Breakdown {
93 iterations: usize,
95 },
96}
97
98impl core::fmt::Display for SparseError {
99 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
100 match self {
101 SparseError::DimensionMismatch { what } => {
102 write!(f, "sparse matrix/vector dimension mismatch: {what}")
103 }
104 SparseError::NotConverged { iterations } => {
105 write!(
106 f,
107 "iterative solver did not converge in {iterations} iterations"
108 )
109 }
110 SparseError::Breakdown { iterations } => {
111 write!(f, "iterative solver broke down at iteration {iterations}")
112 }
113 }
114 }
115}
116
117impl core::error::Error for SparseError {}
118
119#[derive(Clone, Debug, PartialEq, Eq)]
131pub struct CooMatrix<T> {
132 nrows: usize,
133 ncols: usize,
134 rows: Vec<usize>,
135 cols: Vec<usize>,
136 vals: Vec<T>,
137}
138
139impl<T> CooMatrix<T> {
140 pub fn new(nrows: usize, ncols: usize) -> Self {
142 CooMatrix {
143 nrows,
144 ncols,
145 rows: Vec::new(),
146 cols: Vec::new(),
147 vals: Vec::new(),
148 }
149 }
150
151 pub fn nrows(&self) -> usize {
153 self.nrows
154 }
155
156 pub fn ncols(&self) -> usize {
158 self.ncols
159 }
160
161 pub fn nnz(&self) -> usize {
163 self.vals.len()
164 }
165
166 pub fn push(&mut self, row: usize, col: usize, val: T) {
168 self.rows.push(row);
169 self.cols.push(col);
170 self.vals.push(val);
171 }
172}
173
174impl<T: Scalar + Copy> CooMatrix<T> {
175 pub fn from_triplets(
177 nrows: usize,
178 ncols: usize,
179 rows: Vec<usize>,
180 cols: Vec<usize>,
181 vals: Vec<T>,
182 ) -> Self {
183 assert_eq!(rows.len(), cols.len());
184 assert_eq!(rows.len(), vals.len());
185 CooMatrix {
186 nrows,
187 ncols,
188 rows,
189 cols,
190 vals,
191 }
192 }
193
194 #[cfg(feature = "alloc")]
196 pub fn to_csr(&self) -> CsrMatrix<T> {
197 to_csr_impl(self.nrows, self.ncols, &self.rows, &self.cols, &self.vals)
198 }
199
200 #[cfg(feature = "alloc")]
202 pub fn to_csc(&self) -> CscMatrix<T> {
203 to_csc_impl(self.nrows, self.ncols, &self.rows, &self.cols, &self.vals)
204 }
205}
206
207#[derive(Clone, Debug, PartialEq, Eq)]
216pub struct CsrMatrix<T> {
217 nrows: usize,
218 ncols: usize,
219 row_ptr: Vec<usize>,
220 col_idx: Vec<u32>,
223 values: Vec<T>,
224}
225
226impl<T> CsrMatrix<T> {
227 pub fn nrows(&self) -> usize {
229 self.nrows
230 }
231
232 pub fn ncols(&self) -> usize {
234 self.ncols
235 }
236
237 pub fn nnz(&self) -> usize {
239 self.values.len()
240 }
241
242 pub fn iter(&self) -> impl Iterator<Item = (usize, usize, &T)> {
244 let nrows = self.nrows;
245 (0..nrows).flat_map(move |i| {
246 let start = self.row_ptr[i];
247 let end = self.row_ptr[i + 1];
248 (start..end).map(move |k| (i, self.col_idx[k] as usize, &self.values[k]))
249 })
250 }
251}
252
253impl<T: Scalar + Copy> CsrMatrix<T> {
254 #[cfg(feature = "alloc")]
256 pub fn transpose(&self) -> CscMatrix<T> {
257 let rows: Vec<usize> = self.iter().map(|(_, c, _)| c).collect();
259 let cols: Vec<usize> = self.iter().map(|(r, _, _)| r).collect();
260 let vals: Vec<T> = self.iter().map(|(_, _, v)| *v).collect();
261 to_csc_impl(self.ncols, self.nrows, &rows, &cols, &vals)
262 }
263}
264
265#[cfg(feature = "alloc")]
266impl<T: Scalar> CsrMatrix<T> {
267 pub fn matvec(&self, x: &DVector<T>) -> Result<DVector<T>, SparseError> {
273 if x.len() != self.ncols {
274 return Err(SparseError::DimensionMismatch {
275 what: "operands have incompatible dimensions",
276 });
277 }
278 let mut y = vec![T::zero(); self.nrows];
279 self.matvec_into(x.as_slice(), &mut y)?;
280 Ok(DVector::from_vec(y))
281 }
282
283 pub fn matvec_into(&self, x: &[T], y: &mut [T]) -> Result<(), SparseError> {
294 if x.len() != self.ncols || y.len() != self.nrows {
295 return Err(SparseError::DimensionMismatch {
296 what: "operands have incompatible dimensions",
297 });
298 }
299 for (i, yi) in y.iter_mut().enumerate() {
300 let mut s = T::zero();
301 for k in self.row_ptr[i]..self.row_ptr[i + 1] {
302 s = s + self.values[k] * x[self.col_idx[k] as usize];
303 }
304 *yi = s;
305 }
306 Ok(())
307 }
308}
309
310#[cfg(feature = "alloc")]
311impl<T: Scalar> core::ops::Mul<&DVector<T>> for &CsrMatrix<T> {
312 type Output = DVector<T>;
313 fn mul(self, rhs: &DVector<T>) -> DVector<T> {
317 self.matvec(rhs)
318 .unwrap_or_else(|_| panic!("CsrMatrix * DVector: dimension mismatch"))
319 }
320}
321
322#[derive(Clone, Debug, PartialEq, Eq)]
331pub struct CscMatrix<T> {
332 nrows: usize,
333 ncols: usize,
334 col_ptr: Vec<usize>,
335 row_idx: Vec<usize>,
336 values: Vec<T>,
337}
338
339impl<T> CscMatrix<T> {
340 pub fn nrows(&self) -> usize {
342 self.nrows
343 }
344
345 pub fn ncols(&self) -> usize {
347 self.ncols
348 }
349
350 pub fn nnz(&self) -> usize {
352 self.values.len()
353 }
354
355 pub fn iter(&self) -> impl Iterator<Item = (usize, usize, &T)> {
357 let ncols = self.ncols;
358 (0..ncols).flat_map(move |j| {
359 let start = self.col_ptr[j];
360 let end = self.col_ptr[j + 1];
361 (start..end).map(move |k| (self.row_idx[k], j, &self.values[k]))
362 })
363 }
364}
365
366impl<T: Scalar + Copy> CscMatrix<T> {
367 #[cfg(feature = "alloc")]
369 pub fn transpose(&self) -> CsrMatrix<T> {
370 let rows: Vec<usize> = self.iter().map(|(_, c, _)| c).collect();
372 let cols: Vec<usize> = self.iter().map(|(r, _, _)| r).collect();
373 let vals: Vec<T> = self.iter().map(|(_, _, v)| *v).collect();
374 to_csr_impl(self.ncols, self.nrows, &rows, &cols, &vals)
375 }
376}
377
378#[cfg(feature = "alloc")]
379impl<T: Scalar> CscMatrix<T> {
380 pub fn matvec(&self, x: &DVector<T>) -> Result<DVector<T>, SparseError> {
386 if x.len() != self.ncols {
387 return Err(SparseError::DimensionMismatch {
388 what: "operands have incompatible dimensions",
389 });
390 }
391 let nrows = self.nrows;
392 let mut y_data = vec![T::zero(); nrows];
393 for j in 0..self.ncols {
394 let start = self.col_ptr[j];
395 let end = self.col_ptr[j + 1];
396 let xj = x[j];
397 for k in start..end {
398 y_data[self.row_idx[k]] = y_data[self.row_idx[k]] + self.values[k] * xj;
399 }
400 }
401 Ok(DVector::from_vec(y_data))
402 }
403}
404
405#[cfg(feature = "alloc")]
412fn bucket_by<T: Copy>(
413 entries: &[(usize, usize, T)],
414 key: impl Fn(&(usize, usize, T)) -> usize,
415 nkeys: usize,
416) -> Vec<(usize, usize, T)> {
417 let mut offsets = vec![0usize; nkeys + 1];
418 for e in entries {
419 offsets[key(e) + 1] += 1;
420 }
421 for k in 0..nkeys {
422 offsets[k + 1] += offsets[k];
423 }
424 let mut out = match entries.first() {
427 Some(&first) => vec![first; entries.len()],
428 None => Vec::new(),
429 };
430 for e in entries {
431 let k = key(e);
432 out[offsets[k]] = *e;
433 offsets[k] += 1;
434 }
435 out
436}
437
438#[cfg(feature = "alloc")]
442fn merge_sorted<T: Scalar + Copy>(
443 sorted: &[(usize, usize, T)],
444 outer: impl Fn(&(usize, usize, T)) -> usize,
445 nouter: usize,
446) -> (Vec<(usize, usize, T)>, Vec<usize>) {
447 let mut merged: Vec<(usize, usize, T)> = Vec::with_capacity(sorted.len());
448 let mut counts = vec![0usize; nouter];
449 for &(r, c, v) in sorted {
450 match merged.last_mut() {
451 Some(last) if last.0 == r && last.1 == c => last.2 = last.2 + v,
452 _ => {
453 merged.push((r, c, v));
454 counts[outer(&(r, c, v))] += 1;
455 }
456 }
457 }
458 (merged, counts)
459}
460
461#[cfg(feature = "alloc")]
462fn zip_triplets<T: Copy>(rows: &[usize], cols: &[usize], vals: &[T]) -> Vec<(usize, usize, T)> {
463 rows.iter()
464 .zip(cols)
465 .zip(vals)
466 .map(|((&r, &c), &v)| (r, c, v))
467 .collect()
468}
469
470#[cfg(feature = "alloc")]
471fn to_csr_impl<T: Scalar + Copy>(
472 nrows: usize,
473 ncols: usize,
474 rows: &[usize],
475 cols: &[usize],
476 vals: &[T],
477) -> CsrMatrix<T> {
478 assert!(
481 ncols as u64 <= u64::from(u32::MAX) + 1,
482 "CsrMatrix supports at most 2^32 columns"
483 );
484 let entries = zip_triplets(rows, cols, vals);
485 let by_col = bucket_by(&entries, |e| e.1, ncols);
486 let by_row = bucket_by(&by_col, |e| e.0, nrows);
487 let (merged, counts) = merge_sorted(&by_row, |e| e.0, nrows);
488 let mut row_ptr = vec![0usize; nrows + 1];
489 for i in 0..nrows {
490 row_ptr[i + 1] = row_ptr[i] + counts[i];
491 }
492 let mut col_idx = Vec::with_capacity(merged.len());
493 let mut values = Vec::with_capacity(merged.len());
494 for (_, c, v) in merged {
495 col_idx.push(c as u32);
496 values.push(v);
497 }
498 CsrMatrix {
499 nrows,
500 ncols,
501 row_ptr,
502 col_idx,
503 values,
504 }
505}
506
507#[cfg(feature = "alloc")]
508fn to_csc_impl<T: Scalar + Copy>(
509 nrows: usize,
510 ncols: usize,
511 rows: &[usize],
512 cols: &[usize],
513 vals: &[T],
514) -> CscMatrix<T> {
515 let entries = zip_triplets(rows, cols, vals);
517 let by_row = bucket_by(&entries, |e| e.0, nrows);
518 let by_col = bucket_by(&by_row, |e| e.1, ncols);
519 let (merged, counts) = merge_sorted(&by_col, |e| e.1, ncols);
520 let mut col_ptr = vec![0usize; ncols + 1];
521 for j in 0..ncols {
522 col_ptr[j + 1] = col_ptr[j] + counts[j];
523 }
524 let mut row_idx = Vec::with_capacity(merged.len());
525 let mut values = Vec::with_capacity(merged.len());
526 for (r, _, v) in merged {
527 row_idx.push(r);
528 values.push(v);
529 }
530 CscMatrix {
531 nrows,
532 ncols,
533 col_ptr,
534 row_idx,
535 values,
536 }
537}
538
539#[cfg(feature = "alloc")]
559pub fn conjugate_gradient<T: Scalar + Copy + 'static>(
560 a: &CsrMatrix<T>,
561 b: &DVector<T>,
562 x0: Option<DVector<T>>,
563 tol: T,
564 max_iter: usize,
565) -> Result<DVector<T>, SparseError> {
566 let (x, report) = conjugate_gradient_with_report(a, b, x0, tol, max_iter)?;
567 report_to_result(x, report)
568}
569
570#[cfg(feature = "alloc")]
581pub fn conjugate_gradient_with_report<T: Scalar + Copy + 'static>(
582 a: &CsrMatrix<T>,
583 b: &DVector<T>,
584 x0: Option<DVector<T>>,
585 tol: T,
586 max_iter: usize,
587) -> Result<(DVector<T>, SolveReport<T>), SparseError> {
588 if a.nrows() != a.ncols()
590 || b.len() != a.nrows()
591 || x0.as_ref().is_some_and(|v| v.len() != a.nrows())
592 {
593 return Err(SparseError::DimensionMismatch {
594 what: "operands have incompatible dimensions",
595 });
596 }
597 #[cfg(feature = "simd")]
598 {
599 if simd::applies::<T>() {
600 return Ok(simd::cg(a, b, x0, tol, max_iter));
601 }
602 }
603 let n = b.len();
604 cg_core(n, |p, ap| a.matvec_into(p, ap), b, x0, tol, max_iter)
605}
606
607#[cfg(feature = "alloc")]
613pub(crate) fn cg_core<T, A>(
614 n: usize,
615 mut apply: A,
616 b: &DVector<T>,
617 x0: Option<DVector<T>>,
618 tol: T,
619 max_iter: usize,
620) -> Result<(DVector<T>, SolveReport<T>), SparseError>
621where
622 T: Scalar + Copy + 'static,
623 A: FnMut(&[T], &mut [T]) -> Result<(), SparseError>,
624{
625 let mut x = x0.unwrap_or_else(|| DVector::zeros(n));
626 let mut ax = DVector::zeros(n);
627 apply(x.as_slice(), ax.as_mut_slice())?;
628 let mut r = b.clone() - ax;
629 let b_norm = b.norm();
631 let target = if b_norm > T::zero() {
632 tol * b_norm
633 } else {
634 tol
635 };
636 if r.norm() <= target {
637 return Ok(report(x, SolveStatus::Converged, 0, r.norm()));
638 }
639 let mut p = r.clone();
640 let mut ap = DVector::zeros(n);
642 let mut rs_old = r.dot(&r);
643 for it in 0..max_iter {
644 apply(p.as_slice(), ap.as_mut_slice())?;
645 let p_ap = p.dot(&ap);
646 if p_ap.is_nan() || p_ap <= T::zero() {
649 return Ok(report(x, SolveStatus::Breakdown, it, r.norm()));
650 }
651 let alpha = rs_old / p_ap;
652 axpy_slice(x.as_mut_slice(), alpha, p.as_slice());
653 axpy_slice(r.as_mut_slice(), -alpha, ap.as_slice());
654 if r.norm() <= target {
655 return Ok(report(x, SolveStatus::Converged, it + 1, r.norm()));
656 }
657 let rs_new = r.dot(&r);
658 if !rs_new.is_finite() {
659 return Ok(report(x, SolveStatus::Breakdown, it, r.norm()));
660 }
661 let beta = rs_new / rs_old;
662 xpay_slice(p.as_mut_slice(), beta, r.as_slice());
663 rs_old = rs_new;
664 }
665 Ok(report(x, SolveStatus::NotConverged, max_iter, r.norm()))
666}
667
668#[cfg(feature = "simd")]
675mod simd {
676 use alloc::boxed::Box;
677 use alloc::vec::Vec;
678 use core::any::{Any, TypeId};
679 use tpt_math_linalg_dense::DVector;
680 use tpt_math_numeric::{Scalar, SolveReport, SolveStatus};
681 use tpt_simd_sparse::{
682 axpy, axpy_sqnorm, bicgstab_p_update, cg_update, dot, spmv_csr, sqnorm, xpay, CsrView, Real,
683 };
684
685 use super::CsrMatrix;
686
687 pub(crate) fn applies<T: 'static>() -> bool {
689 TypeId::of::<T>() == TypeId::of::<f64>() || TypeId::of::<T>() == TypeId::of::<f32>()
690 }
691
692 fn convert<U: 'static, V: 'static>(u: U) -> V {
694 *(Box::new(u) as Box<dyn Any>)
695 .downcast::<V>()
696 .unwrap_or_else(|_| unreachable!("checked by `applies`"))
697 }
698
699 fn view_as<U: 'static, V: 'static>(u: &U) -> &V {
701 (u as &dyn Any)
702 .downcast_ref::<V>()
703 .unwrap_or_else(|| unreachable!("checked by `applies`"))
704 }
705
706 fn csr_view<R: Real>(a: &CsrMatrix<R>) -> CsrView<'_, R> {
709 CsrView::try_new(a.nrows, a.ncols, &a.row_ptr, &a.col_idx, &a.values)
710 .unwrap_or_else(|_| unreachable!("CsrMatrix invariants hold by construction"))
711 }
712
713 fn finish<T: 'static, R: 'static>(
714 x: Vec<R>,
715 rep: SolveReport<R>,
716 ) -> (DVector<T>, SolveReport<T>) {
717 (
718 DVector::from_vec(convert::<Vec<R>, Vec<T>>(x)),
719 SolveReport {
720 status: rep.status,
721 iterations: rep.iterations,
722 residual: convert(rep.residual),
723 },
724 )
725 }
726
727 type Core<R> = fn(&CsrMatrix<R>, &[R], Option<Vec<R>>, R, usize) -> (Vec<R>, SolveReport<R>);
729
730 fn run<T: Copy + 'static, R: Scalar + Real + 'static>(
732 a: &CsrMatrix<T>,
733 b: &DVector<T>,
734 x0: Option<DVector<T>>,
735 tol: T,
736 max_iter: usize,
737 core: Core<R>,
738 ) -> (DVector<T>, SolveReport<T>) {
739 let a = view_as::<CsrMatrix<T>, CsrMatrix<R>>(a);
740 let b = view_as::<DVector<T>, DVector<R>>(b).as_slice();
741 let x0 = x0.map(|v| convert::<DVector<T>, DVector<R>>(v).as_slice().to_vec());
742 let (x, rep) = core(a, b, x0, convert::<T, R>(tol), max_iter);
743 finish(x, rep)
744 }
745
746 pub(crate) fn cg<T: Copy + 'static>(
748 a: &CsrMatrix<T>,
749 b: &DVector<T>,
750 x0: Option<DVector<T>>,
751 tol: T,
752 max_iter: usize,
753 ) -> (DVector<T>, SolveReport<T>) {
754 if TypeId::of::<T>() == TypeId::of::<f64>() {
755 run::<T, f64>(a, b, x0, tol, max_iter, cg_core::<f64>)
756 } else {
757 run::<T, f32>(a, b, x0, tol, max_iter, cg_core::<f32>)
758 }
759 }
760
761 pub(crate) fn bicgstab<T: Copy + 'static>(
763 a: &CsrMatrix<T>,
764 b: &DVector<T>,
765 x0: Option<DVector<T>>,
766 tol: T,
767 max_iter: usize,
768 ) -> (DVector<T>, SolveReport<T>) {
769 if TypeId::of::<T>() == TypeId::of::<f64>() {
770 run::<T, f64>(a, b, x0, tol, max_iter, bicgstab_core::<f64>)
771 } else {
772 run::<T, f32>(a, b, x0, tol, max_iter, bicgstab_core::<f32>)
773 }
774 }
775
776 fn cg_core<R: Scalar + Real + 'static>(
777 a: &CsrMatrix<R>,
778 b: &[R],
779 x0: Option<Vec<R>>,
780 tol: R,
781 max_iter: usize,
782 ) -> (Vec<R>, SolveReport<R>) {
783 let n = b.len();
784 let view = csr_view(a);
785 let mut x = x0.unwrap_or_else(|| alloc::vec![R::zero(); n]);
786 let mut r = b.to_vec();
788 spmv_csr(-R::one(), &view, &x, R::one(), &mut r);
789 let b_norm = sqnorm(b).sqrt();
791 let target = if b_norm > R::zero() {
792 tol * b_norm
793 } else {
794 tol
795 };
796 let mut rs_old = sqnorm(&r);
797 if rs_old.sqrt() <= target {
798 return (x, rep(SolveStatus::Converged, 0, rs_old.sqrt()));
799 }
800 let mut p = r.clone();
801 let mut ap = alloc::vec![R::zero(); n];
802 for it in 0..max_iter {
803 spmv_csr(R::one(), &view, &p, R::zero(), &mut ap);
804 let p_ap = dot(&p, &ap);
805 if p_ap.is_nan() || p_ap <= R::zero() {
808 return (x, rep(SolveStatus::Breakdown, it, rs_old.sqrt()));
809 }
810 let alpha = rs_old / p_ap;
811 let rs_new = cg_update(alpha, &p, &ap, &mut x, &mut r);
813 if rs_new.sqrt() <= target {
814 return (x, rep(SolveStatus::Converged, it + 1, rs_new.sqrt()));
815 }
816 if !rs_new.is_finite() {
817 return (x, rep(SolveStatus::Breakdown, it, rs_new.sqrt()));
818 }
819 let beta = rs_new / rs_old;
820 xpay(&r, beta, &mut p);
821 rs_old = rs_new;
822 }
823 (x, rep(SolveStatus::NotConverged, max_iter, rs_old.sqrt()))
824 }
825
826 fn bicgstab_core<R: Scalar + Real + 'static>(
827 a: &CsrMatrix<R>,
828 b: &[R],
829 x0: Option<Vec<R>>,
830 tol: R,
831 max_iter: usize,
832 ) -> (Vec<R>, SolveReport<R>) {
833 let n = b.len();
834 let view = csr_view(a);
835 let mut x = x0.unwrap_or_else(|| alloc::vec![R::zero(); n]);
836 let mut r = b.to_vec();
837 spmv_csr(-R::one(), &view, &x, R::one(), &mut r);
838 let b_norm = sqnorm(b).sqrt();
839 let target = if b_norm > R::zero() {
840 tol * b_norm
841 } else {
842 tol
843 };
844 let mut r_norm = sqnorm(&r).sqrt();
845 if r_norm <= target {
846 return (x, rep(SolveStatus::Converged, 0, r_norm));
847 }
848 let r0 = r.clone();
849 let mut p = alloc::vec![R::zero(); n];
850 let mut v = alloc::vec![R::zero(); n];
851 let mut s = alloc::vec![R::zero(); n];
852 let mut t = alloc::vec![R::zero(); n];
853 let mut rho = R::one();
854 let mut alpha = R::one();
855 let mut omega = R::one();
856 for it in 0..max_iter {
857 let rho_new = dot(&r0, &r);
858 if rho_new == R::zero() || !rho_new.is_finite() {
859 return (x, rep(SolveStatus::Breakdown, it, r_norm));
860 }
861 let beta = (rho_new / rho) * (alpha / omega);
862 bicgstab_p_update(beta, omega, &r, &v, &mut p);
864 spmv_csr(R::one(), &view, &p, R::zero(), &mut v);
865 let r0_v = dot(&r0, &v);
866 if r0_v == R::zero() || !r0_v.is_finite() {
867 return (x, rep(SolveStatus::Breakdown, it, r_norm));
868 }
869 alpha = rho_new / r0_v;
870 s.copy_from_slice(&r);
872 axpy(-alpha, &v, &mut s);
873 let s_norm = sqnorm(&s).sqrt();
874 if s_norm <= target {
876 axpy(alpha, &p, &mut x);
877 return (x, rep(SolveStatus::Converged, it + 1, s_norm));
878 }
879 spmv_csr(R::one(), &view, &s, R::zero(), &mut t);
880 let t_sq = dot(&t, &t);
881 if t_sq == R::zero() {
882 return (x, rep(SolveStatus::Breakdown, it, r_norm));
883 }
884 omega = dot(&t, &s) / t_sq;
885 if omega == R::zero() || !omega.is_finite() {
886 return (x, rep(SolveStatus::Breakdown, it, r_norm));
887 }
888 axpy(alpha, &p, &mut x);
890 axpy(omega, &s, &mut x);
891 r.copy_from_slice(&s);
892 r_norm = axpy_sqnorm(-omega, &t, &mut r).sqrt();
893 if r_norm <= target {
894 return (x, rep(SolveStatus::Converged, it + 1, r_norm));
895 }
896 rho = rho_new;
897 }
898 (x, rep(SolveStatus::NotConverged, max_iter, r_norm))
899 }
900
901 fn rep<R>(status: SolveStatus, iterations: usize, residual: R) -> SolveReport<R> {
902 SolveReport {
903 status,
904 iterations,
905 residual,
906 }
907 }
908}
909
910#[cfg(feature = "alloc")]
912fn report<T>(
913 x: DVector<T>,
914 status: SolveStatus,
915 iterations: usize,
916 residual: T,
917) -> (DVector<T>, SolveReport<T>) {
918 (
919 x,
920 SolveReport {
921 status,
922 iterations,
923 residual,
924 },
925 )
926}
927
928#[cfg(feature = "alloc")]
930fn report_to_result<T>(x: DVector<T>, report: SolveReport<T>) -> Result<DVector<T>, SparseError> {
931 match report.status {
932 SolveStatus::Converged => Ok(x),
933 SolveStatus::NotConverged => Err(SparseError::NotConverged {
934 iterations: report.iterations,
935 }),
936 SolveStatus::Breakdown => Err(SparseError::Breakdown {
937 iterations: report.iterations,
938 }),
939 _ => Err(SparseError::Breakdown {
941 iterations: report.iterations,
942 }),
943 }
944}
945
946#[cfg(feature = "alloc")]
959pub fn bicgstab<T: Scalar + Copy + 'static>(
960 a: &CsrMatrix<T>,
961 b: &DVector<T>,
962 x0: Option<DVector<T>>,
963 tol: T,
964 max_iter: usize,
965) -> Result<DVector<T>, SparseError> {
966 let (x, report) = bicgstab_with_report(a, b, x0, tol, max_iter)?;
967 report_to_result(x, report)
968}
969
970#[cfg(feature = "alloc")]
977pub fn bicgstab_with_report<T: Scalar + Copy + 'static>(
978 a: &CsrMatrix<T>,
979 b: &DVector<T>,
980 x0: Option<DVector<T>>,
981 tol: T,
982 max_iter: usize,
983) -> Result<(DVector<T>, SolveReport<T>), SparseError> {
984 if a.nrows() != a.ncols()
986 || b.len() != a.nrows()
987 || x0.as_ref().is_some_and(|v| v.len() != a.nrows())
988 {
989 return Err(SparseError::DimensionMismatch {
990 what: "operands have incompatible dimensions",
991 });
992 }
993 #[cfg(feature = "simd")]
994 {
995 if simd::applies::<T>() {
996 return Ok(simd::bicgstab(a, b, x0, tol, max_iter));
997 }
998 }
999 let n = b.len();
1000 bicgstab_core(n, |p, out| a.matvec_into(p, out), b, x0, tol, max_iter)
1001}
1002
1003#[cfg(feature = "alloc")]
1006pub(crate) fn bicgstab_core<T, A>(
1007 n: usize,
1008 mut apply: A,
1009 b: &DVector<T>,
1010 x0: Option<DVector<T>>,
1011 tol: T,
1012 max_iter: usize,
1013) -> Result<(DVector<T>, SolveReport<T>), SparseError>
1014where
1015 T: Scalar + Copy + 'static,
1016 A: FnMut(&[T], &mut [T]) -> Result<(), SparseError>,
1017{
1018 let mut x = x0.unwrap_or_else(|| DVector::zeros(n));
1019 let mut ax = DVector::zeros(n);
1020 apply(x.as_slice(), ax.as_mut_slice())?;
1021 let mut r = b.clone() - ax;
1022 let b_norm = b.norm();
1024 let target = if b_norm > T::zero() {
1025 tol * b_norm
1026 } else {
1027 tol
1028 };
1029 if r.norm() <= target {
1030 return Ok(report(x, SolveStatus::Converged, 0, r.norm()));
1031 }
1032 let r0 = r.clone();
1033 let mut p = DVector::zeros(n);
1035 let mut v = DVector::zeros(n);
1036 let mut s = DVector::zeros(n);
1037 let mut t = DVector::zeros(n);
1038 let mut rho = T::one();
1039 let mut alpha = T::one();
1040 let mut omega = T::one();
1041 for it in 0..max_iter {
1042 let rho_new = r0.dot(&r);
1043 if rho_new == T::zero() || !rho_new.is_finite() {
1044 return Ok(report(x, SolveStatus::Breakdown, it, r.norm()));
1045 }
1046 let beta = (rho_new / rho) * (alpha / omega);
1047 for ((pi, &vi), &ri) in p
1049 .as_mut_slice()
1050 .iter_mut()
1051 .zip(v.as_slice())
1052 .zip(r.as_slice())
1053 {
1054 *pi = ri + beta * (*pi - omega * vi);
1055 }
1056 apply(p.as_slice(), v.as_mut_slice())?;
1057 let r0_v = r0.dot(&v);
1058 if r0_v == T::zero() || !r0_v.is_finite() {
1059 return Ok(report(x, SolveStatus::Breakdown, it, r.norm()));
1060 }
1061 alpha = rho_new / r0_v;
1062 s.as_mut_slice().copy_from_slice(r.as_slice());
1064 axpy_slice(s.as_mut_slice(), -alpha, v.as_slice());
1065 if s.norm() <= target {
1067 axpy_slice(x.as_mut_slice(), alpha, p.as_slice());
1068 return Ok(report(x, SolveStatus::Converged, it + 1, s.norm()));
1069 }
1070 apply(s.as_slice(), t.as_mut_slice())?;
1071 let t_sq = t.dot(&t);
1072 if t_sq == T::zero() {
1073 return Ok(report(x, SolveStatus::Breakdown, it, r.norm()));
1074 }
1075 omega = t.dot(&s) / t_sq;
1076 if omega == T::zero() || !omega.is_finite() {
1077 return Ok(report(x, SolveStatus::Breakdown, it, r.norm()));
1078 }
1079 axpy_slice(x.as_mut_slice(), alpha, p.as_slice());
1081 axpy_slice(x.as_mut_slice(), omega, s.as_slice());
1082 r.as_mut_slice().copy_from_slice(s.as_slice());
1083 axpy_slice(r.as_mut_slice(), -omega, t.as_slice());
1084 if r.norm() <= target {
1085 return Ok(report(x, SolveStatus::Converged, it + 1, r.norm()));
1086 }
1087 rho = rho_new;
1088 }
1089 Ok(report(x, SolveStatus::NotConverged, max_iter, r.norm()))
1090}
1091
1092#[cfg(feature = "alloc")]
1094fn slice_norm<T: Scalar + Copy>(v: &[T]) -> T {
1095 v.iter().fold(T::zero(), |acc, &x| acc + x * x).sqrt()
1096}
1097
1098#[cfg(feature = "alloc")]
1100fn slice_dot<T: Scalar + Copy>(a: &[T], b: &[T]) -> T {
1101 a.iter().zip(b).fold(T::zero(), |acc, (&x, &y)| acc + x * y)
1102}
1103
1104#[cfg(feature = "alloc")]
1106fn axpy_slice<T: Scalar + Copy>(y: &mut [T], alpha: T, x: &[T]) {
1107 for (yi, &xi) in y.iter_mut().zip(x) {
1108 *yi = *yi + alpha * xi;
1109 }
1110}
1111
1112#[cfg(feature = "alloc")]
1114fn xpay_slice<T: Scalar + Copy>(y: &mut [T], beta: T, x: &[T]) {
1115 for (yi, &xi) in y.iter_mut().zip(x) {
1116 *yi = xi + beta * *yi;
1117 }
1118}
1119
1120#[cfg(feature = "alloc")]
1122fn givens<T: Scalar + Copy>(a: T, b: T) -> (T, T) {
1123 if b == T::zero() {
1124 return (T::one(), T::zero());
1125 }
1126 if b.abs() > a.abs() {
1127 let t = a / b;
1128 let s = T::one() / (T::one() + t * t).sqrt();
1129 (s * t, s)
1130 } else {
1131 let t = b / a;
1132 let c = T::one() / (T::one() + t * t).sqrt();
1133 (c, c * t)
1134 }
1135}
1136
1137#[cfg(feature = "alloc")]
1174pub fn gmres<T: Scalar + Copy + 'static>(
1175 a: &CsrMatrix<T>,
1176 b: &DVector<T>,
1177 x0: Option<DVector<T>>,
1178 tol: T,
1179 restart: usize,
1180 max_iter: usize,
1181) -> Result<DVector<T>, SparseError> {
1182 gmres_right_preconditioned(a, b, x0, tol, restart, max_iter, |v: &[T]| {
1183 Ok::<Vec<T>, SparseError>(v.to_vec())
1184 })
1185}
1186
1187#[cfg(feature = "alloc")]
1199pub fn gmres_right_preconditioned<T, P>(
1200 a: &CsrMatrix<T>,
1201 b: &DVector<T>,
1202 x0: Option<DVector<T>>,
1203 tol: T,
1204 restart: usize,
1205 max_iter: usize,
1206 precond: P,
1207) -> Result<DVector<T>, SparseError>
1208where
1209 T: Scalar + Copy + 'static,
1210 P: Fn(&[T]) -> Result<Vec<T>, SparseError>,
1211{
1212 let (x, report) =
1213 gmres_right_preconditioned_with_report(a, b, x0, tol, restart, max_iter, precond)?;
1214 report_to_result(x, report)
1215}
1216
1217#[cfg(feature = "alloc")]
1225pub fn gmres_right_preconditioned_with_report<T, P>(
1226 a: &CsrMatrix<T>,
1227 b: &DVector<T>,
1228 x0: Option<DVector<T>>,
1229 tol: T,
1230 restart: usize,
1231 max_iter: usize,
1232 precond: P,
1233) -> Result<(DVector<T>, SolveReport<T>), SparseError>
1234where
1235 T: Scalar + Copy + 'static,
1236 P: Fn(&[T]) -> Result<Vec<T>, SparseError>,
1237{
1238 if a.nrows() != a.ncols() || b.len() != a.nrows() {
1239 return Err(SparseError::DimensionMismatch {
1240 what: "operands have incompatible dimensions",
1241 });
1242 }
1243 gmres_core(
1244 b.len(),
1245 |p, out| a.matvec_into(p, out),
1246 b,
1247 x0,
1248 tol,
1249 restart,
1250 max_iter,
1251 precond,
1252 )
1253}
1254
1255#[cfg(feature = "alloc")]
1258#[allow(clippy::too_many_arguments)]
1259pub(crate) fn gmres_core<T, P, A>(
1260 n: usize,
1261 mut apply: A,
1262 b: &DVector<T>,
1263 x0: Option<DVector<T>>,
1264 tol: T,
1265 restart: usize,
1266 max_iter: usize,
1267 precond: P,
1268) -> Result<(DVector<T>, SolveReport<T>), SparseError>
1269where
1270 T: Scalar + Copy + 'static,
1271 P: Fn(&[T]) -> Result<Vec<T>, SparseError>,
1272 A: FnMut(&[T], &mut [T]) -> Result<(), SparseError>,
1273{
1274 let m = restart.max(1);
1275 let mut x: Vec<T> = match x0 {
1276 Some(v) if v.len() == n => v.as_slice().to_vec(),
1277 Some(_) => {
1278 return Err(SparseError::DimensionMismatch {
1279 what: "operands have incompatible dimensions",
1280 })
1281 }
1282 None => vec![T::zero(); n],
1283 };
1284 let b_slice = b.as_slice();
1285 let b_norm = slice_norm(b_slice);
1286 let target = if b_norm > T::zero() {
1287 tol * b_norm
1288 } else {
1289 tol
1290 };
1291
1292 let mut iterations = 0usize;
1293 let mut ax = vec![T::zero(); n];
1294 loop {
1295 apply(&x, &mut ax)?;
1296 let r: Vec<T> = (0..n).map(|i| b_slice[i] - ax[i]).collect();
1297 let beta = slice_norm(&r);
1298 if beta <= target {
1299 return Ok((
1300 DVector::from_vec(x),
1301 SolveReport {
1302 status: SolveStatus::Converged,
1303 iterations,
1304 residual: beta,
1305 },
1306 ));
1307 }
1308 if iterations >= max_iter {
1309 return Ok((
1310 DVector::from_vec(x),
1311 SolveReport {
1312 status: SolveStatus::NotConverged,
1313 iterations,
1314 residual: beta,
1315 },
1316 ));
1317 }
1318
1319 let mut basis: Vec<Vec<T>> = vec![r.iter().map(|&v| v / beta).collect()];
1323 let mut hess: Vec<Vec<T>> = Vec::with_capacity(m);
1324 let mut rotations: Vec<(T, T)> = Vec::with_capacity(m);
1325 let mut g = vec![T::zero(); m + 1];
1326 g[0] = beta;
1327 let mut k = 0;
1328 while k < m && iterations < max_iter {
1329 iterations += 1;
1330 let z = precond(&basis[k])?;
1331 let mut w = vec![T::zero(); n];
1332 apply(&z, &mut w)?;
1333 let mut col = vec![T::zero(); k + 2];
1334 for i in 0..=k {
1335 let h_ik = slice_dot(&w, &basis[i]);
1336 col[i] = h_ik;
1337 for (wj, &vj) in w.iter_mut().zip(&basis[i]) {
1338 *wj = *wj - h_ik * vj;
1339 }
1340 }
1341 let h_next = slice_norm(&w);
1342 col[k + 1] = h_next;
1343
1344 for (i, &(c, s)) in rotations.iter().enumerate() {
1346 let temp = c * col[i] + s * col[i + 1];
1347 col[i + 1] = -s * col[i] + c * col[i + 1];
1348 col[i] = temp;
1349 }
1350 let (c, s) = givens(col[k], col[k + 1]);
1351 rotations.push((c, s));
1352 col[k] = c * col[k] + s * col[k + 1];
1353 col[k + 1] = T::zero();
1354 let g_k = g[k];
1355 g[k + 1] = -s * g_k;
1356 g[k] = c * g_k;
1357 hess.push(col);
1358 k += 1;
1359
1360 if g[k].abs() <= target || h_next == T::zero() {
1363 break;
1364 }
1365 basis.push(w.iter().map(|&v| v / h_next).collect());
1366 }
1367
1368 let mut y = vec![T::zero(); k];
1370 for i in (0..k).rev() {
1371 let mut s = g[i];
1372 for j in (i + 1)..k {
1373 s = s - hess[j][i] * y[j];
1374 }
1375 let diag = hess[i][i];
1376 if diag == T::zero() {
1377 return Ok((
1378 DVector::from_vec(x),
1379 SolveReport {
1380 status: SolveStatus::Breakdown,
1381 iterations,
1382 residual: beta,
1383 },
1384 ));
1385 }
1386 y[i] = s / diag;
1387 }
1388 let mut combination = vec![T::zero(); n];
1390 for (j, &yj) in y.iter().enumerate() {
1391 for (ci, &vi) in combination.iter_mut().zip(&basis[j]) {
1392 *ci = *ci + yj * vi;
1393 }
1394 }
1395 let correction = precond(&combination)?;
1396 for (xi, &si) in x.iter_mut().zip(&correction) {
1397 *xi = *xi + si;
1398 }
1399 }
1400}
1401
1402#[cfg(feature = "alloc")]
1412pub fn gmres_ilu0(
1413 a: &CsrMatrix<f64>,
1414 b: &DVector<f64>,
1415 x0: Option<DVector<f64>>,
1416 tol: f64,
1417 restart: usize,
1418 max_iter: usize,
1419) -> Result<DVector<f64>, SparseError> {
1420 let ilu = Ilu0::factor(a)?;
1421 gmres_right_preconditioned(a, b, x0, tol, restart, max_iter, |v: &[f64]| {
1422 ilu.apply(&DVector::from_vec(v.to_vec()))
1423 .map(|d| d.as_slice().to_vec())
1424 })
1425}
1426
1427#[cfg(feature = "alloc")]
1470pub fn preconditioned_conjugate_gradient<T, P>(
1471 a: &CsrMatrix<T>,
1472 b: &DVector<T>,
1473 x0: Option<DVector<T>>,
1474 tol: T,
1475 max_iter: usize,
1476 precond: P,
1477) -> Result<DVector<T>, SparseError>
1478where
1479 T: Scalar + Copy + 'static,
1480 P: Fn(&DVector<T>) -> Result<DVector<T>, SparseError>,
1481{
1482 if a.nrows() != a.ncols() || b.len() != a.nrows() {
1483 return Err(SparseError::DimensionMismatch {
1484 what: "operands have incompatible dimensions",
1485 });
1486 }
1487 let n = b.len();
1488 let mut x: Vec<T> = match x0 {
1489 Some(v) if v.len() == n => v.as_slice().to_vec(),
1490 Some(_) => {
1491 return Err(SparseError::DimensionMismatch {
1492 what: "operands have incompatible dimensions",
1493 })
1494 }
1495 None => vec![T::zero(); n],
1496 };
1497 let b_slice = b.as_slice();
1498 let b_norm = slice_norm(b_slice);
1499 let target = if b_norm > T::zero() {
1500 tol * b_norm
1501 } else {
1502 tol
1503 };
1504
1505 let mut ax = vec![T::zero(); n];
1506 a.matvec_into(&x, &mut ax)?;
1507 let mut r: Vec<T> = (0..n).map(|i| b_slice[i] - ax[i]).collect();
1508 if slice_norm(&r) <= target {
1509 return Ok(DVector::from_vec(x));
1510 }
1511 let mut z = precond(&DVector::from_vec(r.clone()))?.as_slice().to_vec();
1512 let mut p = z.clone();
1513 let mut rz = slice_dot(&r, &z);
1514 let mut ap = vec![T::zero(); n];
1515
1516 for it in 0..max_iter {
1517 a.matvec_into(&p, &mut ap)?;
1518 let p_ap = slice_dot(&p, &ap);
1519 if p_ap.is_nan() || p_ap <= T::zero() {
1520 return Err(SparseError::Breakdown { iterations: it });
1521 }
1522 let alpha = rz / p_ap;
1523 for (xi, &pi) in x.iter_mut().zip(&p) {
1524 *xi = *xi + alpha * pi;
1525 }
1526 for (ri, &api) in r.iter_mut().zip(&ap) {
1527 *ri = *ri - alpha * api;
1528 }
1529 if slice_norm(&r) <= target {
1530 return Ok(DVector::from_vec(x));
1531 }
1532 z = precond(&DVector::from_vec(r.clone()))?.as_slice().to_vec();
1533 let rz_new = slice_dot(&r, &z);
1534 if !rz_new.is_finite() {
1535 return Err(SparseError::Breakdown { iterations: it });
1536 }
1537 let beta = rz_new / rz;
1538 for (pi, &zi) in p.iter_mut().zip(&z) {
1539 *pi = zi + beta * *pi;
1540 }
1541 rz = rz_new;
1542 }
1543 Err(SparseError::NotConverged {
1544 iterations: max_iter,
1545 })
1546}
1547
1548#[cfg(feature = "alloc")]
1580pub fn jacobi_preconditioned_cg<T: Scalar + Copy + 'static>(
1581 a: &CsrMatrix<T>,
1582 b: &DVector<T>,
1583 x0: Option<DVector<T>>,
1584 tol: T,
1585 max_iter: usize,
1586) -> Result<DVector<T>, SparseError> {
1587 if a.nrows() != a.ncols() || b.len() != a.nrows() {
1588 return Err(SparseError::DimensionMismatch {
1589 what: "operands have incompatible dimensions",
1590 });
1591 }
1592 let n = b.len();
1593
1594 let mut diag = vec![T::zero(); n];
1596 for (i, j, &v) in a.iter() {
1597 if i == j {
1598 diag[i] = v;
1599 }
1600 }
1601 if diag.iter().any(|&d| d == T::zero()) {
1602 return Err(SparseError::Breakdown { iterations: 0 });
1603 }
1604 preconditioned_conjugate_gradient(a, b, x0, tol, max_iter, |r: &DVector<T>| {
1605 Ok(DVector::from_vec(
1606 r.iter().zip(&diag).map(|(&ri, &di)| ri / di).collect(),
1607 ))
1608 })
1609}
1610
1611#[cfg(feature = "alloc")]
1619#[derive(Clone, Debug, PartialEq)]
1620pub struct SparseCholesky {
1621 n: usize,
1622 columns: Vec<Vec<(usize, f64)>>,
1623}
1624
1625#[cfg(feature = "alloc")]
1626impl SparseCholesky {
1627 pub fn factor(a: &CsrMatrix<f64>) -> Result<Self, SparseError> {
1637 if a.nrows() != a.ncols() {
1638 return Err(SparseError::DimensionMismatch {
1639 what: "operands have incompatible dimensions",
1640 });
1641 }
1642 let n = a.nrows();
1643 let mut columns: Vec<Vec<(usize, f64)>> = Vec::with_capacity(n);
1644 let mut work = vec![0.0; n];
1645
1646 for j in 0..n {
1647 for (row, col, &v) in a.iter() {
1649 if row == j && col >= j {
1650 work[col] = v;
1651 }
1652 }
1653 for column in &columns[..j] {
1655 let Ok(pos) = column.binary_search_by_key(&j, |&(i, _)| i) else {
1656 continue;
1657 };
1658 let ljk = column[pos].1;
1659 for &(i, lik) in &column[pos..] {
1660 work[i] -= lik * ljk;
1661 }
1662 }
1663
1664 let pivot = work[j];
1665 if pivot.is_nan() || pivot <= 0.0 {
1666 return Err(SparseError::Breakdown { iterations: j });
1667 }
1668 let diag = tpt_math_numeric::prelude::Float::sqrt(pivot);
1669 let mut column = vec![(j, diag)];
1670 for (i, &w) in work.iter().enumerate().skip(j + 1) {
1671 if w != 0.0 {
1672 column.push((i, w / diag));
1673 }
1674 }
1675 for w in work.iter_mut().skip(j) {
1677 *w = 0.0;
1678 }
1679 columns.push(column);
1680 }
1681 Ok(SparseCholesky { n, columns })
1682 }
1683
1684 pub fn dim(&self) -> usize {
1686 self.n
1687 }
1688
1689 pub fn nnz(&self) -> usize {
1692 self.columns.iter().map(Vec::len).sum()
1693 }
1694
1695 pub fn solve(&self, b: &DVector<f64>) -> Result<DVector<f64>, SparseError> {
1701 if b.len() != self.n {
1702 return Err(SparseError::DimensionMismatch {
1703 what: "operands have incompatible dimensions",
1704 });
1705 }
1706 let mut x: Vec<f64> = b.as_slice().to_vec();
1707 for j in 0..self.n {
1709 let column = &self.columns[j];
1710 x[j] /= column[0].1;
1711 let xj = x[j];
1712 for &(i, v) in &column[1..] {
1713 x[i] -= v * xj;
1714 }
1715 }
1716 for j in (0..self.n).rev() {
1718 let column = &self.columns[j];
1719 let mut s = x[j];
1720 for &(i, v) in &column[1..] {
1721 s -= v * x[i];
1722 }
1723 x[j] = s / column[0].1;
1724 }
1725 Ok(DVector::from_vec(x))
1726 }
1727}
1728
1729#[cfg(feature = "alloc")]
1737#[derive(Clone, Debug, PartialEq)]
1738pub struct Ilu0 {
1739 n: usize,
1740 rows: Vec<Vec<(usize, f64)>>,
1743 diagonal: Vec<usize>,
1745}
1746
1747#[cfg(feature = "alloc")]
1748impl Ilu0 {
1749 pub fn factor(a: &CsrMatrix<f64>) -> Result<Self, SparseError> {
1757 if a.nrows() != a.ncols() {
1758 return Err(SparseError::DimensionMismatch {
1759 what: "operands have incompatible dimensions",
1760 });
1761 }
1762 let n = a.nrows();
1763 let mut rows: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
1764 for (r, c, &v) in a.iter() {
1765 rows[r].push((c, v));
1766 }
1767 for row in &mut rows {
1768 row.sort_by_key(|&(c, _)| c);
1769 }
1770 let mut diagonal = vec![0usize; n];
1771 for (i, row) in rows.iter().enumerate() {
1772 match row.iter().position(|&(c, _)| c == i) {
1773 Some(p) => diagonal[i] = p,
1774 None => return Err(SparseError::Breakdown { iterations: i }),
1775 }
1776 }
1777
1778 const ABSENT: usize = usize::MAX;
1780 let mut pos = vec![ABSENT; n];
1781 for i in 0..n {
1782 for (p, &(c, _)) in rows[i].iter().enumerate() {
1783 pos[c] = p;
1784 }
1785 for kp in 0..rows[i].len() {
1786 let k = rows[i][kp].0;
1787 if k >= i {
1788 break;
1789 }
1790 let pivot = rows[k][diagonal[k]].1;
1791 if pivot == 0.0 || pivot.is_nan() {
1792 return Err(SparseError::Breakdown { iterations: k });
1793 }
1794 let multiplier = rows[i][kp].1 / pivot;
1795 rows[i][kp].1 = multiplier;
1796 let row_k = rows[k].clone();
1798 for &(j, ukj) in row_k.iter().filter(|&&(j, _)| j > k) {
1799 let p = pos[j];
1800 if p != ABSENT {
1801 rows[i][p].1 -= multiplier * ukj;
1802 }
1803 }
1804 }
1805 for &(c, _) in &rows[i] {
1806 pos[c] = ABSENT;
1807 }
1808 }
1809 Ok(Ilu0 { n, rows, diagonal })
1810 }
1811
1812 pub fn apply(&self, r: &DVector<f64>) -> Result<DVector<f64>, SparseError> {
1818 if r.len() != self.n {
1819 return Err(SparseError::DimensionMismatch {
1820 what: "operands have incompatible dimensions",
1821 });
1822 }
1823 let mut y: Vec<f64> = r.as_slice().to_vec();
1824 for i in 0..self.n {
1826 let mut s = y[i];
1827 for &(j, v) in self.rows[i].iter().take_while(|&&(j, _)| j < i) {
1828 s -= v * y[j];
1829 }
1830 y[i] = s;
1831 }
1832 for i in (0..self.n).rev() {
1834 let mut s = y[i];
1835 for &(j, v) in &self.rows[i][self.diagonal[i] + 1..] {
1836 s -= v * y[j];
1837 }
1838 y[i] = s / self.rows[i][self.diagonal[i]].1;
1839 }
1840 Ok(DVector::from_vec(y))
1841 }
1842}
1843
1844#[cfg(feature = "alloc")]
1852#[derive(Clone, Debug, PartialEq)]
1853pub struct Ic0 {
1854 factor: SparseCholesky,
1855}
1856
1857#[cfg(feature = "alloc")]
1858impl Ic0 {
1859 pub fn factor(a: &CsrMatrix<f64>) -> Result<Self, SparseError> {
1870 if a.nrows() != a.ncols() {
1871 return Err(SparseError::DimensionMismatch {
1872 what: "operands have incompatible dimensions",
1873 });
1874 }
1875 let n = a.nrows();
1876 let mut lower: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
1878 for (r, c, &v) in a.iter() {
1879 if r >= c {
1880 lower[c].push((r, v));
1881 }
1882 }
1883 for col in &mut lower {
1884 col.sort_by_key(|&(i, _)| i);
1885 }
1886
1887 let mut columns: Vec<Vec<(usize, f64)>> = Vec::with_capacity(n);
1888 let mut contributors: Vec<Vec<usize>> = vec![Vec::new(); n];
1891 let mut work = vec![0.0; n];
1892 let mut in_pattern = vec![false; n];
1893
1894 for j in 0..n {
1895 for &(i, v) in &lower[j] {
1896 work[i] = v;
1897 in_pattern[i] = true;
1898 }
1899 for &k in &contributors[j] {
1900 let col_k = &columns[k];
1901 let Ok(pos) = col_k.binary_search_by_key(&j, |&(i, _)| i) else {
1902 continue;
1903 };
1904 let ljk = col_k[pos].1;
1905 for &(i, lik) in &col_k[pos..] {
1906 if in_pattern[i] {
1907 work[i] -= lik * ljk;
1908 }
1909 }
1910 }
1911 let pivot = work[j];
1912 if pivot.is_nan() || pivot <= 0.0 {
1913 for &(i, _) in &lower[j] {
1914 work[i] = 0.0;
1915 in_pattern[i] = false;
1916 }
1917 return Err(SparseError::Breakdown { iterations: j });
1918 }
1919 let diag = tpt_math_numeric::prelude::Float::sqrt(pivot);
1920 let mut column = vec![(j, diag)];
1921 for &(i, _) in lower[j].iter().skip(1) {
1922 column.push((i, work[i] / diag));
1923 contributors[i].push(j);
1924 }
1925 for &(i, _) in &lower[j] {
1926 work[i] = 0.0;
1927 in_pattern[i] = false;
1928 }
1929 columns.push(column);
1930 }
1931 Ok(Ic0 {
1932 factor: SparseCholesky { n, columns },
1933 })
1934 }
1935
1936 pub fn dim(&self) -> usize {
1938 self.factor.dim()
1939 }
1940
1941 pub fn apply(&self, r: &DVector<f64>) -> Result<DVector<f64>, SparseError> {
1948 self.factor.solve(r)
1949 }
1950}
1951
1952#[cfg(feature = "alloc")]
1964pub fn ic0_preconditioned_cg(
1965 a: &CsrMatrix<f64>,
1966 b: &DVector<f64>,
1967 x0: Option<DVector<f64>>,
1968 tol: f64,
1969 max_iter: usize,
1970) -> Result<DVector<f64>, SparseError> {
1971 let ic = Ic0::factor(a)?;
1972 preconditioned_conjugate_gradient(a, b, x0, tol, max_iter, |r: &DVector<f64>| ic.apply(r))
1973}
1974
1975#[cfg(feature = "alloc")]
1986#[derive(Clone, Debug, PartialEq)]
1987pub struct SparseLu {
1988 n: usize,
1989 pivot_row: Vec<usize>,
1991 l_cols: Vec<Vec<(usize, f64)>>,
1994 u_cols: Vec<Vec<(usize, f64)>>,
1996 diag: Vec<f64>,
1998}
1999
2000#[cfg(feature = "alloc")]
2001impl SparseLu {
2002 pub fn factor(a: &CsrMatrix<f64>) -> Result<Self, SparseError> {
2010 if a.nrows() != a.ncols() {
2011 return Err(SparseError::DimensionMismatch {
2012 what: "operands have incompatible dimensions",
2013 });
2014 }
2015 let n = a.nrows();
2016 let mut cols: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
2018 for (r, c, &v) in a.iter() {
2019 cols[c].push((r, v));
2020 }
2021
2022 const UNPIVOTED: usize = usize::MAX;
2023 let mut pinv = vec![UNPIVOTED; n];
2024 let mut pivot_row = Vec::with_capacity(n);
2025 let mut l_cols: Vec<Vec<(usize, f64)>> = Vec::with_capacity(n);
2026 let mut u_cols: Vec<Vec<(usize, f64)>> = Vec::with_capacity(n);
2027 let mut diag = Vec::with_capacity(n);
2028
2029 let mut x = vec![0.0; n];
2032 let mut touched = vec![false; n];
2033 let mut nz: Vec<usize> = Vec::new();
2034
2035 for (j, col) in cols.iter().enumerate() {
2036 nz.clear();
2037 for &(r, v) in col {
2038 x[r] = v;
2039 if !touched[r] {
2040 touched[r] = true;
2041 nz.push(r);
2042 }
2043 }
2044 let mut pending: alloc::collections::BTreeSet<usize> = nz
2046 .iter()
2047 .filter(|&&r| pinv[r] != UNPIVOTED)
2048 .map(|&r| pinv[r])
2049 .collect();
2050 let mut u_col = Vec::new();
2051 while let Some(k) = pending.pop_first() {
2052 let xk = x[pivot_row[k]];
2053 if xk == 0.0 {
2054 continue;
2055 }
2056 u_col.push((k, xk));
2057 for &(i, l) in &l_cols[k] {
2058 if !touched[i] {
2059 touched[i] = true;
2060 nz.push(i);
2061 }
2062 x[i] -= l * xk;
2063 if pinv[i] != UNPIVOTED {
2064 pending.insert(pinv[i]);
2065 }
2066 }
2067 }
2068
2069 let mut best: Option<(usize, f64)> = None;
2071 for &r in &nz {
2072 if pinv[r] == UNPIVOTED && best.is_none_or(|(_, b)| x[r].abs() > b.abs()) {
2073 best = Some((r, x[r]));
2074 }
2075 }
2076 let (p, pivot) = match best {
2077 Some((p, v)) if v != 0.0 && v.is_finite() => (p, v),
2078 _ => {
2079 for &r in &nz {
2080 x[r] = 0.0;
2081 touched[r] = false;
2082 }
2083 return Err(SparseError::Breakdown { iterations: j });
2084 }
2085 };
2086 pinv[p] = j;
2087 pivot_row.push(p);
2088 diag.push(pivot);
2089 let l_col: Vec<(usize, f64)> = nz
2090 .iter()
2091 .filter(|&&r| pinv[r] == UNPIVOTED && x[r] != 0.0)
2092 .map(|&r| (r, x[r] / pivot))
2093 .collect();
2094 l_cols.push(l_col);
2095 u_cols.push(u_col);
2096
2097 for &r in &nz {
2098 x[r] = 0.0;
2099 touched[r] = false;
2100 }
2101 }
2102 Ok(SparseLu {
2103 n,
2104 pivot_row,
2105 l_cols,
2106 u_cols,
2107 diag,
2108 })
2109 }
2110
2111 pub fn dim(&self) -> usize {
2113 self.n
2114 }
2115
2116 pub fn nnz(&self) -> usize {
2119 self.l_cols.iter().map(Vec::len).sum::<usize>()
2120 + self.u_cols.iter().map(Vec::len).sum::<usize>()
2121 + self.n
2122 }
2123
2124 pub fn solve(&self, b: &DVector<f64>) -> Result<DVector<f64>, SparseError> {
2130 if b.len() != self.n {
2131 return Err(SparseError::DimensionMismatch {
2132 what: "operands have incompatible dimensions",
2133 });
2134 }
2135 let mut w: Vec<f64> = b.as_slice().to_vec();
2137 let mut z = vec![0.0; self.n];
2138 for k in 0..self.n {
2139 let yk = w[self.pivot_row[k]];
2140 z[k] = yk;
2141 for &(i, l) in &self.l_cols[k] {
2142 w[i] -= l * yk;
2143 }
2144 }
2145 for j in (0..self.n).rev() {
2148 let xj = z[j] / self.diag[j];
2149 z[j] = xj;
2150 for &(k, u) in &self.u_cols[j] {
2151 z[k] -= u * xj;
2152 }
2153 }
2154 Ok(DVector::from_vec(z))
2155 }
2156}
2157
2158#[cfg(test)]
2159mod lu_tests {
2160 use super::*;
2161 use tpt_math_linalg_dense::DMatrix;
2162
2163 fn from_dense(rows: &[&[f64]]) -> CsrMatrix<f64> {
2164 let mut coo = CooMatrix::<f64>::new(rows.len(), rows[0].len());
2165 for (i, row) in rows.iter().enumerate() {
2166 for (j, &v) in row.iter().enumerate() {
2167 if v != 0.0 {
2168 coo.push(i, j, v);
2169 }
2170 }
2171 }
2172 coo.to_csr()
2173 }
2174
2175 fn convection_like(n: usize) -> CsrMatrix<f64> {
2178 let mut coo = CooMatrix::<f64>::new(n, n);
2179 for i in 0..n {
2180 coo.push(i, i, 4.0);
2181 if i + 1 < n {
2182 coo.push(i, i + 1, -1.3);
2183 coo.push(i + 1, i, -0.7);
2184 }
2185 if i + 5 < n {
2186 coo.push(i, i + 5, 0.4);
2187 }
2188 if i >= 3 {
2189 coo.push(i, i - 3, -0.2);
2190 }
2191 }
2192 coo.to_csr()
2193 }
2194
2195 fn residual_norm(a: &CsrMatrix<f64>, x: &DVector<f64>, b: &DVector<f64>) -> f64 {
2196 let ax = a.matvec(x).unwrap();
2197 b.iter()
2198 .zip(ax.iter())
2199 .map(|(&bi, &ai)| (bi - ai) * (bi - ai))
2200 .sum::<f64>()
2201 .sqrt()
2202 }
2203
2204 #[test]
2205 fn solves_matrix_whose_leading_entry_is_zero() {
2206 let a = from_dense(&[&[0.0, 2.0, 1.0], &[1.0, 1.0, 0.0], &[2.0, 0.0, 3.0]]);
2208 let x_true = DVector::from_vec(vec![1.0, -2.0, 0.5]);
2209 let b = a.matvec(&x_true).unwrap();
2210 let lu = SparseLu::factor(&a).unwrap();
2211 let x = lu.solve(&b).unwrap();
2212 for i in 0..3 {
2213 assert!((x[i] - x_true[i]).abs() < 1e-12, "entry {i}: {}", x[i]);
2214 }
2215 }
2216
2217 #[test]
2218 fn agrees_with_dense_lu_on_small_matrix() {
2219 let rows: [&[f64]; 4] = [
2220 &[1.0, 4.0, 0.0, 2.0],
2221 &[3.0, 0.5, 1.0, 0.0],
2222 &[0.0, 2.0, 6.0, 1.0],
2223 &[5.0, 0.0, 1.0, 2.0],
2224 ];
2225 let a = from_dense(&rows);
2226 let dense = DMatrix::from_fn(4, 4, |i, j| rows[i][j]);
2227 let b = DVector::from_vec(vec![1.0, -1.0, 2.0, 0.25]);
2228 let expected = dense.solve(&b).unwrap();
2229 let x = SparseLu::factor(&a).unwrap().solve(&b).unwrap();
2230 for i in 0..4 {
2231 assert!((x[i] - expected[i]).abs() < 1e-12, "entry {i}");
2232 }
2233 }
2234
2235 #[test]
2236 fn small_residual_on_nonsymmetric_band_system() {
2237 let n = 120;
2238 let a = convection_like(n);
2239 let b = DVector::from_fn(n, |i| ((i as f64) * 0.21).cos());
2240 let lu = SparseLu::factor(&a).unwrap();
2241 let x = lu.solve(&b).unwrap();
2242 let r = residual_norm(&a, &x, &b);
2243 assert!(r < 1e-10, "residual {r}");
2244 assert!(lu.nnz() > a.nnz());
2246 }
2247
2248 #[test]
2249 fn factor_is_reusable_for_several_right_hand_sides() {
2250 let n = 40;
2251 let a = convection_like(n);
2252 let lu = SparseLu::factor(&a).unwrap();
2253 for seed in 0..3 {
2254 let b = DVector::from_fn(n, |i| ((i + seed) as f64).sin());
2255 let x = lu.solve(&b).unwrap();
2256 assert!(residual_norm(&a, &x, &b) < 1e-10, "seed {seed}");
2257 }
2258 }
2259
2260 #[test]
2261 fn singular_matrix_is_reported_as_breakdown() {
2262 let a = from_dense(&[&[1.0, 2.0], &[2.0, 4.0]]);
2264 assert!(matches!(
2265 SparseLu::factor(&a),
2266 Err(SparseError::Breakdown { .. })
2267 ));
2268 }
2269
2270 #[test]
2271 fn rejects_non_square_and_wrong_rhs_length() {
2272 let rect = CooMatrix::<f64>::new(2, 3).to_csr();
2273 assert!(matches!(
2274 SparseLu::factor(&rect),
2275 Err(SparseError::DimensionMismatch {
2276 what: "operands have incompatible dimensions"
2277 })
2278 ));
2279 let lu = SparseLu::factor(&from_dense(&[&[2.0, 0.0], &[0.0, 2.0]])).unwrap();
2280 assert!(matches!(
2281 lu.solve(&DVector::from_vec(vec![1.0])),
2282 Err(SparseError::DimensionMismatch {
2283 what: "operands have incompatible dimensions"
2284 })
2285 ));
2286 }
2287}
2288
2289#[cfg(test)]
2290mod ic0_tests {
2291 use super::*;
2292
2293 fn tridiagonal_spd(n: usize) -> CsrMatrix<f64> {
2294 let mut coo = CooMatrix::<f64>::new(n, n);
2295 for i in 0..n {
2296 coo.push(i, i, 4.0);
2297 if i + 1 < n {
2298 coo.push(i, i + 1, -1.0);
2299 coo.push(i + 1, i, -1.0);
2300 }
2301 }
2302 coo.to_csr()
2303 }
2304
2305 fn laplacian_2d(m: usize) -> CsrMatrix<f64> {
2306 let n = m * m;
2307 let mut coo = CooMatrix::<f64>::new(n, n);
2308 for r in 0..m {
2309 for c in 0..m {
2310 let i = r * m + c;
2311 coo.push(i, i, 4.0);
2312 if c + 1 < m {
2313 coo.push(i, i + 1, -1.0);
2314 coo.push(i + 1, i, -1.0);
2315 }
2316 if r + 1 < m {
2317 coo.push(i, i + m, -1.0);
2318 coo.push(i + m, i, -1.0);
2319 }
2320 }
2321 }
2322 coo.to_csr()
2323 }
2324
2325 #[test]
2326 fn exact_when_cholesky_has_no_fill_in() {
2327 let a = tridiagonal_spd(8);
2330 let x_true = DVector::from_fn(8, |i| (i as f64 + 1.0).ln());
2331 let b = a.matvec(&x_true).unwrap();
2332 let ic = Ic0::factor(&a).unwrap();
2333 let x = ic.apply(&b).unwrap();
2334 for i in 0..8 {
2335 assert!((x[i] - x_true[i]).abs() < 1e-12, "entry {i}");
2336 }
2337 }
2338
2339 #[test]
2340 fn pcg_with_ic0_solves_2d_laplacian() {
2341 let a = laplacian_2d(12);
2342 let n = a.nrows();
2343 let x_true = DVector::from_fn(n, |i| (i as f64 * 0.37).sin());
2344 let b = a.matvec(&x_true).unwrap();
2345 let x = ic0_preconditioned_cg(&a, &b, None, 1e-12, 500).unwrap();
2346 for i in 0..n {
2347 assert!((x[i] - x_true[i]).abs() < 1e-8, "entry {i}");
2348 }
2349 }
2350
2351 #[test]
2352 fn ic0_preconditioning_needs_fewer_iterations_than_plain_cg() {
2353 let a = laplacian_2d(20);
2356 let n = a.nrows();
2357 let b = DVector::from_fn(n, |i| if i % 3 == 0 { 1.0 } else { -0.5 });
2358 let budget = |solve: &dyn Fn(usize) -> bool| (1..=400).find(|&k| solve(k)).unwrap();
2359 let plain = budget(&|k| conjugate_gradient(&a, &b, None, 1e-10, k).is_ok());
2360 let precond = budget(&|k| ic0_preconditioned_cg(&a, &b, None, 1e-10, k).is_ok());
2361 assert!(precond < plain, "preconditioned {precond} vs plain {plain}");
2362 }
2363
2364 #[test]
2365 fn rejects_non_positive_pivot() {
2366 let mut coo = CooMatrix::<f64>::new(2, 2);
2368 coo.push(0, 0, 1.0);
2369 coo.push(0, 1, 2.0);
2370 coo.push(1, 0, 2.0);
2371 coo.push(1, 1, 1.0);
2372 assert!(matches!(
2373 Ic0::factor(&coo.to_csr()),
2374 Err(SparseError::Breakdown { .. })
2375 ));
2376 }
2377
2378 #[test]
2379 fn rejects_non_square_and_missing_diagonal() {
2380 let rect = CooMatrix::<f64>::new(2, 3).to_csr();
2381 assert!(matches!(
2382 Ic0::factor(&rect),
2383 Err(SparseError::DimensionMismatch {
2384 what: "operands have incompatible dimensions"
2385 })
2386 ));
2387 let mut coo = CooMatrix::<f64>::new(2, 2);
2388 coo.push(0, 0, 2.0);
2389 coo.push(1, 0, 0.5);
2390 assert!(Ic0::factor(&coo.to_csr()).is_err());
2391 }
2392}
2393
2394#[cfg(test)]
2395mod ilu_tests {
2396 use super::*;
2397
2398 fn tridiagonal(n: usize) -> CsrMatrix<f64> {
2399 let mut coo = CooMatrix::<f64>::new(n, n);
2400 for i in 0..n {
2401 coo.push(i, i, 4.0);
2402 if i + 1 < n {
2403 coo.push(i, i + 1, -1.0);
2404 coo.push(i + 1, i, -1.0);
2405 }
2406 }
2407 coo.to_csr()
2408 }
2409
2410 #[test]
2411 fn exact_when_lu_has_no_fill_in() {
2412 let a = tridiagonal(8);
2414 let x_true = DVector::from_fn(8, |i| (i as f64 + 1.0).ln());
2415 let b = a.matvec(&x_true).unwrap();
2416 let ilu = Ilu0::factor(&a).unwrap();
2417 let x = ilu.apply(&b).unwrap();
2418 assert!((x - x_true).norm() < 1e-12);
2419 }
2420
2421 #[test]
2422 fn approximate_inverse_reduces_residual_on_laplacian() {
2423 let m = 6;
2426 let n = m * m;
2427 let mut coo = CooMatrix::<f64>::new(n, n);
2428 for r in 0..m {
2429 for c in 0..m {
2430 let k = r * m + c;
2431 coo.push(k, k, 4.0);
2432 if c > 0 {
2433 coo.push(k, k - 1, -1.0);
2434 }
2435 if c + 1 < m {
2436 coo.push(k, k + 1, -1.0);
2437 }
2438 if r > 0 {
2439 coo.push(k, k - m, -1.0);
2440 }
2441 if r + 1 < m {
2442 coo.push(k, k + m, -1.0);
2443 }
2444 }
2445 }
2446 let a = coo.to_csr();
2447 let b = DVector::from_fn(n, |i| if i % 3 == 0 { 1.0 } else { -0.5 });
2448 let ilu = Ilu0::factor(&a).unwrap();
2449 let x = ilu.apply(&b).unwrap();
2450 let residual = (b.clone() - a.matvec(&x).unwrap()).norm();
2451 assert!(
2452 residual < 0.5 * b.norm(),
2453 "residual {residual} vs |b| {}",
2454 b.norm()
2455 );
2456 }
2457
2458 #[test]
2459 fn missing_diagonal_is_a_breakdown() {
2460 let mut coo = CooMatrix::<f64>::new(2, 2);
2461 coo.push(0, 0, 1.0);
2462 coo.push(0, 1, 1.0);
2463 coo.push(1, 0, 1.0);
2464 assert_eq!(
2465 Ilu0::factor(&coo.to_csr()),
2466 Err(SparseError::Breakdown { iterations: 1 })
2467 );
2468 }
2469}
2470
2471#[cfg(test)]
2472mod cholesky_tests {
2473 use super::*;
2474
2475 fn laplacian_2d(m: usize) -> CsrMatrix<f64> {
2477 let n = m * m;
2478 let mut coo = CooMatrix::<f64>::new(n, n);
2479 for r in 0..m {
2480 for c in 0..m {
2481 let k = r * m + c;
2482 coo.push(k, k, 4.0);
2483 if c > 0 {
2484 coo.push(k, k - 1, -1.0);
2485 }
2486 if c + 1 < m {
2487 coo.push(k, k + 1, -1.0);
2488 }
2489 if r > 0 {
2490 coo.push(k, k - m, -1.0);
2491 }
2492 if r + 1 < m {
2493 coo.push(k, k + m, -1.0);
2494 }
2495 }
2496 }
2497 coo.to_csr()
2498 }
2499
2500 #[test]
2501 fn solves_2d_laplacian_and_matches_cg() {
2502 let a = laplacian_2d(6);
2503 let n = a.nrows();
2504 let x_true = DVector::from_fn(n, |i| (i as f64 * 0.37).sin());
2505 let b = a.matvec(&x_true).unwrap();
2506 let factor = SparseCholesky::factor(&a).unwrap();
2507 let x = factor.solve(&b).unwrap();
2508 assert!((x.clone() - x_true.clone()).norm() < 1e-10);
2509 let cg = conjugate_gradient(&a, &b, None, 1e-13, 1000).unwrap();
2510 assert!((x - cg).norm() < 1e-8);
2511 }
2512
2513 #[test]
2514 fn factor_is_reusable_for_several_right_hand_sides() {
2515 let a = laplacian_2d(4);
2516 let factor = SparseCholesky::factor(&a).unwrap();
2517 for seed in 1..4 {
2518 let x_true = DVector::from_fn(a.nrows(), |i| ((i + seed) as f64).cos());
2519 let b = a.matvec(&x_true).unwrap();
2520 let x = factor.solve(&b).unwrap();
2521 assert!((x - x_true).norm() < 1e-10);
2522 }
2523 }
2524
2525 #[test]
2526 fn rejects_indefinite_matrix() {
2527 let mut coo = CooMatrix::<f64>::new(2, 2);
2528 coo.push(0, 0, 1.0);
2529 coo.push(1, 1, -1.0);
2530 assert_eq!(
2531 SparseCholesky::factor(&coo.to_csr()),
2532 Err(SparseError::Breakdown { iterations: 1 })
2533 );
2534 }
2535
2536 #[test]
2537 fn rejects_wrong_rhs_length() {
2538 let factor = SparseCholesky::factor(&laplacian_2d(2)).unwrap();
2539 assert_eq!(
2540 factor.solve(&DVector::from_vec(vec![1.0])),
2541 Err(SparseError::DimensionMismatch {
2542 what: "operands have incompatible dimensions"
2543 })
2544 );
2545 }
2546}
2547
2548#[cfg(test)]
2549mod preconditioner_tests {
2550 use super::*;
2551
2552 fn scaled_tridiagonal(n: usize) -> CsrMatrix<f64> {
2554 let mut coo = CooMatrix::<f64>::new(n, n);
2555 for i in 0..n {
2556 let d = 1.0 + 10_000.0 * (i as f64 / (n - 1) as f64);
2557 coo.push(i, i, d);
2558 if i + 1 < n {
2559 coo.push(i, i + 1, 0.5);
2560 coo.push(i + 1, i, 0.5);
2561 }
2562 }
2563 coo.to_csr()
2564 }
2565
2566 #[test]
2567 fn solves_badly_scaled_spd_system() {
2568 let n = 50;
2569 let a = scaled_tridiagonal(n);
2570 let x_true = DVector::from_fn(n, |i| (i as f64 * 0.3).cos());
2571 let b = a.matvec(&x_true).unwrap();
2572 let x = jacobi_preconditioned_cg(&a, &b, None, 1e-12, 500).unwrap();
2573 let err = (x - x_true).norm();
2574 assert!(err < 1e-8, "error {err}");
2575 }
2576
2577 #[test]
2578 fn zero_diagonal_is_a_breakdown() {
2579 let mut coo = CooMatrix::<f64>::new(2, 2);
2580 coo.push(0, 1, 1.0);
2581 coo.push(1, 0, 1.0);
2582 coo.push(1, 1, 2.0);
2583 let a = coo.to_csr();
2584 let b = DVector::from_vec(vec![1.0, 1.0]);
2585 assert_eq!(
2586 jacobi_preconditioned_cg(&a, &b, None, 1e-10, 10),
2587 Err(SparseError::Breakdown { iterations: 0 })
2588 );
2589 }
2590}
2591
2592#[cfg(test)]
2593mod gmres_tests {
2594 use super::*;
2595
2596 fn tridiagonal_3() -> CsrMatrix<f64> {
2597 let mut coo = CooMatrix::<f64>::new(3, 3);
2598 for &(r, c, v) in &[
2599 (0, 0, 4.0),
2600 (0, 1, 1.0),
2601 (1, 0, 2.0),
2602 (1, 1, 5.0),
2603 (1, 2, 1.0),
2604 (2, 1, 1.0),
2605 (2, 2, 3.0),
2606 ] {
2607 coo.push(r, c, v);
2608 }
2609 coo.to_csr()
2610 }
2611
2612 #[test]
2613 fn solves_non_symmetric_system_in_one_cycle() {
2614 let a = tridiagonal_3();
2615 let b = DVector::from_vec(vec![6.0, 15.0, 11.0]);
2616 let x = gmres(&a, &b, None, 1e-12, 3, 100).unwrap();
2617 for (got, want) in x.as_slice().iter().zip([1.0, 2.0, 3.0]) {
2618 assert!((got - want).abs() < 1e-9, "{:?}", x.as_slice());
2619 }
2620 }
2621
2622 #[test]
2623 fn restarted_cycles_converge_on_diagonally_dominant_system() {
2624 let n = 30;
2626 let mut coo = CooMatrix::<f64>::new(n, n);
2627 for i in 0..n {
2628 coo.push(i, i, 4.0);
2629 if i + 1 < n {
2630 coo.push(i, i + 1, -1.5);
2631 }
2632 if i >= 1 {
2633 coo.push(i, i - 1, -0.5);
2634 }
2635 }
2636 let a = coo.to_csr();
2637 let x_true = DVector::from_fn(n, |i| (i as f64 + 1.0).sin());
2638 let b = a.matvec(&x_true).unwrap();
2639 let x = gmres(&a, &b, None, 1e-12, 4, 500).unwrap();
2641 let err = (x - x_true).norm();
2642 assert!(err < 1e-8, "error {err}");
2643 }
2644
2645 #[test]
2646 fn reports_non_convergence() {
2647 let a = tridiagonal_3();
2648 let b = DVector::from_vec(vec![6.0, 15.0, 11.0]);
2649 assert_eq!(
2651 gmres(&a, &b, None, 1e-14, 1, 1),
2652 Err(SparseError::NotConverged { iterations: 1 })
2653 );
2654 }
2655
2656 #[test]
2657 fn ilu_preconditioning_converges_where_plain_gmres_runs_out_of_budget() {
2658 let m = 10;
2660 let n = m * m;
2661 let mut coo = CooMatrix::<f64>::new(n, n);
2662 for r in 0..m {
2663 for c in 0..m {
2664 let k = r * m + c;
2665 coo.push(k, k, 4.0);
2666 if c > 0 {
2667 coo.push(k, k - 1, -1.0);
2668 }
2669 if c + 1 < m {
2670 coo.push(k, k + 1, -1.0);
2671 }
2672 if r > 0 {
2673 coo.push(k, k - m, -1.0);
2674 }
2675 if r + 1 < m {
2676 coo.push(k, k + m, -1.0);
2677 }
2678 }
2679 }
2680 let a = coo.to_csr();
2681 let b = DVector::from_fn(n, |i| if i % 3 == 0 { 1.0 } else { -0.5 });
2682 assert!(matches!(
2685 gmres(&a, &b, None, 1e-10, 40, 20),
2686 Err(SparseError::NotConverged { .. })
2687 ));
2688 let x = gmres_ilu0(&a, &b, None, 1e-10, 40, 20).unwrap();
2689 let residual = (b.clone() - a.matvec(&x).unwrap()).norm();
2690 assert!(residual < 1e-8 * b.norm(), "residual {residual}");
2691 }
2692
2693 #[test]
2694 fn rejects_dimension_mismatch() {
2695 let a = tridiagonal_3();
2696 let b = DVector::from_vec(vec![1.0, 2.0]);
2697 assert_eq!(
2698 gmres(&a, &b, None, 1e-10, 3, 10),
2699 Err(SparseError::DimensionMismatch {
2700 what: "operands have incompatible dimensions"
2701 })
2702 );
2703 let b = DVector::from_vec(vec![1.0, 2.0, 3.0]);
2704 let bad_guess = DVector::from_vec(vec![0.0]);
2705 assert_eq!(
2706 gmres(&a, &b, Some(bad_guess), 1e-10, 3, 10),
2707 Err(SparseError::DimensionMismatch {
2708 what: "operands have incompatible dimensions"
2709 })
2710 );
2711 }
2712}
2713
2714#[cfg(test)]
2715mod tests {
2716 use super::*;
2717
2718 #[test]
2719 fn cg_tolerance_is_relative_to_rhs() {
2720 let a = dense_2x2_csr();
2723 let b = DVector::from_vec(vec![1e-12, 2e-12]);
2724 let x = conjugate_gradient(&a, &b, None, 1e-10, 100).unwrap();
2725 let resid = b.clone() - a.matvec(&x).unwrap();
2726 assert!(resid.norm() <= 1e-10 * b.norm());
2727 assert!(x.norm() > 0.0);
2728 }
2729
2730 #[test]
2731 fn cg_reports_breakdown_on_indefinite_matrix() {
2732 let mut coo = CooMatrix::<f64>::new(2, 2);
2734 coo.push(0, 0, 1.0);
2735 coo.push(1, 1, -1.0);
2736 let a = coo.to_csr();
2737 let b = DVector::from_vec(vec![1.0, 1.0]);
2738 assert_eq!(
2739 conjugate_gradient(&a, &b, None, 1e-12, 10),
2740 Err(SparseError::Breakdown { iterations: 0 })
2741 );
2742 }
2743
2744 #[test]
2745 fn matvec_into_matches_matvec_and_checks_lengths() {
2746 let a = dense_2x2_csr();
2747 let x = [1.0, 2.0];
2748 let mut y = [0.0; 2];
2749 a.matvec_into(&x, &mut y).unwrap();
2750 assert_eq!(y, [6.0, 7.0]);
2752 let reference = a.matvec(&DVector::from_vec(x.to_vec())).unwrap();
2753 assert_eq!(reference.as_slice(), &y);
2754 let mut short = [0.0; 1];
2755 assert_eq!(
2756 a.matvec_into(&x, &mut short),
2757 Err(SparseError::DimensionMismatch {
2758 what: "operands have incompatible dimensions"
2759 })
2760 );
2761 assert_eq!(
2762 a.matvec_into(&[1.0], &mut y),
2763 Err(SparseError::DimensionMismatch {
2764 what: "operands have incompatible dimensions"
2765 })
2766 );
2767 }
2768
2769 fn dense_2x2_csr() -> CsrMatrix<f64> {
2770 let mut coo = CooMatrix::<f64>::new(2, 2);
2771 coo.push(0, 0, 4.0);
2772 coo.push(0, 1, 1.0);
2773 coo.push(1, 0, 1.0);
2774 coo.push(1, 1, 3.0);
2775 coo.to_csr()
2776 }
2777
2778 #[test]
2779 fn coo_to_csr_roundtrip_and_duplicate_sum() {
2780 let mut coo = CooMatrix::<f64>::new(2, 2);
2781 coo.push(0, 0, 1.0);
2784 coo.push(1, 1, 5.0);
2785 coo.push(0, 0, 2.0);
2786 coo.push(0, 1, 7.0);
2787 coo.push(1, 0, 9.0);
2788 let csr = coo.to_csr();
2789 assert_eq!(csr.nrows(), 2);
2790 assert_eq!(csr.ncols(), 2);
2791 assert_eq!(csr.nnz(), 4);
2792 assert_eq!(csr.row_ptr, vec![0, 2, 4]);
2794 assert_eq!(csr.col_idx, vec![0, 1, 0, 1]);
2795 assert_eq!(csr.values, vec![3.0, 7.0, 9.0, 5.0]);
2796
2797 let csc = coo.to_csc();
2798 assert_eq!(csc.col_ptr, vec![0, 2, 4]);
2799 assert_eq!(csc.row_idx, vec![0, 1, 0, 1]);
2800 assert_eq!(csc.values, vec![3.0, 9.0, 7.0, 5.0]);
2801 }
2802
2803 #[test]
2804 fn counting_sort_conversion_matches_dense_accumulation() {
2805 let entries = [
2807 (2usize, 1usize, 1.5_f64),
2808 (0, 3, 2.0),
2809 (2, 1, -0.5),
2810 (1, 0, 4.0),
2811 (0, 0, 1.0),
2812 (2, 3, 3.0),
2813 (0, 3, 0.25),
2814 ];
2815 let (nrows, ncols) = (3, 4);
2816 let mut dense = [[0.0_f64; 4]; 3];
2817 for &(r, c, v) in &entries {
2818 dense[r][c] += v;
2819 }
2820 let mut coo = CooMatrix::new(nrows, ncols);
2821 for &(r, c, v) in &entries {
2822 coo.push(r, c, v);
2823 }
2824 let csr = coo.to_csr();
2825 let csc = coo.to_csc();
2826 assert_eq!(csr.nnz(), 5);
2827 assert_eq!(csc.nnz(), 5);
2828 for (i, row) in dense.iter().enumerate() {
2829 for (j, &expected) in row.iter().enumerate() {
2830 let from_csr: f64 = csr
2831 .iter()
2832 .filter(|e| e.0 == i && e.1 == j)
2833 .map(|e| *e.2)
2834 .sum();
2835 let from_csc: f64 = csc
2836 .iter()
2837 .filter(|e| e.0 == i && e.1 == j)
2838 .map(|e| *e.2)
2839 .sum();
2840 assert_eq!(from_csr, expected, "CSR ({i},{j})");
2841 assert_eq!(from_csc, expected, "CSC ({i},{j})");
2842 }
2843 }
2844 let mut prev: Option<(usize, usize)> = None;
2846 for (r, c, _) in csr.iter() {
2847 if let Some((pr, pc)) = prev {
2848 assert!(r > pr || (r == pr && c > pc), "order at ({r},{c})");
2849 }
2850 prev = Some((r, c));
2851 }
2852 }
2853
2854 #[test]
2855 fn spmv_against_known_matrix() {
2856 let a = dense_2x2_csr();
2857 let x = DVector::from_vec(vec![2.0_f64, -1.0]);
2858 let y = a.matvec(&x).unwrap();
2860 assert_eq!(y, DVector::from_vec(vec![7.0, -1.0]));
2861 let y2 = &a * &x;
2863 assert_eq!(y, y2);
2864 }
2865
2866 #[test]
2867 fn spmv_dimension_mismatch() {
2868 let a = dense_2x2_csr();
2869 let x = DVector::from_vec(vec![1.0_f64]);
2870 assert_eq!(
2871 a.matvec(&x),
2872 Err(SparseError::DimensionMismatch {
2873 what: "operands have incompatible dimensions"
2874 })
2875 );
2876 }
2877
2878 #[test]
2879 fn transpose_csr_to_csc_and_back() {
2880 let a = dense_2x2_csr();
2881 let csc = a.transpose();
2882 assert_eq!(csc.col_ptr, vec![0, 2, 4]);
2884 assert_eq!(csc.row_idx, vec![0, 1, 0, 1]);
2885 assert_eq!(csc.values, vec![4.0, 1.0, 1.0, 3.0]);
2886 let back = csc.transpose();
2887 assert_eq!(back.row_ptr, vec![0, 2, 4]);
2888 assert_eq!(back.col_idx, vec![0, 1, 0, 1]);
2889 assert_eq!(back.values, vec![4.0, 1.0, 1.0, 3.0]);
2890 }
2891
2892 #[test]
2893 fn cg_solves_spd_system() {
2894 let a = dense_2x2_csr();
2895 let b = DVector::from_vec(vec![1.0_f64, 2.0]);
2896 let x = conjugate_gradient(&a, &b, None, 1e-12, 100).unwrap();
2897 let expected = DVector::from_vec(vec![1.0 / 11.0, 7.0 / 11.0]);
2898 assert!((x[0] - expected[0]).abs() < 1e-10);
2899 assert!((x[1] - expected[1]).abs() < 1e-10);
2900 let r = b - a.matvec(&x).unwrap();
2902 assert!(r.norm() < 1e-10);
2903 }
2904
2905 #[test]
2906 fn to_csr_preserves_declared_dimensions() {
2907 let empty = CooMatrix::<f64>::new(3, 3).to_csr();
2909 assert_eq!((empty.nrows(), empty.ncols()), (3, 3));
2910 let mut coo = CooMatrix::<f64>::new(2, 5);
2911 coo.push(0, 1, 2.0);
2912 let a = coo.to_csr();
2913 assert_eq!(a.ncols(), 5);
2914 let x = DVector::from_vec(vec![1.0_f64; 5]);
2915 assert_eq!(a.matvec(&x).unwrap().len(), 2);
2916 assert_eq!(a.transpose().nrows(), 5);
2917 }
2918
2919 #[test]
2920 fn transpose_non_square_dimensions() {
2921 let mut coo = CooMatrix::<f64>::new(2, 3);
2923 coo.push(0, 0, 1.0);
2924 coo.push(0, 2, 2.0);
2925 coo.push(1, 1, 3.0);
2926 let a = coo.to_csr();
2927 let csc = a.transpose();
2928 assert_eq!(csc.nrows(), 3);
2929 assert_eq!(csc.ncols(), 2);
2930 assert_eq!(csc.col_ptr, vec![0, 2, 3]);
2932 assert_eq!(csc.row_idx, vec![0, 2, 1]);
2933 assert_eq!(csc.values, vec![1.0, 2.0, 3.0]);
2934 let back = csc.transpose();
2935 assert_eq!(back.nrows(), 2);
2936 assert_eq!(back.ncols(), 3);
2937 assert_eq!(back.row_ptr, vec![0, 2, 3]);
2938 assert_eq!(back.col_idx, vec![0, 2, 1]);
2939 assert_eq!(back.values, vec![1.0, 2.0, 3.0]);
2940 }
2941
2942 #[test]
2943 fn krylov_rejects_wrong_length_initial_guess() {
2944 let a = dense_2x2_csr();
2946 let b = DVector::from_vec(vec![1.0_f64, 2.0]);
2947 let bad = DVector::from_vec(vec![0.0_f64; 3]);
2948 assert_eq!(
2949 conjugate_gradient(&a, &b, Some(bad.clone()), 1e-10, 10).unwrap_err(),
2950 SparseError::DimensionMismatch {
2951 what: "operands have incompatible dimensions"
2952 }
2953 );
2954 assert_eq!(
2955 bicgstab(&a, &b, Some(bad), 1e-10, 10).unwrap_err(),
2956 SparseError::DimensionMismatch {
2957 what: "operands have incompatible dimensions"
2958 }
2959 );
2960 }
2961
2962 #[test]
2963 fn cg_non_convergence_reports_error() {
2964 let a = dense_2x2_csr();
2965 let b = DVector::from_vec(vec![1.0_f64, 2.0]);
2966 let res = conjugate_gradient(&a, &b, None, 1e-14, 1);
2968 assert!(matches!(
2969 res,
2970 Err(SparseError::NotConverged { iterations: 1 })
2971 ));
2972 }
2973
2974 #[test]
2975 fn bicgstab_non_convergence_reports_error() {
2976 let a = dense_2x2_csr();
2977 let b = DVector::from_vec(vec![1.0_f64, 2.0]);
2978 let res = bicgstab(&a, &b, None, 1e-14, 1);
2979 assert!(matches!(
2980 res,
2981 Err(SparseError::NotConverged { iterations: 1 })
2982 ));
2983 }
2984
2985 #[test]
2986 fn csc_matvec_matches_csr() {
2987 let mut coo = CooMatrix::<f64>::new(2, 2);
2989 coo.push(0, 0, 4.0);
2990 coo.push(0, 1, 1.0);
2991 coo.push(1, 0, 1.0);
2992 coo.push(1, 1, 3.0);
2993 let csc = coo.to_csc();
2994 let x = DVector::from_vec(vec![2.0_f64, -1.0]);
2995 let y = csc.matvec(&x).unwrap();
2996 assert_eq!(y, DVector::from_vec(vec![7.0, -1.0]));
2997 }
2998
2999 #[test]
3000 fn cg_2d_laplacian() {
3001 let n = 9usize;
3003 let mut coo = CooMatrix::<f64>::new(n, n);
3004 for r in 0..3 {
3005 for c in 0..3 {
3006 let i = r * 3 + c;
3007 coo.push(i, i, 4.0);
3008 if r > 0 {
3009 coo.push(i, i - 3, -1.0);
3010 }
3011 if r < 2 {
3012 coo.push(i, i + 3, -1.0);
3013 }
3014 if c > 0 {
3015 coo.push(i, i - 1, -1.0);
3016 }
3017 if c < 2 {
3018 coo.push(i, i + 1, -1.0);
3019 }
3020 }
3021 }
3022 let a = coo.to_csr();
3023 let b = DVector::from_vec(vec![1.0; n]);
3024 let x = conjugate_gradient(&a, &b, None, 1e-10, 1000).unwrap();
3025 let r = b - a.matvec(&x).unwrap();
3026 assert!(r.norm() < 1e-8);
3027 }
3028
3029 #[test]
3030 fn bicgstab_solves_nonsymmetric() {
3031 let mut coo = CooMatrix::<f64>::new(2, 2);
3033 coo.push(0, 0, 2.0);
3034 coo.push(0, 1, 1.0);
3035 coo.push(1, 0, 3.0); coo.push(1, 1, 4.0);
3037 let a = coo.to_csr();
3038 let b = DVector::from_vec(vec![4.0_f64, 11.0]);
3040 let x = bicgstab(&a, &b, None, 1e-12, 200).unwrap();
3041 assert!((x[0] - 1.0).abs() < 1e-9);
3042 assert!((x[1] - 2.0).abs() < 1e-9);
3043 }
3044
3045 #[test]
3046 fn solver_dimension_mismatch() {
3047 let a = dense_2x2_csr();
3048 let b = DVector::from_vec(vec![1.0_f64]);
3049 assert_eq!(
3050 conjugate_gradient(&a, &b, None, 1e-12, 10),
3051 Err(SparseError::DimensionMismatch {
3052 what: "operands have incompatible dimensions"
3053 })
3054 );
3055 assert_eq!(
3056 bicgstab(&a, &b, None, 1e-12, 10),
3057 Err(SparseError::DimensionMismatch {
3058 what: "operands have incompatible dimensions"
3059 })
3060 );
3061 }
3062}
3063
3064#[cfg(test)]
3065mod report_tests {
3066 use super::*;
3067
3068 fn laplacian_1d(n: usize) -> CsrMatrix<f64> {
3069 let mut coo = CooMatrix::<f64>::new(n, n);
3070 for i in 0..n {
3071 coo.push(i, i, 2.0);
3072 if i + 1 < n {
3073 coo.push(i, i + 1, -1.0);
3074 coo.push(i + 1, i, -1.0);
3075 }
3076 }
3077 coo.to_csr()
3078 }
3079
3080 #[test]
3081 fn cg_report_on_convergence_counts_iterations() {
3082 let a = laplacian_1d(20);
3083 let b = DVector::from_fn(20, |i| (i as f64).sin());
3084 let (x, report) = conjugate_gradient_with_report(&a, &b, None, 1e-10, 500).unwrap();
3085 assert_eq!(report.status, SolveStatus::Converged);
3086 assert!(report.iterations > 0 && report.iterations <= 20);
3087 assert!(report.residual <= 1e-10 * b.norm());
3088 let ax = a.matvec(&x).unwrap();
3089 assert!((ax[3] - b[3]).abs() < 1e-8);
3090 }
3091
3092 #[test]
3093 fn cg_report_on_budget_exhaustion_is_ok_not_err() {
3094 let a = laplacian_1d(50);
3095 let b = DVector::from_fn(50, |i| (i as f64 * 0.1).cos());
3096 let (_, report) = conjugate_gradient_with_report(&a, &b, None, 1e-14, 2).unwrap();
3097 assert_eq!(report.status, SolveStatus::NotConverged);
3098 assert_eq!(report.iterations, 2);
3099 assert!(matches!(
3101 conjugate_gradient(&a, &b, None, 1e-14, 2),
3102 Err(SparseError::NotConverged { iterations: 2 })
3103 ));
3104 }
3105
3106 #[test]
3107 fn cg_report_on_indefinite_matrix_is_breakdown() {
3108 let mut coo = CooMatrix::<f64>::new(2, 2);
3109 coo.push(0, 0, 1.0);
3110 coo.push(1, 1, -1.0);
3111 let a = coo.to_csr();
3112 let b = DVector::from_vec(vec![1.0, 1.0]);
3113 let (_, report) = conjugate_gradient_with_report(&a, &b, None, 1e-12, 10).unwrap();
3114 assert_eq!(report.status, SolveStatus::Breakdown);
3115 }
3116
3117 #[test]
3118 fn bicgstab_report_matches_plain_solver() {
3119 let a = laplacian_1d(15);
3120 let b = DVector::from_fn(15, |i| 1.0 + i as f64);
3121 let (x, report) = bicgstab_with_report(&a, &b, None, 1e-10, 200).unwrap();
3122 assert!(report.status.is_converged());
3123 let plain = bicgstab(&a, &b, None, 1e-10, 200).unwrap();
3124 for i in 0..15 {
3125 assert!((x[i] - plain[i]).abs() < 1e-12);
3126 }
3127 let (_, starved) = bicgstab_with_report(&a, &b, None, 1e-14, 1).unwrap();
3128 assert_eq!(starved.status, SolveStatus::NotConverged);
3129 }
3130
3131 #[test]
3132 fn report_still_rejects_dimension_mismatch() {
3133 let a = laplacian_1d(3);
3134 let b = DVector::from_vec(vec![1.0, 2.0]);
3135 assert!(matches!(
3136 conjugate_gradient_with_report(&a, &b, None, 1e-8, 10),
3137 Err(SparseError::DimensionMismatch {
3138 what: "operands have incompatible dimensions"
3139 })
3140 ));
3141 }
3142}
3143
3144#[cfg(test)]
3145mod gmres_report_tests {
3146 use super::*;
3147
3148 fn nonsymmetric(n: usize) -> CsrMatrix<f64> {
3149 let mut coo = CooMatrix::<f64>::new(n, n);
3150 for i in 0..n {
3151 coo.push(i, i, 4.0);
3152 if i + 1 < n {
3153 coo.push(i, i + 1, -1.0);
3154 coo.push(i + 1, i, -0.5);
3155 }
3156 }
3157 coo.to_csr()
3158 }
3159
3160 #[test]
3161 fn gmres_report_converges_and_matches_plain_solver() {
3162 let a = nonsymmetric(12);
3163 let b = DVector::from_fn(12, |i| 1.0 + (i as f64) * 0.3);
3164 let (x, report) =
3165 gmres_right_preconditioned_with_report(&a, &b, None, 1e-10, 12, 200, |v: &[f64]| {
3166 Ok(v.to_vec())
3167 })
3168 .unwrap();
3169 assert!(report.status.is_converged());
3170 assert!(report.iterations > 0);
3171 assert!(report.residual <= 1e-10 * b.norm());
3172 let plain = gmres(&a, &b, None, 1e-10, 12, 200).unwrap();
3173 for i in 0..12 {
3174 assert!((x[i] - plain[i]).abs() < 1e-9);
3175 }
3176 }
3177
3178 #[test]
3179 fn gmres_report_on_budget_exhaustion_is_ok_with_status() {
3180 let a = nonsymmetric(12);
3181 let b = DVector::from_fn(12, |i| 1.0 + (i as f64) * 0.3);
3182 let (_, report) =
3183 gmres_right_preconditioned_with_report(&a, &b, None, 1e-14, 2, 2, |v: &[f64]| {
3184 Ok(v.to_vec())
3185 })
3186 .unwrap();
3187 assert_eq!(report.status, SolveStatus::NotConverged);
3188 assert_eq!(report.iterations, 2);
3189 }
3190}
3191
3192#[cfg(test)]
3193mod solver_path_tests {
3194 use super::*;
3198 use tpt_math_numeric::SolveStatus;
3199
3200 fn laplacian(m: usize) -> CsrMatrix<f64> {
3201 let n = m * m;
3202 let mut coo = CooMatrix::<f64>::new(n, n);
3203 for r in 0..m {
3204 for c in 0..m {
3205 let i = r * m + c;
3206 coo.push(i, i, 4.0);
3207 if c + 1 < m {
3208 coo.push(i, i + 1, -1.0);
3209 coo.push(i + 1, i, -1.0);
3210 }
3211 if r + 1 < m {
3212 coo.push(i, i + m, -1.0);
3213 coo.push(i + m, i, -1.0);
3214 }
3215 }
3216 }
3217 coo.to_csr()
3218 }
3219
3220 fn to_f32(a: &CsrMatrix<f64>) -> CsrMatrix<f32> {
3221 let mut coo = CooMatrix::<f32>::new(a.nrows(), a.ncols());
3222 for (r, c, v) in a.iter() {
3223 coo.push(r, c, *v as f32);
3224 }
3225 coo.to_csr()
3226 }
3227
3228 fn known_system(a: &CsrMatrix<f64>) -> (DVector<f64>, DVector<f64>) {
3230 let n = a.nrows();
3231 let xs = DVector::from_fn(n, |i| 1.0 + (i % 5) as f64 * 0.25);
3232 let b = a.matvec(&xs).unwrap();
3233 (xs, b)
3234 }
3235
3236 #[test]
3237 fn cg_f64_recovers_known_solution() {
3238 let a = laplacian(12);
3239 let (xs, b) = known_system(&a);
3240 let (x, rep) = conjugate_gradient_with_report(&a, &b, None, 1e-12, 1000).unwrap();
3241 assert_eq!(rep.status, SolveStatus::Converged);
3242 assert!(
3243 rep.iterations > 0 && rep.iterations < 200,
3244 "iters {}",
3245 rep.iterations
3246 );
3247 for (g, w) in x.as_slice().iter().zip(xs.as_slice()) {
3248 assert!((g - w).abs() < 1e-8, "{g} vs {w}");
3249 }
3250 }
3251
3252 #[test]
3253 fn bicgstab_f64_recovers_known_solution() {
3254 let a = laplacian(12);
3255 let (xs, b) = known_system(&a);
3256 let (x, rep) = bicgstab_with_report(&a, &b, None, 1e-12, 1000).unwrap();
3257 assert_eq!(rep.status, SolveStatus::Converged);
3258 for (g, w) in x.as_slice().iter().zip(xs.as_slice()) {
3259 assert!((g - w).abs() < 1e-8, "{g} vs {w}");
3260 }
3261 }
3262
3263 #[test]
3264 fn cg_and_bicgstab_f32_recover_known_solution() {
3265 let a64 = laplacian(10);
3266 let a = to_f32(&a64);
3267 let (xs64, b64) = known_system(&a64);
3268 let b = DVector::from_fn(b64.len(), |i| b64.as_slice()[i] as f32);
3269 let (cg_x, cg_rep) = conjugate_gradient_with_report(&a, &b, None, 1e-5, 1000).unwrap();
3270 let (bi_x, bi_rep) = bicgstab_with_report(&a, &b, None, 1e-5, 1000).unwrap();
3271 for (x, rep) in [(cg_x, cg_rep), (bi_x, bi_rep)] {
3272 assert_eq!(rep.status, SolveStatus::Converged);
3273 for (g, w) in x.as_slice().iter().zip(xs64.as_slice()) {
3274 assert!((f64::from(*g) - w).abs() < 1e-3, "{g} vs {w}");
3275 }
3276 }
3277 }
3278
3279 #[test]
3280 fn not_converged_reports_max_iterations() {
3281 let a = laplacian(12);
3282 let (_, b) = known_system(&a);
3283 let (_, rep) = conjugate_gradient_with_report(&a, &b, None, 1e-14, 1).unwrap();
3284 assert_eq!(rep.status, SolveStatus::NotConverged);
3285 assert_eq!(rep.iterations, 1);
3286 let (_, rep) = bicgstab_with_report(&a, &b, None, 1e-14, 1).unwrap();
3287 assert_eq!(rep.status, SolveStatus::NotConverged);
3288 assert_eq!(rep.iterations, 1);
3289 }
3290
3291 #[test]
3292 fn negative_definite_breaks_down_cg_on_both_paths() {
3293 let mut coo = CooMatrix::<f64>::new(3, 3);
3295 for i in 0..3 {
3296 coo.push(i, i, -1.0);
3297 }
3298 let a = coo.to_csr();
3299 let b = DVector::from_fn(3, |_| 1.0);
3300 let (_, rep) = conjugate_gradient_with_report(&a, &b, None, 1e-10, 10).unwrap();
3301 assert_eq!(rep.status, SolveStatus::Breakdown);
3302 assert_eq!(rep.iterations, 0);
3303 }
3304
3305 #[test]
3306 fn zero_rhs_and_exact_start_converge_immediately() {
3307 let a = laplacian(6);
3308 let n = a.nrows();
3309 let zero = DVector::zeros(n);
3310 let (x, rep) = conjugate_gradient_with_report(&a, &zero, None, 1e-10, 10).unwrap();
3311 assert_eq!((rep.status, rep.iterations), (SolveStatus::Converged, 0));
3312 assert!(x.as_slice().iter().all(|&v| v == 0.0));
3313
3314 let (xs, b) = known_system(&a);
3315 let (_, rep) = conjugate_gradient_with_report(&a, &b, Some(xs), 1e-10, 10).unwrap();
3316 assert_eq!((rep.status, rep.iterations), (SolveStatus::Converged, 0));
3317 }
3318}
3319
3320#[cfg(all(test, feature = "alloc"))]
3321mod gap_tests {
3322 use super::*;
3323 use alloc::string::ToString;
3324
3325 fn spd_tridiag(n: usize) -> CsrMatrix<f64> {
3327 let mut coo = CooMatrix::new(n, n);
3328 for i in 0..n {
3329 coo.push(i, i, 4.0);
3330 if i + 1 < n {
3331 coo.push(i, i + 1, -1.0);
3332 coo.push(i + 1, i, -1.0);
3333 }
3334 }
3335 coo.to_csr()
3336 }
3337
3338 fn tridiag(n: usize) -> CsrMatrix<f64> {
3339 let mut coo = CooMatrix::new(n, n);
3340 for i in 0..n {
3341 coo.push(i, i, 4.0);
3342 if i + 1 < n {
3343 coo.push(i, i + 1, -1.5);
3344 coo.push(i + 1, i, -0.5);
3345 }
3346 }
3347 coo.to_csr()
3348 }
3349
3350 #[test]
3351 fn givens_zeroes_the_second_entry_on_both_branches() {
3352 for (a, b) in [
3353 (3.0_f64, 4.0_f64),
3354 (4.0, 3.0),
3355 (-3.0, 4.0),
3356 (0.0, 2.0),
3357 (5.0, 0.0),
3358 ] {
3359 let (c, s) = givens(a, b);
3360 let r = c * a + s * b;
3361 let zero = -s * a + c * b;
3362 assert!(zero.abs() < 1e-12, "({a},{b}) gave {zero}");
3363 assert!((c * c + s * s - 1.0).abs() < 1e-12);
3364 assert!(r.abs() >= 0.0);
3365 }
3366 let (c, s): (f64, f64) = givens(3.0, 4.0);
3367 assert!(
3368 (c - 0.6).abs() < 1e-12 && (s - 0.8).abs() < 1e-12,
3369 "{c}, {s}"
3370 );
3371 let (c, s): (f64, f64) = givens(4.0, 3.0);
3372 assert!(
3373 (c - 0.8).abs() < 1e-12 && (s - 0.6).abs() < 1e-12,
3374 "{c}, {s}"
3375 );
3376 assert_eq!(givens(5.0, 0.0), (1.0, 0.0));
3377 }
3378
3379 #[test]
3380 fn cg_on_a_diagonal_matrix_converges_within_the_distinct_eigenvalue_count() {
3381 let mut coo = CooMatrix::new(4, 4);
3382 for i in 0..4 {
3383 coo.push(i, i, (i + 1) as f64);
3384 }
3385 let a = coo.to_csr();
3386 let b = DVector::from_fn(4, |_| 1.0);
3387 let (x, rep) = conjugate_gradient_with_report(&a, &b, None, 1e-12, 50).unwrap();
3388 assert!(rep.status.is_converged());
3389 assert!(
3390 rep.iterations >= 1 && rep.iterations <= 4,
3391 "{}",
3392 rep.iterations
3393 );
3394 for i in 0..4 {
3395 assert!((x[i] - 1.0 / (i + 1) as f64).abs() < 1e-10);
3396 }
3397 }
3398
3399 #[test]
3400 fn cg_respects_max_iter_and_reports_not_converged_at_the_budget() {
3401 let a = spd_tridiag(30);
3402 let b = DVector::from_fn(30, |i| i as f64 + 1.0);
3403 let (_, rep) = conjugate_gradient_with_report(&a, &b, None, 1e-14, 1).unwrap();
3404 assert_eq!(rep.status, SolveStatus::NotConverged);
3405 assert_eq!(rep.iterations, 1);
3406 let err = report_to_result(DVector::zeros(30), rep);
3407 assert_eq!(err, Err(SparseError::NotConverged { iterations: 1 }));
3408 }
3409
3410 #[test]
3411 fn a_solved_start_vector_takes_zero_iterations() {
3412 let a = spd_tridiag(5);
3413 let b = DVector::from_fn(5, |i| i as f64 - 2.0);
3414 let (x, _) = conjugate_gradient_with_report(&a, &b, None, 1e-12, 100).unwrap();
3415 let (_, rep) = conjugate_gradient_with_report(&a, &b, Some(x), 1e-10, 100).unwrap();
3416 assert!(rep.status.is_converged(), "{rep:?}");
3417 assert_eq!(rep.iterations, 0);
3418 }
3419
3420 #[test]
3421 fn bicgstab_on_the_identity_converges_in_one_iteration() {
3422 let mut coo = CooMatrix::new(3, 3);
3423 for i in 0..3 {
3424 coo.push(i, i, 1.0);
3425 }
3426 let a = coo.to_csr();
3427 let b = DVector::from_fn(3, |i| i as f64 + 1.0);
3428 let (x, rep) = bicgstab_with_report(&a, &b, None, 1e-12, 10).unwrap();
3429 assert!(rep.status.is_converged());
3430 assert_eq!(rep.iterations, 1);
3431 assert!((x[2] - 3.0).abs() < 1e-12);
3432 }
3433
3434 #[test]
3435 fn bicgstab_budget_and_nonsymmetric_convergence() {
3436 let a = tridiag(12);
3437 let b = DVector::from_fn(12, |i| (i as f64).sin());
3438 let (_, rep) = bicgstab_with_report(&a, &b, None, 1e-14, 0).unwrap();
3439 assert_eq!(rep.status, SolveStatus::NotConverged);
3440 assert_eq!(rep.iterations, 0);
3441 let (x, rep) = bicgstab_with_report(&a, &b, None, 1e-12, 200).unwrap();
3442 assert!(rep.status.is_converged());
3443 let ax = a.matvec(&x).unwrap();
3444 for i in 0..12 {
3445 assert!((ax[i] - b[i]).abs() < 1e-9);
3446 }
3447 }
3448
3449 #[test]
3450 fn breakdown_status_maps_to_the_breakdown_error() {
3451 let rep = SolveReport {
3452 status: SolveStatus::Breakdown,
3453 iterations: 3,
3454 residual: 1.0,
3455 };
3456 assert_eq!(
3457 report_to_result(DVector::zeros(2), rep),
3458 Err(SparseError::Breakdown { iterations: 3 })
3459 );
3460 }
3461
3462 #[test]
3463 fn gmres_with_a_small_restart_still_converges() {
3464 let a = tridiag(15);
3465 let b = DVector::from_fn(15, |i| 1.0 + i as f64 * 0.1);
3466 let identity = |v: &[f64]| Ok(v.to_vec());
3467 let (x, rep) =
3468 gmres_right_preconditioned_with_report(&a, &b, None, 1e-11, 3, 500, identity).unwrap();
3469 assert!(rep.status.is_converged(), "{rep:?}");
3470 let ax = a.matvec(&x).unwrap();
3471 for i in 0..15 {
3472 assert!((ax[i] - b[i]).abs() < 1e-8);
3473 }
3474 let (_, rep) =
3475 gmres_right_preconditioned_with_report(&a, &b, None, 1e-14, 2, 1, identity).unwrap();
3476 assert_eq!(rep.status, SolveStatus::NotConverged);
3477 }
3478
3479 #[test]
3480 fn coo_accessors_and_error_messages() {
3481 let mut coo = CooMatrix::new(3, 4);
3482 coo.push(0, 1, 1.0);
3483 coo.push(2, 3, 2.0);
3484 assert_eq!((coo.nrows(), coo.ncols(), coo.nnz()), (3, 4, 2));
3485 assert!(SparseError::DimensionMismatch {
3486 what: "the rhs length"
3487 }
3488 .to_string()
3489 .contains("the rhs length"));
3490 assert!(SparseError::NotConverged { iterations: 7 }
3491 .to_string()
3492 .contains('7'));
3493 assert!(SparseError::Breakdown { iterations: 2 }
3494 .to_string()
3495 .contains('2'));
3496 }
3497
3498 #[test]
3499 fn reordered_factors_expose_their_permutation_and_fill() {
3500 let a = tridiag(6);
3501 let chol = ReorderedCholesky::factor(&a).unwrap();
3502 assert_eq!(chol.permutation().len(), 6);
3503 assert!(chol.nnz() >= 6);
3504 let lu = ReorderedLu::factor(&a, FillOrdering::MinimumDegree).unwrap();
3505 assert_eq!(lu.permutation().len(), 6);
3506 let mut seen = lu.permutation().to_vec();
3507 seen.sort_unstable();
3508 assert_eq!(seen, (0..6).collect::<Vec<_>>());
3509 }
3510
3511 fn repeated_spectrum() -> impl crate::LinearOperator<f64> {
3513 crate::matrix_free(6, |x: &[f64], y: &mut [f64]| {
3514 for i in 0..x.len() {
3515 y[i] = ((i / 2) + 1) as f64 * x[i];
3516 }
3517 })
3518 }
3519
3520 #[test]
3521 fn lanczos_stops_at_the_number_of_distinct_eigenvalues() {
3522 let pairs = crate::lanczos(&repeated_spectrum(), 3, 6, crate::Which::Smallest).unwrap();
3523 assert_eq!(
3524 pairs.krylov_dim, 3,
3525 "invariant subspace after three distinct eigenvalues"
3526 );
3527 for (v, want) in pairs.values.iter().zip([1.0, 2.0, 3.0]) {
3528 assert!((v - want).abs() < 1e-9, "{v} vs {want}");
3529 }
3530 assert!(pairs.residuals.iter().all(|r| *r < 1e-8));
3531 }
3532
3533 #[test]
3534 fn arnoldi_stops_at_the_number_of_distinct_eigenvalues() {
3535 let ritz = crate::arnoldi(&repeated_spectrum(), 3, 6).unwrap();
3536 assert_eq!(ritz.krylov_dim, 3);
3537 let mut re: Vec<f64> = ritz.values.iter().map(|e| e.re).collect();
3538 re.sort_by(|a, b| a.total_cmp(b));
3539 for (v, want) in re.iter().zip([1.0, 2.0, 3.0]) {
3540 assert!((v - want).abs() < 1e-9, "{v} vs {want}");
3541 }
3542 assert!(ritz
3543 .residuals
3544 .iter()
3545 .all(|r| matches!(r, Some(x) if *x < 1e-8)));
3546 }
3547}