Skip to main content

tpt_math_linalg_sparse/
lib.rs

1#![no_std]
2#![forbid(unsafe_code)]
3//! Sparse linear algebra implemented entirely in-house (no external backend).
4//!
5//! This crate provides general-purpose sparse matrix storage — coordinate
6//! (triplet, [`CooMatrix`]), compressed-sparse-row ([`CsrMatrix`]) and
7//! compressed-sparse-column ([`CscMatrix`]) — plus iterative solvers, preconditioners
8//! and direct LU / Cholesky factorisations:
9//! [`conjugate_gradient`] for symmetric positive-definite systems and
10//! [`bicgstab`] for general (non-symmetric) systems.
11//!
12//! Everything is hand-rolled on top of [`tpt_math_linalg_dense::DVector`] (the
13//! dense RHS/solution type) and [`tpt_math_numeric::Scalar`], so there is no
14//! `nalgebra`/`faer`/`sprs` dependency and no license exposure. The design
15//! deliberately mirrors the *storage* portion of a sparse format only; it does
16//! not try to replace [`tpt-fem-sparse`](https://crates.io/crates/tpt-fem-sparse),
17//! which is a separate FEM-assembly adapter (element scatter + duplicate-summing
18//! triplet accumulation) living in the `tpt-fem` repo.
19//!
20//! # Features
21//!
22//! * `std` (default) — enable the allocator and the `std` support of deps.
23//! * `alloc` — signal allocator availability (sparse containers need it).
24//!
25//! # Examples
26//!
27//! ```
28//! use tpt_math_linalg_dense::DVector;
29//! use tpt_math_linalg_sparse::{CooMatrix, conjugate_gradient, SparseError};
30//!
31//! // Build the 2x2 SPD system  A x = b  with  A = [[4,1],[1,3]], b = [1,2].
32//! let mut coo = CooMatrix::<f64>::new(2, 2);
33//! coo.push(0, 0, 4.0);
34//! coo.push(0, 1, 1.0);
35//! coo.push(1, 0, 1.0);
36//! coo.push(1, 1, 3.0);
37//!
38//! let a = coo.to_csr();
39//! let b = DVector::from_vec(vec![1.0, 2.0]);
40//! let x = conjugate_gradient(&a, &b, None, 1e-12, 100).unwrap();
41//! let expected = DVector::from_vec(vec![1.0 / 11.0, 7.0 / 11.0]);
42//! assert!((x[0] - expected[0]).abs() < 1e-10);
43//! assert!((x[1] - expected[1]).abs() < 1e-10);
44//! # let _ = SparseError::DimensionMismatch { what: "operands have incompatible dimensions" };
45//! ```
46
47extern 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/// Errors returned by the sparse solvers and operators.
75#[derive(Debug, Clone, PartialEq, Eq)]
76#[non_exhaustive]
77pub enum SparseError {
78    /// A matrix/vector dimension pairing was incompatible (e.g. a matrix with
79    /// `ncols` columns multiplied by a vector whose length differs).
80    DimensionMismatch {
81        /// What was incompatible, as a static description.
82        what: &'static str,
83    },
84    /// The iterative solver reached `max_iter` without meeting the tolerance.
85    /// `iterations` reports how many iterations were run.
86    NotConverged {
87        /// Number of iterations performed before giving up.
88        iterations: usize,
89    },
90    /// The method hit a numerical breakdown (a zero or negative inner product
91    /// such as `pᵀAp` for CG, or a non-finite value) and cannot continue.
92    Breakdown {
93        /// Iteration at which the breakdown occurred.
94        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// ---------------------------------------------------------------------------
120// COO (triplet) storage
121// ---------------------------------------------------------------------------
122
123/// A sparse matrix in coordinate (COO / triplet) form.
124///
125/// Entries are stored as an unordered list of `(row, col, value)` triplets.
126/// Duplicates are permitted and are summed together on conversion to a
127/// compressed format ([`CooMatrix::to_csr`] / [`CooMatrix::to_csc`]), matching
128/// the duplicate-summing semantics `tpt-fem-sparse` relies on for element
129/// scatter + accumulation.
130#[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    /// Create an empty `nrows` × `ncols` matrix.
141    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    /// Number of rows.
152    pub fn nrows(&self) -> usize {
153        self.nrows
154    }
155
156    /// Number of columns.
157    pub fn ncols(&self) -> usize {
158        self.ncols
159    }
160
161    /// Number of stored entries (including any pending duplicates).
162    pub fn nnz(&self) -> usize {
163        self.vals.len()
164    }
165
166    /// Push a single entry. Duplicates are summed on conversion to CSR/CSC.
167    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    /// Build from parallel `(rows, cols, vals)` triplets.
176    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    /// Convert to compressed-sparse-row form, summing any duplicate entries.
195    #[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    /// Convert to compressed-sparse-column form, summing any duplicate entries.
201    #[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// ---------------------------------------------------------------------------
208// CSR storage
209// ---------------------------------------------------------------------------
210
211/// A sparse matrix in compressed-sparse-row (CSR) form.
212///
213/// `row_ptr` has length `nrows + 1`; `row_ptr[i]` .. `row_ptr[i + 1]` indexes
214/// the stored entries of row `i` inside `col_idx` / `values`.
215#[derive(Clone, Debug, PartialEq, Eq)]
216pub struct CsrMatrix<T> {
217    nrows: usize,
218    ncols: usize,
219    row_ptr: Vec<usize>,
220    // `u32` halves the index traffic and matches tpt-simd-sparse's CSR view.
221    // Construction checks that every column fits (see `to_csr_impl`).
222    col_idx: Vec<u32>,
223    values: Vec<T>,
224}
225
226impl<T> CsrMatrix<T> {
227    /// Number of rows.
228    pub fn nrows(&self) -> usize {
229        self.nrows
230    }
231
232    /// Number of columns.
233    pub fn ncols(&self) -> usize {
234        self.ncols
235    }
236
237    /// Number of stored (post-merge) entries.
238    pub fn nnz(&self) -> usize {
239        self.values.len()
240    }
241
242    /// Iterate over the stored entries as `(row, col, &value)`.
243    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    /// Transpose, producing a [`CscMatrix`].
255    #[cfg(feature = "alloc")]
256    pub fn transpose(&self) -> CscMatrix<T> {
257        // New matrix is `ncols x nrows`; swap row/col roles.
258        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    /// Sparse matrix–vector product `y = A x`.
268    ///
269    /// # Errors
270    ///
271    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `x.len() != ncols()`.
272    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    /// Sparse matrix–vector product `y = A x` written into a caller-owned
284    /// buffer.
285    ///
286    /// Reusing `y` avoids a fresh allocation on every call, which matters in
287    /// loops that apply the same matrix repeatedly.
288    ///
289    /// # Errors
290    ///
291    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `x.len() != ncols()` or
292    /// `y.len() != nrows()`.
293    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    /// # Panics
314    ///
315    /// Panics (via a `DimensionMismatch` message) if `rhs.len() != ncols()`.
316    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// ---------------------------------------------------------------------------
323// CSC storage
324// ---------------------------------------------------------------------------
325
326/// A sparse matrix in compressed-sparse-column (CSC) form.
327///
328/// `col_ptr` has length `ncols + 1`; `col_ptr[j]` .. `col_ptr[j + 1]` indexes
329/// the stored entries of column `j` inside `row_idx` / `values`.
330#[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    /// Number of rows.
341    pub fn nrows(&self) -> usize {
342        self.nrows
343    }
344
345    /// Number of columns.
346    pub fn ncols(&self) -> usize {
347        self.ncols
348    }
349
350    /// Number of stored (post-merge) entries.
351    pub fn nnz(&self) -> usize {
352        self.values.len()
353    }
354
355    /// Iterate over the stored entries as `(row, col, &value)`.
356    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    /// Transpose, producing a [`CsrMatrix`].
368    #[cfg(feature = "alloc")]
369    pub fn transpose(&self) -> CsrMatrix<T> {
370        // New matrix is `ncols x nrows`; swap row/col roles.
371        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    /// Sparse matrix–vector product `y = A x`.
381    ///
382    /// # Errors
383    ///
384    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `x.len() != ncols()`.
385    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// ---------------------------------------------------------------------------
406// Conversion helpers (duplicate-summing)
407// ---------------------------------------------------------------------------
408
409/// Stable counting sort of `(row, col, value)` triplets by one of their
410/// indices: `key` selects the row (`0`) or column (`1`). Runs in `O(nnz + n)`.
411#[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    // Slots are pre-filled with a copy of the first entry (or left empty) and
425    // then overwritten, each at its bucket's running offset.
426    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/// Sum adjacent entries with the same `(row, col)` in an input already grouped
439/// by `(outer, inner)` order. Returns the merged entries and, per outer index,
440/// how many survive.
441#[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    // Column-bucket first, then stable row-bucket: the result is row-major with
479    // columns ascending inside each row, so duplicates are adjacent.
480    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    // Mirror image of `to_csr_impl`: row-bucket first, then stable column-bucket.
516    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// ---------------------------------------------------------------------------
540// Iterative solvers
541// ---------------------------------------------------------------------------
542
543/// Solve `A x = b` with the conjugate gradient method for symmetric
544/// positive-definite `A`.
545///
546/// * `a` — system matrix in CSR form (must be square and SPD).
547/// * `b` — right-hand side.
548/// * `x0` — optional starting guess; zeros are used if `None`.
549/// * `tol` — relative residual tolerance: stop when `‖r‖ ≤ tol·‖b‖` (absolute if
550///   `b = 0`).
551/// * `max_iter` — iteration cap.
552///
553/// # Errors
554///
555/// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `a` is not square or `b`'s
556/// length does not match `a.nrows()`. Returns [`SparseError::NotConverged`] if
557/// the method fails to reach `tol` within `max_iter` steps (or breaks down).
558#[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/// [`conjugate_gradient`] with a [`SolveReport`] instead of an error for
571/// breakdown or non-convergence.
572///
573/// Returns the last iterate together with its report, so a caller can inspect
574/// how far the solve got. Only a dimension mismatch is an `Err`.
575///
576/// # Errors
577///
578/// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `a` is not square or `b`'s
579/// length does not match `a.nrows()`, or if a supplied `x0` has the wrong length.
580#[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    // Check x0 before the SIMD dispatch: the SIMD kernels index it directly.
589    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/// The scalar conjugate-gradient loop, generic over how `A·p` is applied.
608///
609/// `apply(p, ap)` must write `A·p` into `ap`. The CSR path passes
610/// [`CsrMatrix::matvec_into`], and matrix-free callers pass their operator.
611/// `b` must have length `n`.
612#[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    // Relative tolerance: stop when ‖r‖ ≤ tol·‖b‖ (absolute tol if b = 0).
630    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    // Work buffer reused across iterations: the loop allocates nothing.
641    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        // For SPD A, pᵀAp > 0 until convergence; anything else (including NaN)
647        // means the method cannot continue.
648        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/// f32/f64 kernels for CG and BiCGSTAB (feature `simd`).
669///
670/// The generic solvers reach these through `Any` downcasts, which need no
671/// `unsafe`. The loops mirror the scalar ones step for step (same breakdown
672/// checks, same exit points), so the two paths make the same decisions and
673/// differ only in rounding.
674#[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    /// `true` when `T` is `f32` or `f64`, the types with tpt-simd kernels.
688    pub(crate) fn applies<T: 'static>() -> bool {
689        TypeId::of::<T>() == TypeId::of::<f64>() || TypeId::of::<T>() == TypeId::of::<f32>()
690    }
691
692    /// Converts an owned value to a type it is known to have.
693    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    /// Borrowed form of [`convert`].
700    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    /// Validated CSR view over the matrix storage. The invariants hold by
707    /// construction (`to_csr_impl`), so validation cannot fail.
708    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    /// Solver core for one concrete float type `R`.
728    type Core<R> = fn(&CsrMatrix<R>, &[R], Option<Vec<R>>, R, usize) -> (Vec<R>, SolveReport<R>);
729
730    /// Runs a core on the caller's data, which is of type `T` = `R`.
731    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    /// Conjugate gradients for `T` = `f32` or `f64`.
747    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    /// BiCGSTAB for `T` = `f32` or `f64`.
762    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        // r = b - A x, as one SpMV: y = -1 * A x + 1 * b.
787        let mut r = b.to_vec();
788        spmv_csr(-R::one(), &view, &x, R::one(), &mut r);
789        // Relative tolerance: stop when ‖r‖ ≤ tol·‖b‖ (absolute tol if b = 0).
790        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            // For SPD A, pᵀAp > 0 until convergence; anything else (including
806            // NaN) means the method cannot continue.
807            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            // x += alpha p, r -= alpha ap, and the new r·r, in one pass.
812            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            // p = r + beta * (p - omega * v)
863            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 = r - alpha v
871            s.copy_from_slice(&r);
872            axpy(-alpha, &v, &mut s);
873            let s_norm = sqnorm(&s).sqrt();
874            // Half-step exit: if s is already small enough, x + alpha p is the answer.
875            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            // x += alpha p + omega s; r = s - omega t (with its new r·r).
889            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/// Build the `(iterate, report)` pair returned by the `*_with_report` solvers.
911#[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/// Map a report back to the error-returning convention of the plain solvers.
929#[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        // Unknown future statuses are reported as a breakdown: not converged, reason unknown.
940        _ => Err(SparseError::Breakdown {
941            iterations: report.iterations,
942        }),
943    }
944}
945
946/// Solve `A x = b` with the BiCGSTAB method for general (non-symmetric)
947/// systems.
948///
949/// Arguments mirror [`conjugate_gradient`]. BiCGSTAB is less robust than CG on
950/// SPD systems but converges on many indefinite / non-symmetric problems where
951/// CG would fail.
952///
953/// # Errors
954///
955/// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if the dimensions are
956/// incompatible, and [`SparseError::NotConverged`] if the method does not reach
957/// `tol` within `max_iter` steps or encounters a breakdown.
958#[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/// [`bicgstab`] with a [`SolveReport`] instead of an error for breakdown or
971/// non-convergence. Returns the last iterate with its report.
972///
973/// # Errors
974///
975/// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] for incompatible dimensions only.
976#[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    // Check x0 before the SIMD dispatch: the SIMD kernels index it directly.
985    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/// The scalar BiCGSTAB loop, generic over how `A·p` is applied. `apply(p, out)`
1004/// must write `A·p` into `out`. `b` must have length `n`.
1005#[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    // Relative tolerance: stop when ‖r‖ ≤ tol·‖b‖ (absolute tol if b = 0).
1023    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    // Work buffers reused across iterations: the loop allocates nothing.
1034    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        // p = r + beta * (p - omega * v), using the previous v.
1048        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 = r - alpha * v
1063        s.as_mut_slice().copy_from_slice(r.as_slice());
1064        axpy_slice(s.as_mut_slice(), -alpha, v.as_slice());
1065        // Half-step exit: if s is already small enough, x + alpha·p is the answer.
1066        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        // x += alpha * p + omega * s; r = s - omega * t.
1080        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/// Euclidean norm of a slice.
1093#[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/// Dot product of two equal-length slices.
1099#[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/// In-place `y ← y + α·x`.
1105#[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/// In-place `y ← x + β·y` (the search-direction update in CG).
1113#[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/// Givens rotation `(c, s)` with `c·a + s·b = r` and `−s·a + c·b = 0`.
1121#[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/// Solve `A x = b` with restarted GMRES(`restart`) for a general square `A`.
1138///
1139/// Each cycle builds an Arnoldi basis of the Krylov subspace by modified
1140/// Gram–Schmidt, and minimises the residual over that subspace with Givens
1141/// rotations. The basis is discarded every `restart` steps. The method works for
1142/// non-symmetric systems that [`conjugate_gradient`] cannot handle, at the cost
1143/// of storing the whole basis for one cycle.
1144///
1145/// * `tol` — relative residual tolerance: stop when `‖r‖ ≤ tol·‖b‖` (absolute if
1146///   `b = 0`).
1147/// * `restart` — Krylov subspace dimension per cycle (clamped to at least 1).
1148/// * `max_iter` — bound on the total number of Arnoldi steps across all cycles.
1149///
1150/// # Errors
1151///
1152/// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `a` is not square, or `b` or
1153/// `x0` has the wrong length. Returns [`SparseError::NotConverged`] if the
1154/// tolerance is not met within `max_iter` steps, and [`SparseError::Breakdown`]
1155/// if the Hessenberg system becomes singular.
1156///
1157/// # Examples
1158///
1159/// ```
1160/// use tpt_math_linalg_sparse::{gmres, CooMatrix};
1161/// use tpt_math_linalg_dense::DVector;
1162///
1163/// // Non-symmetric tridiagonal system with exact solution (1, 2, 3).
1164/// let mut coo = CooMatrix::<f64>::new(3, 3);
1165/// for &(r, c, v) in &[(0, 0, 4.0), (0, 1, 1.0), (1, 0, 2.0), (1, 1, 5.0), (1, 2, 1.0), (2, 1, 1.0), (2, 2, 3.0)] {
1166///     coo.push(r, c, v);
1167/// }
1168/// let a = coo.to_csr();
1169/// let b = DVector::from_vec(vec![6.0, 15.0, 11.0]);
1170/// let x = gmres(&a, &b, None, 1e-12, 3, 100).unwrap();
1171/// assert!((x[0] - 1.0).abs() < 1e-9 && (x[2] - 3.0).abs() < 1e-9);
1172/// ```
1173#[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/// Right-preconditioned restarted GMRES.
1188///
1189/// Solves `A x = b` through the preconditioned operator `A M⁻¹`, where
1190/// `precond` applies `M⁻¹` to a vector. Right preconditioning leaves the
1191/// residual unchanged, so the tolerance and budget have the same meaning as in
1192/// [`gmres`]. A good `M` makes `A M⁻¹` close to the identity, which cuts the
1193/// number of Arnoldi steps.
1194///
1195/// # Errors
1196///
1197/// As [`gmres`], plus any error returned by `precond`.
1198#[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/// [`gmres_right_preconditioned`] with a [`SolveReport`] instead of an error
1218/// for breakdown or non-convergence. Returns the last iterate with its report.
1219///
1220/// # Errors
1221///
1222/// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] for incompatible dimensions, and
1223/// propagates any error from `precond`.
1224#[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/// The restarted GMRES loop, generic over how `A·p` is applied. `apply(p, out)`
1256/// must write `A·p` into `out`. `b` must have length `n`.
1257#[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        // Arnoldi cycle on the preconditioned operator A M⁻¹. `basis[j]` is the
1320        // j-th orthonormal Krylov vector, `hess[j]` the j-th Hessenberg column
1321        // after the Givens rotations.
1322        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            // Apply the earlier rotations, then a new one for the subdiagonal.
1345            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            // A zero subdiagonal means the subspace is invariant: the solution
1361            // is exact within it, so stop the cycle here.
1362            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        // Solve the upper-triangular system R y = g for the cycle.
1369        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        // The cycle's correction is M⁻¹ (Σ yⱼ vⱼ) because of right preconditioning.
1389        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/// GMRES preconditioned by the ILU(0) factors of `a` itself.
1403///
1404/// Factorises `a` once, then runs [`gmres_right_preconditioned`]. This is the
1405/// usual pairing for sparse non-symmetric systems. It is cheap per iteration and
1406/// often cuts the iteration count a lot.
1407///
1408/// # Errors
1409///
1410/// As [`Ilu0::factor`] and [`gmres`].
1411#[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/// Solve `A x = b` with conjugate gradients preconditioned by the Jacobi
1428/// (diagonal) preconditioner `M = diag(A)`.
1429///
1430/// Each iteration applies `M⁻¹ r` by dividing the residual by the diagonal
1431/// entries. This is cheap and helps most when the diagonal varies widely in
1432/// scale, as with badly scaled stiffness matrices. For SPD `A` with a constant
1433/// diagonal it does nothing useful, and plain [`conjugate_gradient`] is
1434/// equivalent.
1435///
1436/// The tolerance and error conditions are those of [`conjugate_gradient`].
1437///
1438/// # Errors
1439///
1440/// As [`conjugate_gradient`], plus [`SparseError::Breakdown`] at iteration zero
1441/// if a diagonal entry is zero, since the preconditioner is then undefined.
1442///
1443/// # Examples
1444///
1445/// ```
1446/// use tpt_math_linalg_sparse::{jacobi_preconditioned_cg, CooMatrix};
1447/// use tpt_math_linalg_dense::DVector;
1448///
1449/// // Diagonal spans four orders of magnitude.
1450/// let mut coo = CooMatrix::<f64>::new(2, 2);
1451/// coo.push(0, 0, 1.0);
1452/// coo.push(1, 1, 1e4);
1453/// let a = coo.to_csr();
1454/// let b = DVector::from_vec(vec![2.0, 3e4]);
1455/// let x = jacobi_preconditioned_cg(&a, &b, None, 1e-12, 10).unwrap();
1456/// assert!((x[0] - 2.0).abs() < 1e-9 && (x[1] - 3.0).abs() < 1e-9);
1457/// ```
1458/// Solve `A x = b` with conjugate gradients under a caller-supplied SPD
1459/// preconditioner `M`.
1460///
1461/// `precond` must return `M⁻¹ r` for a residual `r`, and `M` must be symmetric
1462/// positive definite for the method to be sound. The tolerance and error
1463/// conditions are those of [`conjugate_gradient`]. [`jacobi_preconditioned_cg`]
1464/// and [`ic0_preconditioned_cg`] are this function with specific preconditioners.
1465///
1466/// # Errors
1467///
1468/// As [`conjugate_gradient`], plus any error returned by `precond`.
1469#[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/// Solve `A x = b` with conjugate gradients preconditioned by the Jacobi
1549/// (diagonal) preconditioner `M = diag(A)`.
1550///
1551/// Each iteration applies `M⁻¹ r` by dividing the residual by the diagonal
1552/// entries. This is cheap and helps most when the diagonal varies widely in
1553/// scale, as with badly scaled stiffness matrices. For SPD `A` with a constant
1554/// diagonal it does nothing useful, and plain [`conjugate_gradient`] is
1555/// equivalent.
1556///
1557/// The tolerance and error conditions are those of [`conjugate_gradient`].
1558///
1559/// # Errors
1560///
1561/// As [`conjugate_gradient`], plus [`SparseError::Breakdown`] at iteration zero
1562/// if a diagonal entry is zero, since the preconditioner is then undefined.
1563///
1564/// # Examples
1565///
1566/// ```
1567/// use tpt_math_linalg_sparse::{jacobi_preconditioned_cg, CooMatrix};
1568/// use tpt_math_linalg_dense::DVector;
1569///
1570/// // Diagonal spans four orders of magnitude.
1571/// let mut coo = CooMatrix::<f64>::new(2, 2);
1572/// coo.push(0, 0, 1.0);
1573/// coo.push(1, 1, 1e4);
1574/// let a = coo.to_csr();
1575/// let b = DVector::from_vec(vec![2.0, 3e4]);
1576/// let x = jacobi_preconditioned_cg(&a, &b, None, 1e-12, 10).unwrap();
1577/// assert!((x[0] - 2.0).abs() < 1e-9 && (x[1] - 3.0).abs() < 1e-9);
1578/// ```
1579#[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    // Extract diag(A); a missing or zero diagonal entry makes M singular.
1595    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/// Sparse Cholesky factor `A = L Lᵀ` of a symmetric positive-definite matrix.
1612///
1613/// Stored by columns: column `j` holds the entries `L(i, j)` with `i ≥ j`,
1614/// sorted by row, with the diagonal first. No fill-reducing ordering is applied,
1615/// so fill-in can be larger than with a reordered factorisation. The method is
1616/// exact up to rounding, and the factor is reused for any number of right-hand
1617/// sides.
1618#[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    /// Factorise a symmetric positive-definite CSR matrix.
1628    ///
1629    /// Only the lower triangle of `a` is read; symmetry is assumed, not checked.
1630    ///
1631    /// # Errors
1632    ///
1633    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `a` is not square, and
1634    /// [`SparseError::Breakdown`] if a pivot is not positive, which means the
1635    /// matrix is not positive definite.
1636    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            // Load column j of A (the lower part of row j, by symmetry).
1648            for (row, col, &v) in a.iter() {
1649                if row == j && col >= j {
1650                    work[col] = v;
1651                }
1652            }
1653            // Subtract the contributions of the earlier columns.
1654            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            // Clear the workspace for the next column.
1676            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    /// Dimension of the factorised matrix.
1685    pub fn dim(&self) -> usize {
1686        self.n
1687    }
1688
1689    /// Number of stored entries in `L`, including the diagonal. Comparing this
1690    /// with the entries of `A` shows how much fill-in occurred.
1691    pub fn nnz(&self) -> usize {
1692        self.columns.iter().map(Vec::len).sum()
1693    }
1694
1695    /// Solve `A x = b` with the stored factor.
1696    ///
1697    /// # Errors
1698    ///
1699    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `b` has the wrong length.
1700    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        // Forward substitution L y = b, column by column.
1708        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        // Back substitution Lᵀ x = y, using the same columns as rows of Lᵀ.
1717        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/// Incomplete LU factorisation with zero fill-in, ILU(0).
1730///
1731/// Computes `L U ≈ A` where `L` is unit lower triangular and `U` upper
1732/// triangular, and keeps only the sparsity pattern of `A`. The product matches
1733/// `A` on that pattern and differs elsewhere. Applying `(LU)⁻¹` to a vector is
1734/// a cheap approximate inverse, which makes ILU(0) a standard preconditioner.
1735/// For a matrix with no fill-in under LU, such as a tridiagonal one, it is exact.
1736#[cfg(feature = "alloc")]
1737#[derive(Clone, Debug, PartialEq)]
1738pub struct Ilu0 {
1739    n: usize,
1740    /// Each row sorted by column. Strictly lower entries hold `L`, the diagonal
1741    /// and upper entries hold `U`.
1742    rows: Vec<Vec<(usize, f64)>>,
1743    /// Position of the diagonal entry within each row.
1744    diagonal: Vec<usize>,
1745}
1746
1747#[cfg(feature = "alloc")]
1748impl Ilu0 {
1749    /// Compute the ILU(0) factors of a square CSR matrix.
1750    ///
1751    /// # Errors
1752    ///
1753    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `a` is not square, and
1754    /// [`SparseError::Breakdown`] if a row has no diagonal entry or a pivot is
1755    /// zero.
1756    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        // IKJ-ordered elimination restricted to the existing pattern.
1779        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                // Row k is finished, so reading it while updating row i is safe.
1797                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    /// Apply the preconditioner: returns `(LU)⁻¹ r`, an approximation to `A⁻¹ r`.
1813    ///
1814    /// # Errors
1815    ///
1816    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `r` has the wrong length.
1817    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        // Forward substitution with unit lower L.
1825        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        // Back substitution with upper U.
1833        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/// Incomplete Cholesky factorisation with zero fill-in, IC(0).
1845///
1846/// For a symmetric positive-definite `A`, computes a lower-triangular `L` whose
1847/// sparsity pattern is exactly the lower triangle of `A`, with `L Lᵀ ≈ A`. It is
1848/// the symmetric counterpart of [`Ilu0`] and the usual preconditioner for CG.
1849/// The product matches `A` on the pattern and differs elsewhere. For a matrix
1850/// whose Cholesky factor has no fill-in, such as a tridiagonal one, it is exact.
1851#[cfg(feature = "alloc")]
1852#[derive(Clone, Debug, PartialEq)]
1853pub struct Ic0 {
1854    factor: SparseCholesky,
1855}
1856
1857#[cfg(feature = "alloc")]
1858impl Ic0 {
1859    /// Compute the IC(0) factor of a symmetric positive-definite CSR matrix.
1860    ///
1861    /// Only the lower triangle of `a` is read; symmetry is assumed, not checked.
1862    ///
1863    /// # Errors
1864    ///
1865    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `a` is not square, and
1866    /// [`SparseError::Breakdown`] if a column has no diagonal entry or a pivot is
1867    /// not positive. A non-positive pivot means the incomplete factor does not
1868    /// exist for this pattern, which can happen even for an SPD matrix.
1869    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        // Lower-triangle columns of A: lower[j] holds (i, A_ij) for i ≥ j.
1877        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        // contributors[i] lists the finished columns k < i with L(i, k) in their
1889        // pattern, so column j only visits the columns that can update it.
1890        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    /// Dimension of the factorised matrix.
1937    pub fn dim(&self) -> usize {
1938        self.factor.dim()
1939    }
1940
1941    /// Apply the preconditioner: returns `(L Lᵀ)⁻¹ r`, an approximation to
1942    /// `A⁻¹ r`.
1943    ///
1944    /// # Errors
1945    ///
1946    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `r` has the wrong length.
1947    pub fn apply(&self, r: &DVector<f64>) -> Result<DVector<f64>, SparseError> {
1948        self.factor.solve(r)
1949    }
1950}
1951
1952/// Solve `A x = b` with conjugate gradients preconditioned by the IC(0) factor
1953/// of `a`.
1954///
1955/// Factorises `a` once and then runs [`preconditioned_conjugate_gradient`]. Use
1956/// it for sparse SPD systems where Jacobi scaling is not enough, such as the
1957/// 2D Laplacian. The tolerance and error conditions are those of
1958/// [`conjugate_gradient`].
1959///
1960/// # Errors
1961///
1962/// As [`Ic0::factor`] and [`conjugate_gradient`].
1963#[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/// Sparse LU factorisation with partial pivoting, `P A = L U`.
1976///
1977/// Left-looking (Gilbert–Peierls) elimination: column `j` of `A` is solved
1978/// against the already-computed `L` columns, touching only the pivot steps whose
1979/// entries are non-zero, in increasing order. Pivoting picks the largest-magnitude
1980/// candidate in the column, which keeps the factorisation stable for
1981/// non-symmetric and indefinite matrices. Fill-in is not reduced by any ordering,
1982/// so `L` and `U` can be much denser than `A` on unstructured problems.
1983///
1984/// The factor is reusable for any number of right-hand sides via [`SparseLu::solve`].
1985#[cfg(feature = "alloc")]
1986#[derive(Clone, Debug, PartialEq)]
1987pub struct SparseLu {
1988    n: usize,
1989    /// `pivot_row[k]` is the original row chosen as the pivot at step `k`.
1990    pivot_row: Vec<usize>,
1991    /// `L` column `k`: unit lower entries `(row, value)` for rows that were not
1992    /// pivots at steps `≤ k`. The unit diagonal is implicit.
1993    l_cols: Vec<Vec<(usize, f64)>>,
1994    /// `U` column `j`: strictly upper entries `(step, value)` with `step < j`.
1995    u_cols: Vec<Vec<(usize, f64)>>,
1996    /// `U` diagonal, one entry per step.
1997    diag: Vec<f64>,
1998}
1999
2000#[cfg(feature = "alloc")]
2001impl SparseLu {
2002    /// Factorise a square CSR matrix.
2003    ///
2004    /// # Errors
2005    ///
2006    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `a` is not square, and
2007    /// [`SparseError::Breakdown`] at step `k` if column `k` has no usable pivot,
2008    /// which means the matrix is singular (structurally or numerically).
2009    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        // Column-wise copy of A.
2017        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        // Dense accumulator for the current column, plus the list of rows it
2030        // touches so that only those entries are visited and cleared.
2031        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            // Pivot steps to apply, in increasing order.
2045            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            // Partial pivoting: largest magnitude among the unpivoted rows.
2070            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    /// Dimension of the factorised matrix.
2112    pub fn dim(&self) -> usize {
2113        self.n
2114    }
2115
2116    /// Stored entries in `L` and `U` together, counting the diagonal of `U`.
2117    /// Comparing this with the entries of `A` shows how much fill-in occurred.
2118    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    /// Solve `A x = b` with the stored factor.
2125    ///
2126    /// # Errors
2127    ///
2128    /// Returns [`SparseError::DimensionMismatch { what: "operands have incompatible dimensions" }`] if `b` has the wrong length.
2129    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        // Forward substitution L y = P b, in pivot-step order.
2136        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        // Back substitution U x = y. Column j of U holds the entries above its
2146        // diagonal, so x_j is final once j is reached in descending order.
2147        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    /// Non-symmetric, diagonally dominant band with an off-band coupling, so
2176    /// the factor has real fill-in.
2177    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        // A(0,0) = 0, so the first step must pivot on a different row.
2207        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        // The factor really is sparse-but-filled: more than A's entries.
2245        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        // The second row is twice the first.
2263        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        // A tridiagonal SPD matrix has a bidiagonal Cholesky factor, so IC(0)
2328        // is the exact factor and applying it inverts A.
2329        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        // Find the smallest iteration budget that solves the system: the
2354        // preconditioned solve must need strictly fewer iterations.
2355        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        // Symmetric but indefinite: the second pivot is negative.
2367        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        // A tridiagonal matrix produces no fill-in, so ILU(0) equals LU.
2413        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        // 2D Laplacian: LU fills in, so ILU(0) is only approximate, but applying
2424        // it should still reduce the residual a lot compared with doing nothing.
2425        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    /// 2D Laplacian (5-point stencil) on a `m × m` grid, which is SPD.
2476    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    /// SPD tridiagonal with a diagonal spanning 1 to 10⁴.
2553    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        // n = 30 with a diagonal 4 and a non-symmetric off-diagonal pattern.
2625        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        // Restart 4 forces many cycles, so the restart logic is exercised.
2640        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        // One Arnoldi step cannot resolve a 3×3 system to 1e-14.
2650        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        // 2D Laplacian on a 10×10 grid (n = 100).
2659        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        // Measured: plain GMRES needs 26 steps for this tolerance and ILU(0)
2683        // needs 14. A budget of 20 separates the two.
2684        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        // ‖b‖ ≈ 2e-12 is already below the absolute tol 1e-10, so the old
2721        // absolute test returned x0 = 0 without solving anything.
2722        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        // diag(1, -1) with b = (1, 1): pᵀAp = 1 - 1 = 0 on the first step.
2733        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        // [4 1; 1 3] * [1; 2] = [6; 7]
2751        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        // Two contributions to (0,0) that must be summed, plus a duplicate that
2782        // is out of order.
2783        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        // Row 0: (0,0)=3, (0,1)=7 ; row 1: (1,0)=9, (1,1)=5.
2793        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        // Unsorted triplets with duplicates in both row- and column-major order.
2806        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        // CSR stores columns ascending within each row.
2845        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        // [[4,1],[1,3]] * [2,-1] = [7, -1].
2859        let y = a.matvec(&x).unwrap();
2860        assert_eq!(y, DVector::from_vec(vec![7.0, -1.0]));
2861        // Operator form.
2862        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        // A^T = [[4,1],[1,3]] (symmetric) -> CSC col 0: (0,4),(1,1); col 1: (0,1),(1,3).
2883        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        // Residual check.
2901        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        // Empty matrix and trailing empty columns keep their declared shape.
2908        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        // 2x3 matrix -> transpose is 3x2.
2922        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        // CSC column 0: (0,1),(2,2); col 1: (1,3).
2931        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        // Under `simd` this used to panic in the kernel instead of returning Err.
2945        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        // One iteration is far from convergence -> NotConverged.
2967        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        // A = [[4,1],[1,3]] as CSC; x = [2,-1] -> [7,-1].
2988        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        // 5-point 2D Laplacian on a 3x3 interior grid (9 unknowns), SPD.
3002        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        // A non-symmetric matrix with a known solution x = [1, 2].
3032        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); // breaks symmetry
3036        coo.push(1, 1, 4.0);
3037        let a = coo.to_csr();
3038        // b = A * [1, 2] = [4, 11].
3039        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        // The plain solver reports the same situation as an error.
3100        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    //! The f32/f64 solver paths (tpt-simd-sparse with the `simd` feature, the
3195    //! scalar loops otherwise) must agree on the solution, the iteration count
3196    //! to within one, and the exit status. These run in both configurations.
3197    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    /// `b = A x*` for a known `x*`, so the solution can be checked directly.
3229    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        // A = -I: pᵀAp < 0 on the first step.
3294        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    /// Symmetric positive-definite tridiagonal, for CG.
3326    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    /// diag(1, 1, 2, 2, 3, 3): three distinct eigenvalues, each with multiplicity 2.
3512    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}