Skip to main content

sparse_ir_sve/sve/
compute.rs

1//! Main SVE computation functions
2
3use crate::checks::{require_accuracy, require_nonzero_size};
4use crate::error::Error;
5use crate::fpu_check::FpuGuard;
6use crate::kernel::{AbstractKernel, ExpandableKernel, SVEKernel};
7use crate::matrix::Mat;
8use crate::numeric::CustomNumeric;
9
10use super::result::SVEResult;
11use super::strategy::{NonCentrosymmSVE, SVEStrategy};
12use super::types::{TworkType, safe_epsilon};
13
14/// Default relative cutoff for singular value truncation: `2 * T::epsilon()`
15///
16/// This is `2^-51` (about 4.44e-16) for `f64` and `2^-104` (about 4.93e-32)
17/// for `Df64`. Both SVE paths use it when `cutoff` is `None`.
18/// Convention-matched with libsparseir, whose `pre_postprocess` in
19/// `backend/cxx/include/sparseir/impl/sve_impl.ipp` (commit 4bc58ea) uses
20/// `T(2) * std::numeric_limits<T>::epsilon()` when the cutoff is NaN.
21fn default_cutoff<T: CustomNumeric>() -> T {
22    T::from_f64_unchecked(2.0) * T::epsilon()
23}
24
25/// Cutoff of [`SVEOptions::cutoff_from_epsilon`] relative to the required
26/// accuracy ε
27///
28/// A basis of singular functions accurate to ε keeps the singular values
29/// ≥ ε·s₀, plus one more to estimate its error; resolving the spectrum
30/// further down to 2·ε_work dominates the cost of the SVE in Df64. The cutoff
31/// is also the stopping tolerance of the ACA in the block SVDs, whose
32/// stopping test can underestimate the residual, so the factor leaves a
33/// margin: with 10⁻⁶·ε, the singular values such a basis uses deviated from
34/// the full spectrum by up to 2·10⁻⁴ relative, measured on the kernel
35/// e^{-Λy(x+1)/2} / (1 + e^{-Λy}) on [-1, 1]² with Λ = 10⁶, ε = 10⁻¹²; at
36/// 10⁻¹⁰·ε they agree to ≲ 4·10⁻¹¹ relative for Λ ≤ 10⁶,
37/// ε = 10⁻¹⁰…10⁻¹⁵.
38pub const ACCURACY_CUTOFF_FACTOR: f64 = 1e-10;
39
40/// Cutoff of [`SVEOptions::cutoff_from_epsilon`]:
41/// `max(2 * T::epsilon(), ACCURACY_CUTOFF_FACTOR * epsilon)`
42///
43/// For `epsilon` ≤ 4.4e-6 computed in `f64` this is [`default_cutoff`].
44fn basis_cutoff<T: CustomNumeric>(epsilon: f64) -> T {
45    CustomNumeric::max(
46        default_cutoff::<T>(),
47        T::from_f64_unchecked(ACCURACY_CUTOFF_FACTOR * epsilon),
48    )
49}
50
51/// How far down the block SVDs resolve the singular values
52#[derive(Clone, Copy, Debug)]
53enum Resolve {
54    /// To the working precision, `2 * T::epsilon()`
55    Full,
56    /// To [`basis_cutoff`], which is also the truncation cutoff
57    Basis,
58}
59
60/// Release unused memory back to the OS.
61///
62/// SVE computation allocates large temporary buffers for SVD.
63/// After computation, these are freed but the allocator may retain them.
64/// This function asks the allocator to return unused memory to the OS.
65///
66/// Supported platforms:
67/// - macOS: uses `malloc_zone_pressure_relief`
68/// - Linux (glibc): uses `malloc_trim`
69/// - Other platforms: no-op (memory is still freed, just not returned to OS immediately)
70#[inline]
71fn release_unused_memory() {
72    #[cfg(target_os = "macos")]
73    {
74        unsafe extern "C" {
75            fn malloc_zone_pressure_relief(zone: *mut std::ffi::c_void, goal: usize) -> usize;
76        }
77        unsafe { malloc_zone_pressure_relief(std::ptr::null_mut(), 0) };
78    }
79
80    // Only use malloc_trim on Linux with glibc (not musl)
81    #[cfg(all(target_os = "linux", target_env = "gnu"))]
82    {
83        unsafe extern "C" {
84            fn malloc_trim(pad: usize) -> i32;
85        }
86        unsafe { malloc_trim(0) };
87    }
88}
89
90/// The truncation of the spectrum ([`SVEOptions`])
91#[derive(Debug, Clone, Copy, PartialEq)]
92enum Cutoff {
93    /// `2 * machine epsilon` of the working precision
94    Default,
95    /// The given relative cutoff
96    Relative(f64),
97    /// [`basis_cutoff`] of the accuracy, also where the block SVDs stop
98    FromEpsilon,
99}
100
101/// Options of [`compute_sve_with`]
102///
103/// [`SVEOptions::new`] gives the defaults: the best accuracy of the working
104/// precision, which is chosen from the accuracy ([`TworkType::Auto`]), every
105/// singular value above `2 * machine epsilon` of it, and the even/odd
106/// expansion of a centrosymmetric kernel. Each method sets one option:
107///
108/// ```
109/// use sparse_ir_sve::{SVEOptions, TworkType};
110///
111/// let options = SVEOptions::new()
112///     .epsilon(1e-10)
113///     .max_num_svals(50)
114///     .twork(TworkType::Float64X2);
115/// ```
116#[derive(Debug, Clone, Copy, PartialEq)]
117pub struct SVEOptions {
118    epsilon: Option<f64>,
119    cutoff: Cutoff,
120    max_num_svals: Option<usize>,
121    twork: TworkType,
122    full_domain: bool,
123}
124
125impl Default for SVEOptions {
126    fn default() -> Self {
127        Self {
128            epsilon: None,
129            cutoff: Cutoff::Default,
130            max_num_svals: None,
131            twork: TworkType::Auto,
132            full_domain: false,
133        }
134    }
135}
136
137impl SVEOptions {
138    /// The default options
139    pub fn new() -> Self {
140        Self::default()
141    }
142
143    /// Required accuracy, in (0, 1); by default the best accuracy of the
144    /// working precision (about 1.6e-16 in Float64X2)
145    pub fn epsilon(mut self, epsilon: f64) -> Self {
146        self.epsilon = Some(epsilon);
147        self
148    }
149
150    /// Relative cutoff, in [0, 1]: the singular values below `cutoff` times
151    /// the largest one are discarded
152    ///
153    /// By default `2 * machine epsilon` of the working precision, about
154    /// 4.44e-16 in Float64 and 4.93e-32 in Float64X2 (the libsparseir
155    /// default). The SVD of each block already discards the singular values
156    /// below `2 * machine epsilon` times its largest one, so a smaller
157    /// cutoff has little effect. Replaces [`Self::cutoff_from_epsilon`].
158    pub fn cutoff(mut self, cutoff: f64) -> Self {
159        self.cutoff = Cutoff::Relative(cutoff);
160        self
161    }
162
163    /// Keep only the singular values that an expansion accurate to
164    /// `epsilon` uses
165    ///
166    /// Truncates the spectrum at `max(2 * machine epsilon, f * epsilon)`
167    /// times the largest singular value, with `f` =
168    /// [`ACCURACY_CUTOFF_FACTOR`]. In Float64X2 (`epsilon` below about 1e-8)
169    /// the block SVDs stop there, which is about 1.5 to 2.3 times faster
170    /// than the default, with about 20% fewer singular values. In Float64
171    /// the result is that of the default truncated at the cutoff, which for
172    /// `epsilon` ≤ 4.4e-6 is the same result.
173    ///
174    /// The singular values ≥ `epsilon` times the largest one, plus one more,
175    /// agree with those of the default to about 1e-10 relative, not to the
176    /// working precision. Replaces [`Self::cutoff`].
177    pub fn cutoff_from_epsilon(mut self) -> Self {
178        self.cutoff = Cutoff::FromEpsilon;
179        self
180    }
181
182    /// Maximum number of singular values to keep, positive
183    pub fn max_num_svals(mut self, max_num_svals: usize) -> Self {
184        self.max_num_svals = Some(max_num_svals);
185        self
186    }
187
188    /// Working precision; by default chosen from the accuracy
189    /// ([`TworkType::Auto`])
190    pub fn twork(mut self, twork: TworkType) -> Self {
191        self.twork = twork;
192        self
193    }
194
195    /// Whether to expand a centrosymmetric kernel over its full domain,
196    /// without exploiting its symmetry; false by default
197    ///
198    /// The singular values agree with the even/odd expansion up to rounding,
199    /// but the SVD is taken of one matrix with twice as many rows and columns
200    /// as each even/odd block (about four times the work), the singular
201    /// functions have no parity, and those of (nearly) degenerate singular
202    /// values may mix the even and odd sectors. Other kernels are always
203    /// expanded over their full domain.
204    pub fn full_domain(mut self, full_domain: bool) -> Self {
205        self.full_domain = full_domain;
206        self
207    }
208}
209
210/// The SVE of `kernel` with `options`
211///
212/// A centrosymmetric kernel ([`ReducedKernel`]) is block-diagonalized into
213/// its even and odd reduced kernels, whose singular functions have definite
214/// parity, unless [`SVEOptions::full_domain`] is set; any other kernel is
215/// expanded over its full domain `[xmin, xmax] × [ymin, ymax]`. The working
216/// precision is chosen from the accuracy unless [`SVEOptions::twork`] sets
217/// it. [`compute_sve`] takes the most common options as arguments.
218///
219/// [`ReducedKernel`]: crate::kernel::ReducedKernel
220///
221/// # Errors
222///
223/// * [`Error::InvalidParameter`] if the accuracy is not in (0, 1), the
224///   cutoff is not in [0, 1], or the maximum number of singular values is
225///   0; checked before any work
226/// * [`Error::NonFiniteInput`] if the discretized kernel has a NaN or
227///   infinite entry (e.g. a kernel value that overflows)
228/// * [`Error::DecompositionFailed`] if an SVD fails
229///
230/// # FPU State Warning
231///
232/// This function checks for dangerous FPU settings (Flush-to-Zero and
233/// Denormals-Are-Zero) that can cause incorrect results. If detected, it
234/// temporarily corrects the FPU state and prints a warning. If you see this
235/// warning, add `-fp-model precise` flag when compiling with Intel Fortran.
236pub fn compute_sve_with<K: ExpandableKernel>(
237    kernel: K,
238    options: &SVEOptions,
239) -> Result<SVEResult, Error> {
240    let (cutoff, resolve) = match options.cutoff {
241        Cutoff::Default => (None, Resolve::Full),
242        Cutoff::Relative(cutoff) => (Some(cutoff), Resolve::Full),
243        Cutoff::FromEpsilon => (None, Resolve::Basis),
244    };
245    let (epsilon, max_num_svals, twork) = (options.epsilon, options.max_num_svals, options.twork);
246    if options.full_domain {
247        let aca = !kernel.implements_reduced_kernel();
248        compute_sve_impl(
249            FullDomain { kernel, aca },
250            epsilon,
251            cutoff,
252            max_num_svals,
253            twork,
254            resolve,
255        )
256    } else {
257        compute_sve_impl(
258            KernelDomain(kernel),
259            epsilon,
260            cutoff,
261            max_num_svals,
262            twork,
263            resolve,
264        )
265    }
266}
267
268/// Main SVE computation function
269///
270/// Chooses the SVE strategy from the kernel ([`ExpandableKernel`]) and the
271/// working precision from epsilon. A centrosymmetric kernel
272/// ([`ReducedKernel`]) is block-diagonalized into its even and odd reduced
273/// kernels ([`CentrosymmSVE`]), whose singular functions have definite
274/// parity; any other kernel is expanded over its full domain
275/// `[xmin, xmax] × [ymin, ymax]` ([`NonCentrosymmSVE`]). This is
276/// [`compute_sve_with`] with these options; the others are those of
277/// [`SVEOptions::new`].
278///
279/// [`ReducedKernel`]: crate::kernel::ReducedKernel
280/// [`CentrosymmSVE`]: crate::unstable::sve::CentrosymmSVE
281///
282/// # Arguments
283///
284/// * `kernel` - The kernel to expand
285/// * `epsilon` - Required accuracy, in (0, 1). `None` selects the best
286///   accuracy of the working precision (about 1.6e-16 in Float64X2).
287/// * `cutoff` - Relative tolerance for singular value truncation: singular
288///   values smaller than `cutoff` times the largest singular value are
289///   discarded. `None` selects `2 * machine epsilon` of the working precision,
290///   about 4.44e-16 for Float64 and 4.93e-32 for Float64X2 (the libsparseir
291///   default). The SVD of each block already discards singular values below
292///   `2 * machine epsilon` times that block's largest singular value, so a
293///   smaller `cutoff` has little effect. Must be in [0, 1].
294/// * `max_num_svals` - Maximum number of singular values to keep
295/// * `twork` - Working precision type (Auto for automatic selection)
296///
297/// # Returns
298///
299/// SVEResult containing singular functions and values
300///
301/// # Errors
302///
303/// * [`Error::InvalidParameter`] if `epsilon` is not in (0, 1), `cutoff` is
304///   not in [0, 1], or `max_num_svals` is `Some(0)`; checked before any work
305/// * [`Error::NonFiniteInput`] if the discretized kernel has a NaN or
306///   infinite entry (e.g. a kernel value that overflows)
307/// * [`Error::DecompositionFailed`] if an SVD fails
308///
309/// # FPU State Warning
310///
311/// This function checks for dangerous FPU settings (Flush-to-Zero and Denormals-Are-Zero)
312/// that can cause incorrect results. If detected, it temporarily corrects the FPU state
313/// and prints a warning. If you see this warning, add `-fp-model precise` flag when
314/// compiling with Intel Fortran.
315pub fn compute_sve<K>(
316    kernel: K,
317    epsilon: Option<f64>,
318    cutoff: Option<f64>,
319    max_num_svals: Option<usize>,
320    twork: TworkType,
321) -> Result<SVEResult, Error>
322where
323    K: ExpandableKernel,
324{
325    compute_sve_impl(
326        KernelDomain(kernel),
327        epsilon,
328        cutoff,
329        max_num_svals,
330        twork,
331        Resolve::Full,
332    )
333}
334
335/// Check the parameters of [`compute_sve_with`]
336fn check_sve_parameters(
337    epsilon: Option<f64>,
338    cutoff: Option<f64>,
339    max_num_svals: Option<usize>,
340) -> Result<(), Error> {
341    require_accuracy("epsilon", epsilon)?;
342    if let Some(c) = cutoff {
343        if !(0.0..=1.0).contains(&c) {
344            return Err(Error::InvalidParameter {
345                name: "cutoff",
346                value: format!("{c:?}"),
347                reason: "must be in [0, 1]".to_string(),
348            });
349        }
350    }
351    require_nonzero_size("max_num_svals", max_num_svals)
352}
353
354/// The SVE strategy of a kernel, in the working precision chosen later
355trait StrategyOf {
356    fn strategy<T>(self, epsilon: f64) -> Result<Box<dyn SVEStrategy<T>>, Error>
357    where
358        T: CustomNumeric + Send + Sync + Clone + 'static;
359
360    /// Whether the blocks are decomposed by ACA in Df64 (see
361    /// [`compute_sve_with_precision`])
362    fn aca(&self) -> bool;
363}
364
365/// The strategy of the kernel ([`ExpandableKernel::sve_strategy`]): the
366/// even/odd blocks of a centrosymmetric kernel, otherwise the full domain
367struct KernelDomain<K>(K);
368
369impl<K: ExpandableKernel> StrategyOf for KernelDomain<K> {
370    fn strategy<T>(self, epsilon: f64) -> Result<Box<dyn SVEStrategy<T>>, Error>
371    where
372        T: CustomNumeric + Send + Sync + Clone + 'static,
373    {
374        self.0.sve_strategy(epsilon)
375    }
376
377    fn aca(&self) -> bool {
378        true
379    }
380}
381
382/// The full domain ([`NonCentrosymmSVE`]) for any kernel
383struct FullDomain<K> {
384    kernel: K,
385    /// Whether to take the Df64 block SVD by ACA: not for a centrosymmetric
386    /// kernel, whose full-domain block holds the even and odd spectra
387    /// interleaved in nearly degenerate pairs, where the ACA missed up to 5
388    /// singular values near the cutoff (logistic, Λ = 1e5 and 1e6,
389    /// ε = 1e-15)
390    aca: bool,
391}
392
393impl<K> StrategyOf for FullDomain<K>
394where
395    K: AbstractKernel + SVEKernel + Clone + 'static,
396{
397    fn strategy<T>(self, epsilon: f64) -> Result<Box<dyn SVEStrategy<T>>, Error>
398    where
399        T: CustomNumeric + Send + Sync + Clone + 'static,
400    {
401        Ok(Box::new(NonCentrosymmSVE::new(self.kernel, epsilon)?))
402    }
403
404    fn aca(&self) -> bool {
405        self.aca
406    }
407}
408
409/// The SVE of [`compute_sve`] and [`compute_sve_with`] by the strategy
410/// `sve`
411fn compute_sve_impl<S: StrategyOf>(
412    sve: S,
413    epsilon: Option<f64>,
414    cutoff: Option<f64>,
415    max_num_svals: Option<usize>,
416    twork: TworkType,
417    resolve: Resolve,
418) -> Result<SVEResult, Error> {
419    check_sve_parameters(epsilon, cutoff, max_num_svals)?;
420
421    // Protect computation from dangerous FPU settings (FZ/DAZ)
422    // This temporarily disables FZ/DAZ and restores them after computation
423    let _fpu_guard = FpuGuard::new_protect_computation();
424
425    // Determine safe epsilon and working precision
426    let (safe_epsilon, twork_actual) = safe_epsilon(epsilon, twork);
427
428    // Dispatch based on working precision
429    let aca = sve.aca();
430    let result = match twork_actual {
431        TworkType::Float64 => compute_sve_with_precision::<f64>(
432            sve.strategy(safe_epsilon)?,
433            safe_epsilon,
434            cutoff,
435            max_num_svals,
436            resolve,
437            aca,
438        ),
439        TworkType::Float64X2 => compute_sve_with_precision::<crate::Df64>(
440            sve.strategy(safe_epsilon)?,
441            safe_epsilon,
442            cutoff.map(crate::Df64::from),
443            max_num_svals,
444            resolve,
445            aca,
446        ),
447        _ => panic!("Invalid TworkType: {:?}", twork_actual),
448    };
449
450    // Release temporary memory back to OS after SVE computation
451    release_unused_memory();
452
453    result
454}
455
456/// [`compute_sve_impl`] in the working precision `T`
457fn compute_sve_with_precision<T>(
458    sve: Box<dyn SVEStrategy<T>>,
459    epsilon: f64,
460    cutoff: Option<T>,
461    max_num_svals: Option<usize>,
462    resolve: Resolve,
463    aca: bool,
464) -> Result<SVEResult, Error>
465where
466    T: CustomNumeric + Send + Sync + Clone + 'static,
467{
468    // 1. SVE strategy: `sve`
469
470    // The block SVDs resolve the spectrum to the working precision, which an
471    // explicit cutoff then only truncates in step 4 (the singular values of
472    // an SVD close to its tolerance are not accurate, see `tsvd_aca`), or,
473    // for `SVEOptions::cutoff_from_epsilon` in Df64, only down to its cutoff.
474    let (rtol_t, svd_rtol) = match resolve {
475        Resolve::Full => (cutoff.unwrap_or_else(default_cutoff::<T>), 0.0),
476        Resolve::Basis => {
477            let c = basis_cutoff::<T>(epsilon);
478            (c, c.to_f64())
479        }
480    };
481
482    // 2.-3. The SVD of each block, the blocks concurrently (they are
483    // independent). The work is counted as forming the blocks in full, in
484    // f64 operations (a Df64 operation costs `DF64_OP` of them, as in the
485    // ACA).
486    let is_f64 = std::any::TypeId::of::<T>() == std::any::TypeId::of::<f64>();
487    let entry_work = if is_f64 {
488        crate::cost::KERNEL_ENTRY
489    } else {
490        crate::cost::KERNEL_ENTRY * crate::cost::DF64_OP
491    };
492    let svds = if !aca || is_f64 {
493        // In f64, by the column-pivoted QR of the formed blocks, as before
494        // the ACA: the f64 SVE is that of main bitwise. Taken by ACA, its
495        // singular values agree to the working precision, but the number of
496        // those at the 2·ε_work noise floor differed in about one case out
497        // of eight, by up to 8; and the f64 SVE is cheap either way. Also
498        // in Df64 when `aca` is false (see `FullDomain::aca`).
499        let matrices = sve.matrices();
500        let work = matrices
501            .iter()
502            .map(|m| m.shape().0 * m.shape().1 * entry_work)
503            .sum();
504        crate::parallel::map_on_pool(matrices.len(), work, |b| {
505            crate::tsvd::compute_svd_dtensor(&matrices[b])
506        })
507    } else {
508        // In Df64, by adaptive cross approximation of the blocks, evaluated
509        // lazily: the SVD only touches their pivot rows and columns (ACA
510        // reads fewer entries but does more per entry read).
511        let blocks = sve.blocks();
512        let work = blocks
513            .iter()
514            .map(|block| block.nrows() * block.ncols() * entry_work)
515            .sum();
516        crate::parallel::map_on_pool(blocks.len(), work, |b| {
517            let block = &blocks[b];
518            crate::tsvd::compute_svd_aca(
519                block.nrows(),
520                block.ncols(),
521                &|i, j| block.entry(i, j),
522                svd_rtol,
523            )
524        })
525    };
526
527    let mut u_list = Vec::new();
528    let mut s_list = Vec::new();
529    let mut v_list = Vec::new();
530    for svd in svds {
531        let (u, s, v) = svd?;
532        u_list.push(u);
533        s_list.push(s);
534        v_list.push(v);
535    }
536
537    // 4. Truncate based on cutoff (default: 2 * T::epsilon(), see default_cutoff)
538    let (u_trunc, s_trunc, v_trunc) = truncate(u_list, s_list, v_list, rtol_t, max_num_svals);
539
540    // 5. Post-process to create SVEResult
541    sve.postprocess(u_trunc, s_trunc, v_trunc)
542}
543
544/// [`compute_sve`] by the dense CPQR-based SVD of the fully formed blocks
545/// ([`SVEStrategy::matrices`] and [`compute_svd_dtensor`]), as before the ACA
546/// (and as `compute_sve` still does in f64): the reference the ACA path is
547/// tested against
548///
549/// It forms every block and decomposes it in full, which in Float64X2 takes
550/// far longer than [`compute_sve`] (about 50 s, on 8 threads, for the kernel
551/// e^{-Λy(x+1)/2} / (1 + e^{-Λy}) with Λ = 10⁶), so it is meant for checking
552/// the result of [`compute_sve`] on a new kernel. The cutoff is the default one of
553/// [`compute_sve`], `2 * machine epsilon`.
554///
555/// With `full_domain`, the strategy of [`SVEOptions::full_domain`]
556/// ([`NonCentrosymmSVE`]) instead of that of the kernel.
557///
558/// # Errors
559///
560/// The errors of [`compute_sve`]
561///
562/// [`compute_svd_dtensor`]: crate::tsvd::compute_svd_dtensor
563pub fn compute_sve_dense<K>(
564    kernel: K,
565    epsilon: Option<f64>,
566    twork: TworkType,
567    full_domain: bool,
568) -> Result<SVEResult, Error>
569where
570    K: ExpandableKernel,
571{
572    fn run<T, K>(kernel: K, epsilon: f64, full_domain: bool) -> Result<SVEResult, Error>
573    where
574        T: CustomNumeric + Send + Sync + Clone + 'static,
575        K: ExpandableKernel,
576    {
577        let sve: Box<dyn SVEStrategy<T>> = if full_domain {
578            Box::new(NonCentrosymmSVE::new(kernel, epsilon)?)
579        } else {
580            kernel.sve_strategy::<T>(epsilon)?
581        };
582        let (mut u_list, mut s_list, mut v_list) = (Vec::new(), Vec::new(), Vec::new());
583        for matrix in sve.matrices() {
584            let (u, s, v) = crate::tsvd::compute_svd_dtensor(&matrix)?;
585            u_list.push(u);
586            s_list.push(s);
587            v_list.push(v);
588        }
589        let (u, s, v) = truncate(u_list, s_list, v_list, default_cutoff::<T>(), None);
590        sve.postprocess(u, s, v)
591    }
592    check_sve_parameters(epsilon, None, None)?;
593    let _fpu_guard = FpuGuard::new_protect_computation();
594    let (safe_epsilon, twork) = safe_epsilon(epsilon, twork);
595    match twork {
596        TworkType::Float64 => run::<f64, K>(kernel, safe_epsilon, full_domain),
597        TworkType::Float64X2 => run::<crate::Df64, K>(kernel, safe_epsilon, full_domain),
598        TworkType::Auto => unreachable!("safe_epsilon resolves TworkType::Auto"),
599    }
600}
601
602/// Truncate SVD results based on cutoff and maximum size
603///
604/// # Arguments
605///
606/// * `u_list` - List of U matrices
607/// * `s_list` - List of singular value vectors
608/// * `v_list` - List of V matrices
609/// * `rtol` - Relative tolerance for truncation
610/// * `max_num_svals` - Maximum number of singular values to keep
611///
612/// # Returns
613///
614/// Tuple of (truncated_u_list, truncated_s_list, truncated_v_list)
615pub(crate) fn truncate<T: CustomNumeric>(
616    u_list: Vec<Mat<T>>,
617    s_list: Vec<Vec<T>>,
618    v_list: Vec<Mat<T>>,
619    rtol: T,
620    max_num_svals: Option<usize>,
621) -> (Vec<Mat<T>>, Vec<Vec<T>>, Vec<Mat<T>>) {
622    let zero = T::zero();
623
624    // Validate
625    if let Some(max) = max_num_svals {
626        if max == 0 {
627            panic!("max_num_svals must be positive");
628        }
629    }
630    if rtol < zero || rtol > T::from_f64_unchecked(1.0) {
631        panic!("rtol must be in [0, 1]");
632    }
633
634    // Find global maximum singular value
635    let mut all_svals = Vec::new();
636    for s in &s_list {
637        all_svals.extend(s.iter().copied());
638    }
639
640    let max_sval = all_svals
641        .iter()
642        .max_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal))
643        .copied()
644        .unwrap_or(zero);
645
646    // Determine cutoff
647    let cutoff = if let Some(max_count) = max_num_svals {
648        if max_count < all_svals.len() {
649            let mut sorted = all_svals.clone();
650            sorted.sort_by(|a, b| b.partial_cmp(a).unwrap_or(std::cmp::Ordering::Equal));
651            let nth = sorted[max_count - 1];
652            if rtol * max_sval > nth {
653                rtol * max_sval
654            } else {
655                nth
656            }
657        } else {
658            rtol * max_sval
659        }
660    } else {
661        rtol * max_sval
662    };
663
664    // Truncate each result
665    let mut u_trunc = Vec::new();
666    let mut s_trunc = Vec::new();
667    let mut v_trunc = Vec::new();
668
669    for i in 0..s_list.len() {
670        let s = &s_list[i];
671        let u = &u_list[i];
672        let v = &v_list[i];
673
674        // Count singular values above cutoff
675        let mut n_keep = 0;
676        for &val in s.iter() {
677            if val >= cutoff {
678                n_keep += 1;
679            }
680        }
681
682        // Slice U: keep first n_keep columns. Preserve one output block per
683        // input block even when all singular values in that block are removed.
684        let u_shape = *u.shape();
685        let u_sliced = Mat::<T>::from_fn([u_shape.0, n_keep], |idx| u[[idx[0], idx[1]]]);
686        u_trunc.push(u_sliced);
687
688        s_trunc.push(s[..n_keep].to_vec());
689
690        // Slice V: keep first n_keep columns
691        let v_shape = *v.shape();
692        let v_sliced = Mat::<T>::from_fn([v_shape.0, n_keep], |idx| v[[idx[0], idx[1]]]);
693        v_trunc.push(v_sliced);
694    }
695
696    (u_trunc, s_trunc, v_trunc)
697}
698
699#[cfg(test)]
700mod tests {
701    use super::*;
702
703    /// The default cutoff is exactly `2 * machine epsilon` of each working
704    /// precision (issue #249); `Df64` epsilon is `f64::EPSILON^2 / 2 = 2^-105`.
705    #[test]
706    fn test_default_cutoff_is_two_machine_epsilon() {
707        assert_eq!(default_cutoff::<f64>(), 2.0 * f64::EPSILON);
708        assert_eq!(default_cutoff::<f64>(), 2f64.powi(-51));
709
710        let df64 = default_cutoff::<crate::Df64>();
711        assert_eq!(df64, crate::Df64::from(2f64.powi(-104)));
712        assert_eq!((df64.hi(), df64.lo()), (2f64.powi(-104), 0.0));
713    }
714
715    /// The cutoff of `SVEOptions::cutoff_from_epsilon` is `ACCURACY_CUTOFF_FACTOR *
716    /// epsilon`, floored at the default `2 * machine epsilon`, which it is for
717    /// f64 with epsilon <= 4.4e-6
718    #[test]
719    fn test_basis_cutoff() {
720        for epsilon in [1e-8, 1e-6, 4.4e-6] {
721            assert_eq!(basis_cutoff::<f64>(epsilon), default_cutoff::<f64>());
722        }
723        assert_eq!(basis_cutoff::<f64>(1e-4 / ACCURACY_CUTOFF_FACTOR), 1e-4);
724        assert_eq!(
725            basis_cutoff::<crate::Df64>(1e-30),
726            default_cutoff::<crate::Df64>()
727        );
728        assert_eq!(
729            basis_cutoff::<crate::Df64>(1e-10),
730            crate::Df64::from(ACCURACY_CUTOFF_FACTOR * 1e-10)
731        );
732    }
733
734    #[test]
735    fn test_truncate_by_rtol() {
736        let u = vec![Mat::<f64>::from_elem([3, 3], 1.0)];
737        let s = vec![vec![10.0, 5.0, 0.1]];
738        let v = vec![Mat::<f64>::from_elem([3, 3], 1.0)];
739
740        // rtol = 0.1, max_sval = 10.0, cutoff = 1.0
741        // Keep values >= 1.0: [10.0, 5.0]
742        let (_, s_trunc, _) = truncate(u, s, v, 0.1, None);
743
744        assert_eq!(s_trunc[0].len(), 2);
745        assert_eq!(s_trunc[0][0], 10.0);
746        assert_eq!(s_trunc[0][1], 5.0);
747    }
748
749    #[test]
750    fn test_truncate_by_max_size() {
751        let u = vec![Mat::<f64>::from_elem([3, 3], 1.0)];
752        let s = vec![vec![10.0, 5.0, 2.0]];
753        let v = vec![Mat::<f64>::from_elem([3, 3], 1.0)];
754
755        // max_num_svals = 2
756        let (_, s_trunc, _) = truncate(u, s, v, 0.0, Some(2));
757
758        assert_eq!(s_trunc[0].len(), 2);
759    }
760
761    #[test]
762    #[should_panic(expected = "max_num_svals must be positive")]
763    fn test_truncate_rejects_zero_max_size() {
764        let u = vec![Mat::<f64>::from_elem([1, 1], 1.0)];
765        let s = vec![vec![1.0]];
766        let v = vec![Mat::<f64>::from_elem([1, 1], 1.0)];
767
768        truncate(u, s, v, 0.0, Some(0));
769    }
770
771    #[test]
772    fn test_truncate_preserves_empty_blocks() {
773        let u = vec![
774            Mat::<f64>::from_elem([2, 1], 1.0),
775            Mat::<f64>::from_elem([2, 1], 2.0),
776        ];
777        let s = vec![vec![10.0], vec![1.0]];
778        let v = vec![
779            Mat::<f64>::from_elem([2, 1], 1.0),
780            Mat::<f64>::from_elem([2, 1], 2.0),
781        ];
782
783        let (u_trunc, s_trunc, v_trunc) = truncate(u, s, v, 0.5, None);
784
785        assert_eq!(s_trunc.len(), 2);
786        assert_eq!(s_trunc[0], vec![10.0]);
787        assert!(s_trunc[1].is_empty());
788        assert_eq!(*u_trunc[1].shape(), (2, 0));
789        assert_eq!(*v_trunc[1].shape(), (2, 0));
790    }
791
792    #[test]
793    #[should_panic(expected = "rtol must be in [0, 1]")]
794    fn test_truncate_invalid_rtol() {
795        let u = vec![Mat::<f64>::from_elem([1, 1], 1.0)];
796        let s = vec![vec![1.0]];
797        let v = vec![Mat::<f64>::from_elem([1, 1], 1.0)];
798
799        truncate(u, s, v, 1.5, None);
800    }
801}