1use 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#[derive(Debug, Clone)]
16pub struct SVDResult<T> {
17 pub u: DMatrix<T>,
19 pub s: DVector<T>,
21 pub v: DMatrix<T>,
23 pub rank: usize,
25}
26
27#[derive(Debug, Clone)]
29pub struct TSVDConfig<T> {
30 pub rtol: T,
32}
33
34impl<T> TSVDConfig<T> {
35 pub fn new(rtol: T) -> Self {
36 Self { rtol }
37 }
38}
39
40const SVD_MAX_SWEEPS_PER_SINGULAR_VALUE: usize = 30;
52
53pub(crate) fn svd_max_sweeps(nrows: usize, ncols: usize) -> usize {
55 SVD_MAX_SWEEPS_PER_SINGULAR_VALUE * nrows.min(ncols).max(1)
57}
58
59fn 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
70pub(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#[inline]
99fn get_epsilon_for_svd<T: RealField + Copy>() -> T {
100 use std::any::Any;
101
102 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 T::from_f64(1e-15).unwrap_or(T::one() * T::from_f64(1e-15).unwrap_or(T::one()))
110 }
111}
112
113fn 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 let eps = get_epsilon_for_svd::<T>();
132
133 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
143pub(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 check_finite(matrix)?;
153 let svd = bounded_svd(matrix, svd_max_sweeps(matrix.nrows(), matrix.ncols()))?;
154
155 let u_matrix = svd.u.unwrap();
157 let s_vector = svd.singular_values; let v_t_matrix = svd.v_t.unwrap();
159
160 let rank = calculate_rank_from_vector(&s_vector, rtol);
163
164 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
172pub 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
195fn 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 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 break;
226 }
227 }
228
229 rank
230}
231
232fn 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 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 == Zero::zero() {
251 return 0;
252 }
253
254 for i in 0..dim {
256 let diag_abs = ComplexField::abs(r_matrix[(i, i)]);
257
258 if diag_abs < rtol * max_diag_abs {
260 rank = i;
261 break;
262 }
263 }
264
265 rank
266}
267
268pub 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 check_finite(matrix)?;
305
306 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 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 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 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 let r_truncated: DMatrix<T> = r_matrix.rows(0, qr_rank).into();
344 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 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 let q_truncated: DMatrix<T> = q_matrix.columns(0, qr_rank).into();
362 let u_full = &q_truncated * &svd_result.u;
363
364 let mut v_full = svd_result.v.clone();
369 permutation.inv_permute_rows(&mut v_full);
370
371 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
382pub(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 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
408pub fn tsvd_f64(matrix: &DMatrix<f64>, rtol: f64) -> Result<SVDResult<f64>, Error> {
410 tsvd(matrix, TSVDConfig::new(rtol))
411}
412
413pub fn tsvd_df64(matrix: &DMatrix<Df64>, rtol: Df64) -> Result<SVDResult<Df64>, Error> {
415 tsvd(matrix, TSVDConfig::new(rtol))
416}
417
418pub 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
427pub(crate) type SvdMats<T> = (Mat<T>, Vec<T>, Mat<T>);
429
430pub 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
462pub(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
491fn 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
515fn 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 #[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 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 #[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 #[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 #[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 #[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 #[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 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 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 T::one() / T::from((i + j + 1) as f64)
726 })
727 }
728
729 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 u * &DMatrix::from_diagonal(s) * &v.transpose()
742 }
743
744 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 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 let config = TSVDConfig::new(T::from(rtol));
773 let result = tsvd(&h, config).unwrap();
774
775 let h_reconstructed = reconstruct_matrix_generic(&result.u, &result.s, &result.v);
777
778 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 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 test_hilbert_reconstruction_generic::<Df64>(10, 1e-28, 1e-30);
813 }
814
815 #[test]
816 fn test_hilbert_100x100_f64_reconstruction() {
817 test_hilbert_reconstruction_generic::<f64>(100, 1e-12, 1e-12);
819 }
820
821 #[test]
822 fn test_hilbert_100x100_df64_reconstruction() {
823 test_hilbert_reconstruction_generic::<Df64>(100, 1e-28, 1e-28);
825 }
826}