Skip to main content

sparse_ir_sve/sve/
strategy.rs

1//! SVE computation strategies
2
3use crate::error::Error;
4use crate::gauss::{Rule, sve_legendre};
5use crate::kernel::{AbstractKernel, ReducedKernel, SVEHints, SVEKernel, SymmetryType};
6use crate::kernelmatrix::{matrix_from_gauss_noncentrosymmetric, matrix_from_gauss_with_segments};
7use crate::matrix::Mat;
8use crate::numeric::CustomNumeric;
9use crate::poly::PiecewiseLegendrePolyVector;
10
11use super::result::SVEResult;
12use super::utils::{
13    SvdBlock, canonicalize_signs, extend_to_full_domain, half_domain_segments, merge_blocks,
14    remove_weights, svd_to_polynomials,
15};
16
17/// A discretized, weighted kernel matrix `A[i, j] = K(x_i, y_j) √w_i √w'_j`
18/// (Gauss points `x_i`, `y_j`, weights `w_i`, `w'_j`) whose entries are
19/// evaluated on demand
20///
21/// The SVD of the double-double SVE, by adaptive cross approximation, only
22/// touches a few rows and columns of `A`, so the matrix is not formed.
23pub struct KernelBlock<'a, T> {
24    nrows: usize,
25    ncols: usize,
26    entry: Box<dyn Fn(usize, usize) -> T + Sync + 'a>,
27}
28
29impl<'a, T: CustomNumeric> KernelBlock<'a, T> {
30    /// Block of size `nrows × ncols` with entries `entry(i, j)`
31    pub fn new(nrows: usize, ncols: usize, entry: impl Fn(usize, usize) -> T + Sync + 'a) -> Self {
32        Self {
33            nrows,
34            ncols,
35            entry: Box::new(entry),
36        }
37    }
38
39    /// Number of rows (Gauss points in x)
40    pub fn nrows(&self) -> usize {
41        self.nrows
42    }
43
44    /// Number of columns (Gauss points in y)
45    pub fn ncols(&self) -> usize {
46        self.ncols
47    }
48
49    /// Entry `A[i, j]`
50    pub fn entry(&self, i: usize, j: usize) -> T {
51        (self.entry)(i, j)
52    }
53}
54
55/// Trait for SVE computation strategies
56pub trait SVEStrategy<T: CustomNumeric> {
57    /// Compute the discretized matrices for SVD
58    fn matrices(&self) -> Vec<Mat<T>>;
59
60    /// The discretized, weighted kernel blocks to decompose, the matrices of
61    /// [`Self::matrices`] with their entries evaluated on demand
62    ///
63    /// `compute_sve` decomposes these in double-double by adaptive cross
64    /// approximation, which reads only a few rows and columns of each (in
65    /// f64 it decomposes [`Self::matrices`] as before). The default forms the
66    /// matrices; the strategies of this crate evaluate the kernel lazily.
67    fn blocks(&self) -> Vec<KernelBlock<'_, T>>
68    where
69        T: Send + Sync + 'static,
70    {
71        self.matrices()
72            .into_iter()
73            .map(|m| {
74                let (nrows, ncols) = *m.shape();
75                KernelBlock::new(nrows, ncols, move |i, j| m[[i, j]])
76            })
77            .collect()
78    }
79
80    /// Post-process SVD results to create SVEResult
81    ///
82    /// # Errors
83    ///
84    /// The errors of [`SVEResult::new`]
85    fn postprocess(
86        &self,
87        u_list: Vec<Mat<T>>,
88        s_list: Vec<Vec<T>>,
89        v_list: Vec<Mat<T>>,
90    ) -> Result<SVEResult, Error>;
91}
92
93/// Sampling-based SVE computation
94///
95/// This is the general SVE computation strategy that works with discretized kernels.
96/// It does NOT know about symmetry - it just processes a given discretized kernel matrix.
97///
98/// # Responsibility
99///
100/// - Remove weights from SVD results
101/// - Convert to polynomials on the domain specified by segments
102/// - Domain extension is caller's responsibility
103pub struct SamplingSVE<T>
104where
105    T: CustomNumeric + Send + Sync + 'static,
106{
107    segments_x: Vec<T>,
108    segments_y: Vec<T>,
109    gauss_x: Rule<T>,
110    gauss_y: Rule<T>,
111    #[allow(dead_code)]
112    epsilon: f64,
113    n_gauss: usize,
114}
115
116impl<T> SamplingSVE<T>
117where
118    T: CustomNumeric + Send + Sync + 'static,
119{
120    /// Create a new SamplingSVE
121    ///
122    /// This takes only the geometric information needed for polynomial conversion,
123    /// not the kernel itself.
124    pub fn new(
125        segments_x: Vec<T>,
126        segments_y: Vec<T>,
127        gauss_x: Rule<T>,
128        gauss_y: Rule<T>,
129        epsilon: f64,
130        n_gauss: usize,
131    ) -> Self {
132        Self {
133            segments_x,
134            segments_y,
135            gauss_x,
136            gauss_y,
137            epsilon,
138            n_gauss,
139        }
140    }
141
142    /// The weighted block `K(x_i, y_j) √w_i √w'_j` of the kernel function `k`
143    /// on this discretization, as the matrices of the strategies weight it
144    pub(crate) fn weighted_block<'a>(
145        &'a self,
146        k: impl Fn(T, T) -> T + Sync + 'a,
147    ) -> KernelBlock<'a, T> {
148        let wx: Vec<T> = self.gauss_x.w.iter().map(|w| w.sqrt()).collect();
149        let wy: Vec<T> = self.gauss_y.w.iter().map(|w| w.sqrt()).collect();
150        let (x, y) = (&self.gauss_x.x, &self.gauss_y.x);
151        KernelBlock::new(x.len(), y.len(), move |i, j| k(x[i], y[j]) * wx[i] * wy[j])
152    }
153
154    /// Post-process a single SVD result to create polynomials
155    ///
156    /// This converts SVD results to piecewise Legendre polynomials
157    /// on the domain specified by segments (e.g., [0, xmax] for reduced kernels).
158    ///
159    /// # Errors
160    ///
161    /// The errors of the crate-internal `svd_to_polynomials`, and
162    /// [`Error::EmptyInput`] if the
163    /// SVD result has no singular values
164    pub fn postprocess_single(
165        &self,
166        u: &Mat<T>,
167        s: &[T],
168        v: &Mat<T>,
169    ) -> Result<
170        (
171            PiecewiseLegendrePolyVector,
172            Vec<f64>,
173            PiecewiseLegendrePolyVector,
174        ),
175        Error,
176    > {
177        let (u_polys, s, v_polys) = self.postprocess_block(u, s, v)?;
178        Ok((
179            PiecewiseLegendrePolyVector::new(u_polys)?,
180            s,
181            PiecewiseLegendrePolyVector::new(v_polys)?,
182        ))
183    }
184
185    /// [`Self::postprocess_single`] returning plain vectors, which may be
186    /// empty
187    fn postprocess_block(&self, u: &Mat<T>, s: &[T], v: &Mat<T>) -> Result<SvdBlock, Error> {
188        // 1. Remove weights
189        // Both U and V have rows corresponding to Gauss points, so is_row=true for both
190        let u_unweighted = remove_weights(u, self.gauss_x.w.as_slice(), true);
191        let v_unweighted = remove_weights(v, self.gauss_y.w.as_slice(), true);
192
193        // 2. Convert to polynomials
194        let gauss_rule_f64 = sve_legendre::<f64>(self.n_gauss);
195        let u_polys = svd_to_polynomials(
196            &u_unweighted,
197            &self.segments_x,
198            &gauss_rule_f64,
199            self.n_gauss,
200        )?;
201        let v_polys = svd_to_polynomials(
202            &v_unweighted,
203            &self.segments_y,
204            &gauss_rule_f64,
205            self.n_gauss,
206        )?;
207
208        // Note: No domain extension here - that's the caller's responsibility
209        Ok((u_polys, s.iter().map(|&x| x.to_f64()).collect(), v_polys))
210    }
211}
212
213/// Centrosymmetric SVE computation
214///
215/// Exploits even/odd symmetry for efficient computation.
216/// This manages the symmetry: creating reduced kernels, extending to full domain, and merging.
217pub struct CentrosymmSVE<T, K>
218where
219    T: CustomNumeric + Send + Sync + 'static,
220    K: ReducedKernel + SVEKernel,
221{
222    kernel: K,
223    epsilon: f64,
224    hints: K::SVEHintsType<T>,
225    #[allow(dead_code)]
226    n_gauss: usize,
227
228    // Geometric information (positive domain [0, xmax])
229    #[allow(dead_code)]
230    segments_x: Vec<T>,
231    #[allow(dead_code)]
232    segments_y: Vec<T>,
233    gauss_x: Rule<T>,
234    gauss_y: Rule<T>,
235
236    // The general SVE processor (no symmetry knowledge)
237    sampling_sve: SamplingSVE<T>,
238}
239
240impl<T, K> CentrosymmSVE<T, K>
241where
242    T: CustomNumeric + Send + Sync + Clone + 'static,
243    K: ReducedKernel + SVEKernel + Clone,
244    K::SVEHintsType<T>: SVEHints<T> + Clone,
245{
246    /// Create a new CentrosymmSVE
247    ///
248    /// # Errors
249    ///
250    /// * [`Error::InvalidParameter`] if the domain of the kernel is not
251    ///   symmetric (`xmin != -xmax` or `ymin != -ymax`), or if the SVE hints
252    ///   of the kernel give segments that are not finite and strictly
253    ///   increasing
254    pub fn new(kernel: K, epsilon: f64) -> Result<Self, Error> {
255        // The even/odd SVE covers [0, xmax] x [0, ymax] and mirrors it, so it
256        // would silently drop the part of an asymmetric domain.
257        for (name, min, max) in [
258            ("kernel domain [xmin, xmax]", kernel.xmin(), kernel.xmax()),
259            ("kernel domain [ymin, ymax]", kernel.ymin(), kernel.ymax()),
260        ] {
261            if min != -max {
262                return Err(Error::InvalidParameter {
263                    name,
264                    value: format!("[{min:?}, {max:?}]"),
265                    reason: "must be symmetric about 0 for a centrosymmetric kernel".to_string(),
266                });
267            }
268        }
269        let hints = kernel.sve_hints::<T>(epsilon);
270
271        // The half [0, xmax] x [0, ymax] of the segments; the even and odd
272        // blocks hold their mirror images
273        let segments_x = half_domain_segments(&hints.segments_x());
274        let segments_y = half_domain_segments(&hints.segments_y());
275        let n_gauss = hints.ngauss();
276
277        // Create composite Gauss rules
278        let rule = sve_legendre::<T>(n_gauss);
279        let gauss_x = rule.piecewise(&segments_x)?;
280        let gauss_y = rule.piecewise(&segments_y)?;
281
282        // Create the general SVE processor
283        let sampling_sve = SamplingSVE::new(
284            segments_x.clone(),
285            segments_y.clone(),
286            gauss_x.clone(),
287            gauss_y.clone(),
288            epsilon,
289            n_gauss,
290        );
291
292        Ok(Self {
293            kernel,
294            epsilon,
295            hints,
296            n_gauss,
297            segments_x,
298            segments_y,
299            gauss_x,
300            gauss_y,
301            sampling_sve,
302        })
303    }
304
305    /// Compute reduced kernel matrix for given symmetry
306    fn compute_reduced_matrix(&self, symmetry: SymmetryType) -> Mat<T> {
307        // Compute K_red(x, y) = K(x, y) + sign * K(x, -y)
308        // where x, y are in [0, xmax] and [0, ymax]
309        let discretized = matrix_from_gauss_with_segments(
310            &self.kernel,
311            &self.gauss_x,
312            &self.gauss_y,
313            symmetry,
314            &self.hints,
315        );
316
317        // Apply weights for SVE
318
319        discretized.apply_weights_for_sve()
320    }
321
322    /// Extend polynomials from [0, xmax] to [-xmax, xmax]
323    fn extend_result_to_full_domain(
324        &self,
325        result: SvdBlock,
326        symmetry: SymmetryType,
327    ) -> Result<SvdBlock, Error> {
328        let (u, s, v) = result;
329
330        // Extend u and v from [0, xmax] to [-xmax, xmax]
331        let u_full = extend_to_full_domain(u, symmetry)?;
332        let v_full = extend_to_full_domain(v, symmetry)?;
333
334        Ok((u_full, s, v_full))
335    }
336}
337
338impl<T, K> SVEStrategy<T> for CentrosymmSVE<T, K>
339where
340    T: CustomNumeric + Send + Sync + Clone + 'static,
341    K: ReducedKernel + SVEKernel + Clone,
342    K::SVEHintsType<T>: SVEHints<T> + Clone,
343{
344    fn matrices(&self) -> Vec<Mat<T>> {
345        // Compute reduced kernels for even and odd symmetries
346        let even_matrix = self.compute_reduced_matrix(SymmetryType::Even);
347        let odd_matrix = self.compute_reduced_matrix(SymmetryType::Odd);
348
349        vec![even_matrix, odd_matrix]
350    }
351
352    fn blocks(&self) -> Vec<KernelBlock<'_, T>> {
353        // The weighted reduced kernels K(x, y) ± K(x, -y), evaluated lazily
354        [SymmetryType::Even, SymmetryType::Odd]
355            .into_iter()
356            .map(|symmetry| {
357                self.sampling_sve
358                    .weighted_block(move |x, y| self.kernel.compute_reduced(x, y, symmetry))
359            })
360            .collect()
361    }
362
363    fn postprocess(
364        &self,
365        u_list: Vec<Mat<T>>,
366        s_list: Vec<Vec<T>>,
367        v_list: Vec<Mat<T>>,
368    ) -> Result<SVEResult, Error> {
369        // Process even and odd results using SamplingSVE (which doesn't know
370        // about symmetry). Keep plain vectors until the merge: truncation can
371        // empty a block (keeping only the largest singular value empties the
372        // odd one), and a PiecewiseLegendrePolyVector cannot be empty.
373        let result_even = self
374            .sampling_sve
375            .postprocess_block(&u_list[0], &s_list[0], &v_list[0])?;
376        let result_odd = self
377            .sampling_sve
378            .postprocess_block(&u_list[1], &s_list[1], &v_list[1])?;
379
380        // Now extend to full domain (this is where symmetry comes in)
381        let result_even_full =
382            self.extend_result_to_full_domain(result_even, SymmetryType::Even)?;
383        let result_odd_full = self.extend_result_to_full_domain(result_odd, SymmetryType::Odd)?;
384
385        // Merge the results (at least one singular value is kept)
386        merge_blocks(result_even_full, result_odd_full, self.epsilon)
387    }
388}
389
390/// Non-centrosymmetric SVE computation
391///
392/// This strategy computes the kernel matrix directly over the full domain
393/// [xmin, xmax] × [ymin, ymax] given by the kernel's [`SVEHints`]. No symmetry
394/// exploitation is performed, so it works for any kernel.
395///
396/// Centrosymmetric kernels are also expanded correctly, on the same
397/// segments of the full domain. The singular values then agree with
398/// [`CentrosymmSVE`] up to rounding, but the SVD is taken of a single matrix
399/// with twice as many rows and columns as each even/odd block, and the
400/// singular functions carry no parity tag.
401///
402/// The SVD sign gauge is fixed by demanding `u_l(xmax) >= 0`, as
403/// [`CentrosymmSVE`] does and as libsparseir's `SamplingSVE::postprocess`
404/// does via `canonicalize` (convention-matched with
405/// `backend/cxx/include/sparseir/impl/sve_impl.ipp`, libsparseir commit
406/// 4bc58ea).
407#[allow(dead_code)]
408pub struct NonCentrosymmSVE<T, K>
409where
410    T: CustomNumeric + Send + Sync + 'static,
411    K: AbstractKernel + SVEKernel,
412{
413    kernel: K,
414    epsilon: f64,
415    hints: K::SVEHintsType<T>,
416    n_gauss: usize,
417
418    // Geometric information (full domain [-xmax, xmax])
419    segments_x: Vec<T>,
420    segments_y: Vec<T>,
421    gauss_x: Rule<T>,
422    gauss_y: Rule<T>,
423
424    // The general SVE processor
425    sampling_sve: SamplingSVE<T>,
426}
427
428impl<T, K> NonCentrosymmSVE<T, K>
429where
430    T: CustomNumeric + Send + Sync + Clone + 'static,
431    K: AbstractKernel + SVEKernel + Clone,
432    K::SVEHintsType<T>: SVEHints<T> + Clone,
433{
434    /// Create a new NonCentrosymmSVE
435    ///
436    /// # Errors
437    ///
438    /// [`Error::InvalidParameter`] if the SVE hints of the kernel give
439    /// segments that are not finite and strictly increasing, or that do not
440    /// run from `xmin` to `xmax` (`ymin` to `ymax`). Hints written for the
441    /// half domain `[0, xmax]` of sparse-ir 0.15 are rejected here: the SVE
442    /// over their segments would expand only part of the kernel.
443    pub fn new(kernel: K, epsilon: f64) -> Result<Self, Error> {
444        let hints = kernel.sve_hints::<T>(epsilon);
445
446        // Get segments for full domain [xmin, xmax], [ymin, ymax]
447        let segments_x = hints.segments_x();
448        let segments_y = hints.segments_y();
449        let n_gauss = hints.ngauss();
450
451        // Create composite Gauss rules for full domain
452        let rule = sve_legendre::<T>(n_gauss);
453        let gauss_x = rule.piecewise(&segments_x)?;
454        let gauss_y = rule.piecewise(&segments_y)?;
455        check_segment_ends(
456            "SVE hints segments_x",
457            &segments_x,
458            kernel.xmin(),
459            kernel.xmax(),
460        )?;
461        check_segment_ends(
462            "SVE hints segments_y",
463            &segments_y,
464            kernel.ymin(),
465            kernel.ymax(),
466        )?;
467
468        // Create the general SVE processor
469        let sampling_sve = SamplingSVE::new(
470            segments_x.clone(),
471            segments_y.clone(),
472            gauss_x.clone(),
473            gauss_y.clone(),
474            epsilon,
475            n_gauss,
476        );
477
478        Ok(Self {
479            kernel,
480            epsilon,
481            hints,
482            n_gauss,
483            segments_x,
484            segments_y,
485            gauss_x,
486            gauss_y,
487            sampling_sve,
488        })
489    }
490
491    /// Compute kernel matrix for non-centrosymmetric kernel
492    fn compute_matrix(&self) -> Mat<T> {
493        // Compute K(x, y) directly over full domain
494        let discretized = matrix_from_gauss_noncentrosymmetric(
495            &self.kernel,
496            &self.gauss_x,
497            &self.gauss_y,
498            &self.hints,
499        );
500
501        // Apply weights for SVE
502        discretized.apply_weights_for_sve()
503    }
504}
505
506/// `InvalidParameter` unless the segment boundaries (at least one segment,
507/// as `Rule::piecewise` checks) start at `min` and end at `max`
508///
509/// Exact comparison, as in `SegmentHints::new`: the boundaries are meant to
510/// be the bounds of the domain, not values near them.
511fn check_segment_ends<T: CustomNumeric>(
512    name: &'static str,
513    segments: &[T],
514    min: f64,
515    max: f64,
516) -> Result<(), Error> {
517    let (first, last) = (segments[0].to_f64(), segments[segments.len() - 1].to_f64());
518    if first != min || last != max {
519        return Err(Error::InvalidParameter {
520            name,
521            value: format!("[{first:?}, {last:?}]"),
522            reason: format!(
523                "must run from the lower to the upper bound of the domain, [{min:?}, {max:?}]"
524            ),
525        });
526    }
527    Ok(())
528}
529
530impl<T, K> SVEStrategy<T> for NonCentrosymmSVE<T, K>
531where
532    T: CustomNumeric + Send + Sync + Clone + 'static,
533    K: AbstractKernel + SVEKernel + Clone,
534    K::SVEHintsType<T>: SVEHints<T> + Clone,
535{
536    fn matrices(&self) -> Vec<Mat<T>> {
537        // Single matrix for non-centrosymmetric kernel
538        vec![self.compute_matrix()]
539    }
540
541    fn blocks(&self) -> Vec<KernelBlock<'_, T>> {
542        // The weighted kernel over the full domain, evaluated lazily
543        vec![
544            self.sampling_sve
545                .weighted_block(|x, y| self.kernel.compute(x, y)),
546        ]
547    }
548
549    fn postprocess(
550        &self,
551        u_list: Vec<Mat<T>>,
552        s_list: Vec<Vec<T>>,
553        v_list: Vec<Mat<T>>,
554    ) -> Result<SVEResult, Error> {
555        // Process single result using SamplingSVE. The functions are
556        // already on the full domain. Fix the sign gauge u_l(xmax) >= 0 as
557        // CentrosymmSVE does in merge_results.
558        let (u_polys, s, v_polys) = self
559            .sampling_sve
560            .postprocess_block(&u_list[0], &s_list[0], &v_list[0])?;
561        let (u_polys, v_polys) = canonicalize_signs(u_polys, v_polys);
562        // A matrix of rank 0 leaves empty vectors; SVEResult::new reports the
563        // empty `s`.
564        SVEResult::new(
565            PiecewiseLegendrePolyVector::from_polys_unchecked(u_polys),
566            s,
567            PiecewiseLegendrePolyVector::from_polys_unchecked(v_polys),
568            self.epsilon,
569        )
570    }
571}