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}