Skip to main content

sparse_ir_sve/
tsvd.rs

1//! High-precision truncated SVD implementation using nalgebra
2//!
3//! This module provides QR + SVD based truncated SVD decomposition
4//! with support for extended precision arithmetic.
5
6use crate::Df64;
7use crate::col_piv_qr::ColPivQR;
8use crate::error::Error;
9use crate::matrix::Mat;
10use crate::numeric::CustomNumeric;
11use nalgebra::{ComplexField, DMatrix, DVector, RealField};
12use num_traits::{One, ToPrimitive, Zero};
13
14/// Result of SVD decomposition
15#[derive(Debug, Clone)]
16pub struct SVDResult<T> {
17    /// Left singular vectors (m × rank)
18    pub u: DMatrix<T>,
19    /// Singular values (rank)
20    pub s: DVector<T>,
21    /// Right singular vectors (n × rank)
22    pub v: DMatrix<T>,
23    /// Effective rank
24    pub rank: usize,
25}
26
27/// Configuration for TSVD computation
28#[derive(Debug, Clone)]
29pub struct TSVDConfig<T> {
30    /// Relative tolerance for rank determination
31    pub rtol: T,
32}
33
34impl<T> TSVDConfig<T> {
35    pub fn new(rtol: T) -> Self {
36        Self { rtol }
37    }
38}
39
40/// Maximum number of implicit-shift QR sweeps per singular value in the SVD
41///
42/// nalgebra's `try_svd` iterates until convergence when its `max_niter` is 0,
43/// and a NaN or an infinity never converges: the SVD then loops forever. The
44/// limit turns non-convergence into [`Error::DecompositionFailed`]. The SVDs of
45/// the SVE matrices of the kernels e^{-Λy(x+1)/2} / (1 ± e^{-Λy}) (the latter
46/// times y) on [-1, 1]² (Λ from 1 to 1e5, f64 and Df64) converge within 1.4
47/// sweeps per singular value; LAPACK's
48/// `dbdsqr` allows `MAXITR = 6` sweeps per singular value (the bound is
49/// convention-matched with it, no code is derived from it). 30 leaves a wide
50/// margin and still bounds the work on a matrix that does not converge.
51const SVD_MAX_SWEEPS_PER_SINGULAR_VALUE: usize = 30;
52
53/// Iteration limit of the SVD of an `nrows × ncols` matrix
54pub(crate) fn svd_max_sweeps(nrows: usize, ncols: usize) -> usize {
55    // Never 0, which nalgebra reads as "no limit"
56    SVD_MAX_SWEEPS_PER_SINGULAR_VALUE * nrows.min(ncols).max(1)
57}
58
59/// Reject a matrix with a NaN or infinite entry
60///
61/// Reports the first such entry in column-major (storage) order.
62fn check_finite<T>(matrix: &DMatrix<T>) -> Result<(), Error>
63where
64    T: ComplexField + ToPrimitive + Copy,
65{
66    let nrows = matrix.nrows();
67    check_finite_entries(matrix.as_slice(), |k| (k % nrows, k / nrows))
68}
69
70/// [`Error::NonFiniteInput`] (named `matrix`) for the first NaN or infinite
71/// value of `values`, the matrix entries at `index(k)`
72pub(crate) fn check_finite_entries<T>(
73    values: &[T],
74    index: impl Fn(usize) -> (usize, usize),
75) -> Result<(), Error>
76where
77    T: ComplexField + ToPrimitive + Copy,
78{
79    match values.iter().position(|x| !x.is_finite()) {
80        None => Ok(()),
81        Some(k) => {
82            let (row, col) = index(k);
83            Err(Error::NonFiniteInput {
84                name: "matrix",
85                index: vec![row, col],
86                value: ToPrimitive::to_f64(&values[k]).unwrap_or(f64::NAN),
87            })
88        }
89    }
90}
91
92/// Get appropriate epsilon value for SVD convergence based on type
93///
94/// Returns the machine epsilon (EPSILON constant) for the given type.
95/// This is preferred over approx::AbsDiffEq::default_epsilon() because
96/// the latter may return MIN_POSITIVE for Df64, which is too small and
97/// causes excessive iterations in SVD.
98#[inline]
99fn get_epsilon_for_svd<T: RealField + Copy>() -> T {
100    use std::any::Any;
101
102    // f64::EPSILON ≈ 2.22e-16, Df64::EPSILON ≈ 2.465e-32
103    if let Some(&eps) = (&f64::EPSILON as &dyn Any).downcast_ref::<T>() {
104        eps
105    } else if let Some(&eps) = (&crate::Df64::EPSILON as &dyn Any).downcast_ref::<T>() {
106        eps
107    } else {
108        // Fallback: use a reasonable default
109        T::from_f64(1e-15).unwrap_or(T::one() * T::from_f64(1e-15).unwrap_or(T::one()))
110    }
111}
112
113/// Full SVD by nalgebra's implicit-shift QR iteration, stopped after
114/// `max_niter` sweeps
115///
116/// The singular values are sorted in descending order. `max_niter` must be
117/// positive (nalgebra reads 0 as "no limit"). The matrix must not be empty.
118fn bounded_svd<T>(
119    matrix: &DMatrix<T>,
120    max_niter: usize,
121) -> Result<nalgebra::SVD<T, nalgebra::Dyn, nalgebra::Dyn>, Error>
122where
123    T: ComplexField + RealField + Copy,
124{
125    debug_assert!(max_niter > 0, "max_niter = 0 would not bound the SVD");
126    // Use type-appropriate epsilon for SVD convergence
127    // For f64: f64::EPSILON (約 2.22e-16)
128    // For Df64: Df64::EPSILON (約 2.465e-32)
129    // Note: We use EPSILON (machine epsilon) instead of default_epsilon() (from approx trait)
130    // because default_epsilon() may return MIN_POSITIVE for Df64, which is too small.
131    let eps = get_epsilon_for_svd::<T>();
132
133    // Perform FULL SVD decomposition with explicit epsilon
134    // try_svd automatically sorts singular values in descending order
135    matrix
136        .clone()
137        .try_svd(true, true, eps, max_niter)
138        .ok_or_else(|| Error::DecompositionFailed {
139            reason: format!("the SVD did not converge within {max_niter} iterations"),
140        })
141}
142
143/// [`svd_decompose`] returning an error instead of panicking
144pub(crate) fn try_svd_decompose<T>(matrix: &DMatrix<T>, rtol: f64) -> Result<SVDResult<T>, Error>
145where
146    T: ComplexField + RealField + Copy + nalgebra::RealField + ToPrimitive,
147{
148    if matrix.is_empty() {
149        return Err(Error::EmptyInput { name: "matrix" });
150    }
151    // A non-finite entry would exhaust the iteration limit; reject it early.
152    check_finite(matrix)?;
153    let svd = bounded_svd(matrix, svd_max_sweeps(matrix.nrows(), matrix.ncols()))?;
154
155    // Extract U, S, V matrices (already sorted by nalgebra)
156    let u_matrix = svd.u.unwrap();
157    let s_vector = svd.singular_values; // Sorted in descending order
158    let v_t_matrix = svd.v_t.unwrap();
159
160    // Calculate effective rank from sorted singular values
161    // Early termination is possible in rank calculation because values are sorted
162    let rank = calculate_rank_from_vector(&s_vector, rtol);
163
164    // Convert to thin SVD (truncate to effective rank)
165    let u = DMatrix::from(u_matrix.columns(0, rank));
166    let s = DVector::from(s_vector.rows(0, rank));
167    let v = DMatrix::from(v_t_matrix.rows(0, rank).transpose());
168
169    Ok(SVDResult { u, s, v, rank })
170}
171
172/// Perform SVD decomposition using nalgebra with sorted singular values
173///
174/// Note: This computes ALL singular values, not a truncated SVD.
175/// The truncation happens after SVD computation based on rtol.
176///
177/// # Arguments
178/// * `matrix` - Input matrix (m × n)
179/// * `rtol` - Relative tolerance for rank determination (used for rank calculation, not SVD convergence)
180///
181/// # Returns
182/// * `SVDResult` - Truncated SVD result with U, S, V matrices and rank
183///
184/// # Panics
185/// Panics if the matrix is empty, has a NaN or infinite entry, or the SVD
186/// iteration does not converge within its iteration limit
187/// ([`Error`] describes each case). [`tsvd`] reports these as errors.
188pub fn svd_decompose<T>(matrix: &DMatrix<T>, rtol: f64) -> SVDResult<T>
189where
190    T: ComplexField + RealField + Copy + nalgebra::RealField + ToPrimitive,
191{
192    try_svd_decompose(matrix, rtol).unwrap_or_else(|err| panic!("SVD computation failed: {err}"))
193}
194
195/// Calculate effective rank from sorted singular values
196///
197/// # Arguments
198/// * `singular_values` - Vector of singular values (sorted in descending order)
199/// * `rtol` - Relative tolerance for rank determination
200///
201/// # Returns
202/// * `usize` - Effective rank
203///
204/// # Note
205/// Since singular values are sorted in descending order by try_svd,
206/// this function can terminate early when a value below the threshold is found.
207fn calculate_rank_from_vector<T>(singular_values: &DVector<T>, rtol: f64) -> usize
208where
209    T: RealField + Copy + ToPrimitive,
210{
211    if singular_values.is_empty() {
212        return 0;
213    }
214
215    // First element is the maximum (sorted in descending order)
216    let max_sv = singular_values[0];
217    let threshold = max_sv * T::from_f64(rtol).unwrap_or(T::zero());
218
219    let mut rank = 0;
220    for &sv in singular_values.iter() {
221        if sv > threshold {
222            rank += 1;
223        } else {
224            // Early termination: since values are sorted, all remaining values are also below threshold
225            break;
226        }
227    }
228
229    rank
230}
231
232/// Calculate rank from R matrix diagonal elements
233fn calculate_rank_from_r<T: RealField>(r_matrix: &DMatrix<T>, rtol: T) -> usize
234where
235    T: ComplexField + RealField + Copy,
236{
237    let dim = r_matrix.nrows().min(r_matrix.ncols());
238    let mut rank = dim;
239
240    // Find the maximum diagonal element
241    let mut max_diag_abs = Zero::zero();
242    for i in 0..dim {
243        let diag_abs = ComplexField::abs(r_matrix[(i, i)]);
244        if diag_abs > max_diag_abs {
245            max_diag_abs = diag_abs;
246        }
247    }
248
249    // If max_diag_abs is zero, rank is zero
250    if max_diag_abs == Zero::zero() {
251        return 0;
252    }
253
254    // Check each diagonal element
255    for i in 0..dim {
256        let diag_abs = ComplexField::abs(r_matrix[(i, i)]);
257
258        // Check if the diagonal element is too small relative to the maximum diagonal element
259        if diag_abs < rtol * max_diag_abs {
260            rank = i;
261            break;
262        }
263    }
264
265    rank
266}
267
268/// Main TSVD function using QR + SVD approach
269///
270/// Computes the truncated SVD using the algorithm:
271/// 1. Apply QR decomposition to A to get Q and R
272/// 2. Compute SVD of R
273/// 3. Reconstruct final U and V matrices
274///
275/// # Arguments
276/// * `matrix` - Input matrix (m × n)
277/// * `config` - TSVD configuration
278///
279/// # Returns
280/// * `SVDResult` - Truncated SVD result
281///
282/// # Errors
283/// * [`Error::EmptyInput`] if the matrix has no rows or no columns
284/// * [`Error::InvalidParameter`] unless `0 < config.rtol < 1` (a NaN
285///   tolerance is rejected)
286/// * [`Error::NonFiniteInput`] if an entry of the matrix is NaN or infinite
287/// * [`Error::DecompositionFailed`] if the QR of the matrix overflows (its R
288///   factor has a non-finite entry) or the SVD iteration does not converge
289pub fn tsvd<T>(matrix: &DMatrix<T>, config: TSVDConfig<T>) -> Result<SVDResult<T>, Error>
290where
291    T: ComplexField
292        + RealField
293        + Copy
294        + nalgebra::RealField
295        + std::fmt::Debug
296        + ToPrimitive
297        + CustomNumeric,
298{
299    let (m, n) = matrix.shape();
300    check_tsvd_input(m, n, config.rtol)?;
301
302    // The SVD iteration never converges on a NaN or an infinity (it looped
303    // forever before the iteration limit of `bounded_svd`).
304    check_finite(matrix)?;
305
306    // Step 1: Apply QR decomposition to A using nalgebra with early termination
307    // Convert config.rtol (T) to T::RealField for QR decomposition
308    let qr_rtol = Some(config.rtol.clone().modulus());
309    let qr = ColPivQR::new_with_rtol(matrix.clone(), qr_rtol);
310    let q_matrix = qr.q();
311    let r_matrix = qr.r();
312    let permutation = qr.p();
313
314    // A finite matrix can still overflow in the QR (a column norm above
315    // f64::MAX). The input is valid, so a non-finite entry of R is a failure
316    // of the decomposition, not a non-finite input.
317    if let Err(Error::NonFiniteInput { index, value, .. }) = check_finite(&r_matrix) {
318        return Err(Error::DecompositionFailed {
319            reason: format!(
320                "the R factor of the QR decomposition has the non-finite entry {value} at index {index:?}"
321            ),
322        });
323    }
324
325    // Step 2: Apply QR-based rank estimation first
326    // Use type-specific epsilon for QR diagonal elements (more conservative than rtol)
327    let qr_rank = calculate_rank_from_r(
328        &r_matrix,
329        T::from_f64_unchecked(2.0) * get_epsilon_for_svd::<T>(),
330    );
331
332    if qr_rank == 0 {
333        // Matrix has zero rank
334        return Ok(SVDResult {
335            u: DMatrix::zeros(m, 0),
336            s: DVector::zeros(0),
337            v: DMatrix::zeros(n, 0),
338            rank: 0,
339        });
340    }
341
342    // Step 3: Truncate R to estimated rank and apply SVD
343    let r_truncated: DMatrix<T> = r_matrix.rows(0, qr_rank).into();
344    // Use rtol directly as T
345    let rtol_t = config.rtol;
346    let rtol_f64 = rtol_t.to_f64();
347    let svd_result = try_svd_decompose(&r_truncated, rtol_f64)?;
348
349    if svd_result.rank == 0 {
350        // Matrix has zero rank
351        return Ok(SVDResult {
352            u: DMatrix::zeros(m, 0),
353            s: DVector::zeros(0),
354            v: DMatrix::zeros(n, 0),
355            rank: 0,
356        });
357    }
358
359    // Step 4: Reconstruct full SVD
360    // U = Q * U_R (Q is (m, qr_rank), U_R is (qr_rank, svd_result.rank))
361    let q_truncated: DMatrix<T> = q_matrix.columns(0, qr_rank).into();
362    let u_full = &q_truncated * &svd_result.u;
363
364    // V = P^T * V_R (apply inverse permutation matrix)
365    // Since A*P = Q*R, we have A = Q*R*P^T
366    // After SVD of R: A = Q*U_R*S_R*V_R^T*P^T = U*S*V^T
367    // where V^T = V_R^T*P^T, so V = P^(-1)*V_R = P^T*V_R
368    let mut v_full = svd_result.v.clone();
369    permutation.inv_permute_rows(&mut v_full);
370
371    // S_full = S_R (already correct size)
372    let s_full = svd_result.s.clone();
373
374    Ok(SVDResult {
375        u: u_full,
376        s: s_full,
377        v: v_full,
378        rank: svd_result.rank,
379    })
380}
381
382/// Check that an `m × n` input of a truncated SVD is not empty and that
383/// `0 < rtol < 1`
384///
385/// # Errors
386/// * [`Error::EmptyInput`] if the matrix has no rows or no columns
387/// * [`Error::InvalidParameter`] unless `0 < rtol < 1` (a NaN tolerance is
388///   rejected)
389pub(crate) fn check_tsvd_input<T: RealField + CustomNumeric>(
390    m: usize,
391    n: usize,
392    rtol: T,
393) -> Result<(), Error> {
394    if m == 0 || n == 0 {
395        return Err(Error::EmptyInput { name: "matrix" });
396    }
397    // Written so that a NaN tolerance fails the check too
398    if !(rtol > Zero::zero() && rtol < One::one()) {
399        return Err(Error::InvalidParameter {
400            name: "rtol",
401            value: format!("{:?}", CustomNumeric::to_f64(rtol)),
402            reason: "must be in (0, 1)".to_string(),
403        });
404    }
405    Ok(())
406}
407
408/// Convenience function for f64 TSVD
409pub fn tsvd_f64(matrix: &DMatrix<f64>, rtol: f64) -> Result<SVDResult<f64>, Error> {
410    tsvd(matrix, TSVDConfig::new(rtol))
411}
412
413/// Convenience function for Df64 TSVD
414pub fn tsvd_df64(matrix: &DMatrix<Df64>, rtol: Df64) -> Result<SVDResult<Df64>, Error> {
415    tsvd(matrix, TSVDConfig::new(rtol))
416}
417
418/// Convenience function for Df64 TSVD from f64 matrix
419pub fn tsvd_df64_from_f64(matrix: &DMatrix<f64>, rtol: f64) -> Result<SVDResult<Df64>, Error> {
420    let matrix_df64 = DMatrix::from_fn(matrix.nrows(), matrix.ncols(), |i, j| {
421        Df64::from(matrix[(i, j)])
422    });
423    let rtol_df64 = Df64::from(rtol);
424    tsvd(&matrix_df64, TSVDConfig::new(rtol_df64))
425}
426
427/// Thin SVD `(U, s, V)` as matrices of the element type
428pub(crate) type SvdMats<T> = (Mat<T>, Vec<T>, Mat<T>);
429
430/// Compute SVD for DTensor using nalgebra-based TSVD
431///
432/// Supports both f64 and Df64 types. Uses the dense CPQR-based [`tsvd`], which
433/// is robust for arbitrary matrices.
434///
435/// # Errors
436/// The errors of [`tsvd`]: [`Error::EmptyInput`], [`Error::NonFiniteInput`]
437/// and [`Error::DecompositionFailed`]
438///
439/// # Panics
440/// Panics if `T` is neither `f64` nor `Df64`
441pub fn compute_svd_dtensor<T: CustomNumeric + 'static>(
442    matrix: &Mat<T>,
443) -> Result<SvdMats<T>, Error> {
444    let (m, n) = *matrix.shape();
445    in_element_type::<T>(
446        0.0,
447        |config| {
448            tsvd(
449                &DMatrix::from_fn(m, n, |i, j| f64::convert_from(matrix[[i, j]])),
450                config,
451            )
452        },
453        |config| {
454            tsvd(
455                &DMatrix::from_fn(m, n, |i, j| Df64::convert_from(matrix[[i, j]])),
456                config,
457            )
458        },
459    )
460}
461
462/// Truncated SVD of the `m × n` matrix whose entries are `entry(i, j)`, by
463/// the ACA-accelerated [`crate::aca::tsvd_aca`], which evaluates the entries
464/// only at its pivot rows and columns
465///
466/// Intended for the smooth, rapidly rank-decaying SVE kernel matrices, where
467/// it is several times faster than [`compute_svd_dtensor`]. Singular values
468/// below `rtol` times the largest one are dropped; `rtol` is raised to at
469/// least 2·ε of the element type (pass 0 for that tolerance, as in
470/// [`compute_svd_dtensor`]). Falls back to the dense path if ACA does not
471/// converge.
472///
473/// # Errors
474/// The errors of [`crate::aca::tsvd_aca`]
475///
476/// # Panics
477/// Panics if `T` is neither `f64` nor `Df64`
478pub(crate) fn compute_svd_aca<T: CustomNumeric + 'static>(
479    m: usize,
480    n: usize,
481    entry: &(dyn Fn(usize, usize) -> T + Sync),
482    rtol: f64,
483) -> Result<SvdMats<T>, Error> {
484    in_element_type::<T>(
485        rtol,
486        |config| crate::aca::tsvd_aca(m, n, |i, j| f64::convert_from(entry(i, j)), config),
487        |config| crate::aca::tsvd_aca(m, n, |i, j| Df64::convert_from(entry(i, j)), config),
488    )
489}
490
491/// Run the `f64` or the `Df64` SVD, whichever matches `T`, with the relative
492/// tolerance `max(rtol, 2ε)` for the `ε` of that type, and return the result
493/// as matrices of `T` (conversions between equal types are exact)
494///
495/// # Panics
496/// Panics if `T` is neither `f64` nor `Df64`
497fn in_element_type<T: CustomNumeric + 'static>(
498    rtol: f64,
499    svd_f64: impl FnOnce(TSVDConfig<f64>) -> Result<SVDResult<f64>, Error>,
500    svd_df64: impl FnOnce(TSVDConfig<Df64>) -> Result<SVDResult<Df64>, Error>,
501) -> Result<SvdMats<T>, Error> {
502    use std::any::TypeId;
503
504    if TypeId::of::<T>() == TypeId::of::<f64>() {
505        let rtol = rtol.max(2.0 * f64::EPSILON);
506        Ok(svd_result_to_mats(svd_f64(TSVDConfig::new(rtol))?))
507    } else if TypeId::of::<T>() == TypeId::of::<Df64>() {
508        let rtol = CustomNumeric::max(Df64::from(rtol), Df64::from(2.0) * Df64::epsilon());
509        Ok(svd_result_to_mats(svd_df64(TSVDConfig::new(rtol))?))
510    } else {
511        panic!("SVD is only implemented for f64 and Df64");
512    }
513}
514
515/// Split an [`SVDResult`] into matrices `(U, s, V)`, converting each element
516fn svd_result_to_mats<R: CustomNumeric + 'static, T: CustomNumeric>(
517    result: SVDResult<R>,
518) -> SvdMats<T> {
519    let u = Mat::<T>::from_fn([result.u.nrows(), result.u.ncols()], |idx| {
520        T::convert_from(result.u[(idx[0], idx[1])])
521    });
522    let s: Vec<T> = result.s.iter().map(|&x| T::convert_from(x)).collect();
523    let v = Mat::<T>::from_fn([result.v.nrows(), result.v.ncols()], |idx| {
524        T::convert_from(result.v[(idx[0], idx[1])])
525    });
526    (u, s, v)
527}
528
529#[cfg(test)]
530mod tests {
531    use super::*;
532    use nalgebra::DMatrix;
533    use num_traits::cast::ToPrimitive;
534
535    #[test]
536    fn test_svd_identity_matrix() {
537        let matrix = DMatrix::<f64>::identity(3, 3);
538        let result = svd_decompose(&matrix, 1e-12);
539
540        assert_eq!(result.rank, 3);
541        assert_eq!(result.s.len(), 3);
542        assert_eq!(result.u.nrows(), 3);
543        assert_eq!(result.u.ncols(), 3);
544        assert_eq!(result.v.nrows(), 3);
545        assert_eq!(result.v.ncols(), 3);
546    }
547
548    #[test]
549    fn test_tsvd_identity_matrix() {
550        let matrix = DMatrix::<f64>::identity(3, 3);
551        let result = tsvd_f64(&matrix, 1e-12).unwrap();
552
553        assert_eq!(result.rank, 3);
554        assert_eq!(result.s.len(), 3);
555    }
556
557    #[test]
558    fn test_tsvd_rank_one() {
559        let matrix = DMatrix::<f64>::from_fn(3, 3, |i, j| (i + 1) as f64 * (j + 1) as f64);
560        let result = tsvd_f64(&matrix, 1e-12).unwrap();
561
562        assert_eq!(result.rank, 1);
563    }
564
565    /// A matrix with no rows or no columns is empty, not only 0 × 0; an empty
566    /// batch produces such shapes.
567    #[test]
568    fn test_tsvd_empty_matrix() {
569        for (rows, cols) in [(0, 0), (0, 3), (3, 0)] {
570            let matrix = DMatrix::<f64>::zeros(rows, cols);
571            assert!(
572                matches!(
573                    tsvd_f64(&matrix, 1e-12),
574                    Err(Error::EmptyInput { name: "matrix" })
575                ),
576                "{rows} x {cols}"
577            );
578        }
579    }
580
581    /// A 4 x 4 matrix of full rank with `bad` at (1, 2)
582    fn matrix_with_entry(bad: f64) -> DMatrix<f64> {
583        DMatrix::<f64>::from_fn(4, 4, |i, j| {
584            if (i, j) == (1, 2) {
585                bad
586            } else {
587                1.0 / (1.0 + i as f64 + j as f64) + if i == j { 1.0 } else { 0.0 }
588            }
589        })
590    }
591
592    fn assert_non_finite_at_1_2<T>(result: Result<SVDResult<T>, Error>, bad: f64) {
593        match result {
594            Err(Error::NonFiniteInput { name, index, value }) => {
595                assert_eq!(name, "matrix");
596                assert_eq!(index, vec![1, 2]);
597                assert!(value.is_nan() == bad.is_nan() && (bad.is_nan() || value == bad));
598            }
599            Err(other) => panic!("expected NonFiniteInput, got {other:?}"),
600            Ok(_) => panic!("expected NonFiniteInput, got Ok"),
601        }
602    }
603
604    /// Before the fix, `tsvd` passed `max_niter = 0` (unbounded) to nalgebra's
605    /// `try_svd`, which never converges on a NaN or an infinity: these calls
606    /// did not return.
607    #[test]
608    fn test_tsvd_rejects_non_finite_input() {
609        for bad in [f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
610            let matrix = matrix_with_entry(bad);
611            assert_non_finite_at_1_2(tsvd_f64(&matrix, 1e-12), bad);
612            assert_non_finite_at_1_2(tsvd_df64_from_f64(&matrix, 1e-28), bad);
613            let matrix_df64 = matrix.map(Df64::from);
614            assert_non_finite_at_1_2(tsvd_df64(&matrix_df64, Df64::from(1e-28)), bad);
615        }
616    }
617
618    /// A NaN tolerance passed the `rtol <= 0 || rtol >= 1` check before the
619    /// fix and gave a silent rank-0 result. The message shows the value as a
620    /// number for Df64 too.
621    #[test]
622    fn test_tsvd_rejects_nan_tolerance() {
623        let matrix = matrix_with_entry(0.5);
624        let expected = "invalid rtol = NaN: must be in (0, 1)";
625
626        let err = tsvd_f64(&matrix, f64::NAN).unwrap_err();
627        assert!(matches!(err, Error::InvalidParameter { name: "rtol", .. }));
628        assert_eq!(err.to_string(), expected);
629
630        let matrix_df64 = matrix.map(Df64::from);
631        let err = tsvd_df64(&matrix_df64, Df64::from(f64::NAN)).unwrap_err();
632        assert_eq!(err.to_string(), expected);
633    }
634
635    #[test]
636    fn test_compute_svd_dtensor_reports_errors() {
637        let empty = Mat::<f64>::zeros([0, 3]);
638        assert_eq!(
639            compute_svd_dtensor(&empty).unwrap_err(),
640            Error::EmptyInput { name: "matrix" }
641        );
642        let nan = Mat::<f64>::from_fn([2, 2], |idx| {
643            if idx[0] == 1 && idx[1] == 0 {
644                f64::NAN
645            } else {
646                1.0
647            }
648        });
649        assert!(matches!(
650            compute_svd_dtensor(&nan),
651            Err(Error::NonFiniteInput { name: "matrix", .. })
652        ));
653        let nan_df64 = Mat::<Df64>::from_fn([2, 2], |idx| {
654            Df64::from(if idx[0] == 1 && idx[1] == 0 {
655                f64::NAN
656            } else {
657                1.0
658            })
659        });
660        assert!(matches!(
661            compute_svd_dtensor(&nan_df64),
662            Err(Error::NonFiniteInput { name: "matrix", .. })
663        ));
664    }
665
666    /// A finite matrix whose QR overflows: the norm of its column, about
667    /// 2.5e308, exceeds f64::MAX. The input is valid, so this is a failure of
668    /// the decomposition. Before the fix it was reported as a non-finite
669    /// entry of the input matrix, at the index of the infinite entry of R.
670    #[test]
671    fn test_tsvd_reports_overflow_of_the_r_factor_as_decomposition_failure() {
672        let matrix = DMatrix::<f64>::from_column_slice(2, 1, &[f64::MAX, f64::MAX]);
673        match tsvd_f64(&matrix, 1e-12) {
674            Err(Error::DecompositionFailed { reason }) => assert!(
675                reason.starts_with("the R factor of the QR decomposition has the non-finite entry"),
676                "{reason}"
677            ),
678            other => panic!("expected DecompositionFailed, got {other:?}"),
679        }
680    }
681
682    /// A tolerance out of range is shown in scientific notation, not with
683    /// hundreds of digits.
684    #[test]
685    fn test_tsvd_shows_an_invalid_tolerance_compactly() {
686        let matrix = matrix_with_entry(0.5);
687        let err = tsvd_f64(&matrix, 1e300).unwrap_err();
688        assert_eq!(err.to_string(), "invalid rtol = 1e300: must be in (0, 1)");
689    }
690
691    /// Non-convergence of the SVD iteration is reported as an error. A NaN
692    /// never converges, so it exhausts any iteration limit; `bounded_svd`
693    /// does not check finiteness itself.
694    #[test]
695    fn test_bounded_svd_reports_non_convergence() {
696        let matrix = matrix_with_entry(f64::NAN);
697        assert!(matches!(
698            bounded_svd(&matrix, 50),
699            Err(Error::DecompositionFailed { reason })
700                if reason == "the SVD did not converge within 50 iterations"
701        ));
702
703        // The limit used for real matrices is ample for a finite one.
704        let finite = matrix_with_entry(0.5);
705        let svd = bounded_svd(&finite, svd_max_sweeps(4, 4)).unwrap();
706        let reconstructed = svd.recompose().unwrap();
707        assert!((reconstructed - &finite).norm() < 1e-14 * finite.norm());
708    }
709
710    #[test]
711    #[should_panic(expected = "matrix has the non-finite entry inf at index [1, 2]")]
712    fn test_svd_decompose_panics_on_non_finite_input() {
713        svd_decompose(&matrix_with_entry(f64::INFINITY), 1e-12);
714    }
715
716    /// Create Hilbert matrix of size n x n with generic type
717    /// H[i,j] = 1 / (i + j + 1)
718    fn create_hilbert_matrix_generic<T>(n: usize) -> DMatrix<T>
719    where
720        T: nalgebra::RealField + From<f64> + Copy + std::ops::Div<Output = T>,
721    {
722        DMatrix::from_fn(n, n, |i, j| {
723            // For high precision types like Df64, we need to do the division in type T
724            // to preserve precision, not in f64
725            T::one() / T::from((i + j + 1) as f64)
726        })
727    }
728
729    /// Reconstruct matrix from SVD with generic type: A = U * S * V^T
730    fn reconstruct_matrix_generic<T>(
731        u: &DMatrix<T>,
732        s: &nalgebra::DVector<T>,
733        v: &DMatrix<T>,
734    ) -> DMatrix<T>
735    where
736        T: nalgebra::RealField + Copy,
737    {
738        // A = U * S * V^T
739        // U: (m × k), S: (k), V: (n × k)
740        // Result: (m × n)
741        u * &DMatrix::from_diagonal(s) * &v.transpose()
742    }
743
744    /// Calculate Frobenius norm of matrix with generic type
745    fn frobenius_norm_generic<T>(matrix: &DMatrix<T>) -> f64
746    where
747        T: nalgebra::RealField + Copy + ToPrimitive,
748    {
749        let mut sum = 0.0;
750        for i in 0..matrix.nrows() {
751            for j in 0..matrix.ncols() {
752                let val = matrix[(i, j)].to_f64().unwrap_or(0.0);
753                sum += val * val;
754            }
755        }
756        sum.sqrt()
757    }
758
759    /// Generic Hilbert matrix reconstruction test
760    fn test_hilbert_reconstruction_generic<T>(n: usize, rtol: f64, expected_max_error: f64)
761    where
762        T: nalgebra::RealField
763            + From<f64>
764            + Copy
765            + ToPrimitive
766            + std::fmt::Debug
767            + crate::numeric::CustomNumeric,
768    {
769        let h = create_hilbert_matrix_generic::<T>(n);
770
771        // Compute TSVD with specified tolerance
772        let config = TSVDConfig::new(T::from(rtol));
773        let result = tsvd(&h, config).unwrap();
774
775        // Reconstruct matrix
776        let h_reconstructed = reconstruct_matrix_generic(&result.u, &result.s, &result.v);
777
778        // Calculate reconstruction error (in the same type T to preserve precision)
779        let error_matrix = &h - &h_reconstructed;
780        let error_norm = frobenius_norm_generic(&error_matrix);
781        let relative_error = error_norm / frobenius_norm_generic(&h);
782
783        // Check that reconstruction error is within expected bounds
784        assert!(
785            relative_error <= expected_max_error,
786            "Relative reconstruction error {} exceeds expected maximum {}",
787            relative_error,
788            expected_max_error
789        );
790    }
791
792    #[test]
793    fn test_hilbert_5x5_f64_reconstruction() {
794        test_hilbert_reconstruction_generic::<f64>(5, 1e-12, 1e-14);
795    }
796
797    #[test]
798    fn test_hilbert_5x5_df64_reconstruction() {
799        test_hilbert_reconstruction_generic::<Df64>(5, 1e-28, 1e-28);
800    }
801
802    #[test]
803    fn test_hilbert_10x10_f64_reconstruction() {
804        test_hilbert_reconstruction_generic::<f64>(10, 1e-12, 1e-12);
805    }
806
807    #[test]
808    fn test_hilbert_10x10_df64_reconstruction() {
809        // Note: 10x10 Hilbert matrix has very large condition number (~1e13)
810        // Even with Df64, reconstruction is limited by nalgebra's matrix operations
811        // which may not fully utilize Df64's precision in intermediate calculations
812        test_hilbert_reconstruction_generic::<Df64>(10, 1e-28, 1e-30);
813    }
814
815    #[test]
816    fn test_hilbert_100x100_f64_reconstruction() {
817        // Large matrix test with f64 - expect reasonable performance
818        test_hilbert_reconstruction_generic::<f64>(100, 1e-12, 1e-12);
819    }
820
821    #[test]
822    fn test_hilbert_100x100_df64_reconstruction() {
823        // Large matrix test with Df64 - expect high precision but longer execution time
824        test_hilbert_reconstruction_generic::<Df64>(100, 1e-28, 1e-28);
825    }
826}