Skip to main content

sparse_ir_sve/sve/
utils.rs

1//! Utility functions for SVE computation
2
3use crate::error::Error;
4use crate::gauss::Rule;
5use crate::interpolation1d::legendre_collocation_matrix;
6use crate::kernel::SymmetryType;
7use crate::matrix::{Mat, Mat3};
8use crate::numeric::CustomNumeric;
9use crate::poly::{PiecewiseLegendrePoly, PiecewiseLegendrePolyVector};
10
11/// Remove Gauss weights from SVD matrix
12///
13/// This function removes the square root of Gauss quadrature weights that were
14/// applied before SVD computation. This is the inverse operation of
15/// `DiscretizedKernel::apply_weights_for_sve()`.
16///
17/// # Arguments
18///
19/// * `matrix` - SVD result matrix (U or V^T)
20/// * `weights` - Gauss quadrature weights
21/// * `is_row` - If true, remove from rows; if false, remove from columns
22///
23/// # Returns
24///
25/// Matrix with weights removed
26pub(crate) fn remove_weights<T: CustomNumeric>(
27    matrix: &Mat<T>,
28    weights: &[T],
29    is_row: bool,
30) -> Mat<T> {
31    let mut result = matrix.clone();
32
33    let shape = *result.shape();
34    if is_row {
35        // Remove weights from rows (for U matrix)
36        for i in 0..shape.0 {
37            let sqrt_weight = weights[i].sqrt();
38            for j in 0..shape.1 {
39                result[[i, j]] = result[[i, j]] / sqrt_weight;
40            }
41        }
42    } else {
43        // Remove weights from columns (for V matrix)
44        for j in 0..shape.1 {
45            let sqrt_weight = weights[j].sqrt();
46            for i in 0..shape.0 {
47                result[[i, j]] = result[[i, j]] / sqrt_weight;
48            }
49        }
50    }
51
52    result
53}
54
55/// Mirror half-domain segment boundaries onto the full domain
56///
57/// Maps `[0, s_1, ..., s_n]` to `[-s_n, ..., -s_1, -0, s_1, ..., s_n]`.
58/// This is the knot layout of the singular functions of a centrosymmetric
59/// SVE, so a full-domain discretization built from these segments uses the
60/// mirror images of the half-domain segments. A kernel's full-domain
61/// [`SVEHints`](crate::kernel::SVEHints) can be built from half-domain ones
62/// with it.
63///
64/// The input must start at zero, as [`half_domain_segments`] returns it.
65pub fn mirror_segments_to_full_domain<T: CustomNumeric>(half: &[T]) -> Vec<T> {
66    let mut full = Vec::with_capacity((2 * half.len()).saturating_sub(1));
67    full.extend(half.iter().rev().map(|&s| -s));
68    full.extend(half.iter().skip(1).copied());
69    full
70}
71
72/// The half-domain segment boundaries the SVE of a centrosymmetric kernel
73/// discretizes
74///
75/// Maps the boundaries of the full domain to `[0, s_1, ..., s_n]`: those in
76/// `(0, max]` with 0 added. On boundaries symmetric about 0 this is the
77/// inverse of [`mirror_segments_to_full_domain`].
78pub fn half_domain_segments<T: CustomNumeric>(full: &[T]) -> Vec<T> {
79    std::iter::once(T::zero())
80        .chain(full.iter().copied().filter(|&s| s > T::zero()))
81        .collect()
82}
83
84/// Extend polynomials from [0, xmax] to [-xmax, xmax] using symmetry
85///
86/// # Arguments
87///
88/// * `polys` - Polynomials defined on [0, xmax]
89/// * `symmetry` - Even or Odd symmetry type
90///
91/// # Returns
92///
93/// Polynomials extended to full domain [-xmax, xmax], with `symm` set from
94/// `symmetry` and `l` kept unchanged
95///
96/// # Mathematical Background
97///
98/// For Even symmetry (sign = +1): f(-x) = f(x)
99/// For Odd symmetry (sign = -1): f(-x) = -f(x)
100///
101/// Legendre polynomial parity: P_n(-x) = (-1)^n P_n(x)
102///
103/// # Errors
104///
105/// * [`Error::InvalidParameter`] if a polynomial does not start at x = 0
106///   (the half domain [0, xmax]): its mirrored knots would decrease or
107///   overlap
108/// * The errors of [`PiecewiseLegendrePoly::new`] for the extended knots
109pub(crate) fn extend_to_full_domain(
110    polys: Vec<PiecewiseLegendrePoly>,
111    symmetry: SymmetryType,
112) -> Result<Vec<PiecewiseLegendrePoly>, Error> {
113    let sign = symmetry.sign() as f64;
114    let symm = symmetry.sign(); // Preserve symmetry: +1 for even, -1 for odd
115
116    // Create poly_flip_x: alternating signs for Legendre polynomials
117    // This accounts for P_n(-x) = (-1)^n P_n(x)
118    let n_poly_coeffs = if !polys.is_empty() {
119        polys[0].data.shape().0
120    } else {
121        return Ok(Vec::new());
122    };
123
124    let poly_flip_x: Vec<f64> = (0..n_poly_coeffs)
125        .map(|i| if i % 2 == 0 { 1.0 } else { -1.0 })
126        .collect();
127
128    polys
129        .into_iter()
130        .map(|poly| {
131            if poly.knots[0] != 0.0 {
132                return Err(Error::InvalidParameter {
133                    name: "polys",
134                    value: format!("a polynomial on [{:?}, {:?}]", poly.xmin, poly.xmax),
135                    reason: "must be defined on [0, xmax] (the half domain)".to_string(),
136                });
137            }
138            // Create full segments from this polynomial's knots: [-xmax, ..., 0, ..., xmax]
139            let full_segments = mirror_segments_to_full_domain(&poly.knots);
140
141            // Normalize by 1/sqrt(2) and convert to f64
142            let pos_data =
143                Mat::<f64>::from_fn(poly.data.dims(), |idx| poly.data[idx] / 2.0_f64.sqrt());
144
145            // Create negative part by reversing columns and applying signs
146            let pos_shape = *pos_data.shape();
147            let mut neg_data = Mat::<f64>::from_fn([pos_shape.0, pos_shape.1], |idx| {
148                // Reverse column order: map column j to column (n_cols - 1 - j)
149                let reversed_col = pos_shape.1 - 1 - idx[1];
150                pos_data[[idx[0], reversed_col]]
151            });
152
153            // Apply poly_flip_x and sign to negative part
154            for (i, &flip_sign) in poly_flip_x.iter().enumerate() {
155                let coeff_sign = flip_sign * sign;
156                for j in 0..pos_shape.1 {
157                    neg_data[[i, j]] *= coeff_sign;
158                }
159            }
160
161            // Combine negative and positive parts (concatenate along axis 1)
162            let combined_data = Mat::<f64>::from_fn([pos_shape.0, pos_shape.1 * 2], |idx| {
163                if idx[1] < pos_shape.1 {
164                    neg_data[[idx[0], idx[1]]]
165                } else {
166                    pos_data[[idx[0], idx[1] - pos_shape.1]]
167                }
168            });
169
170            // Create complete polynomial with full segments
171            // Preserve symmetry from even/odd decomposition
172            PiecewiseLegendrePoly::new(
173                combined_data,
174                full_segments,
175                poly.l,
176                None, // delta_x will be computed automatically
177                symm, // Preserve symmetry: +1 for even, -1 for odd
178            )
179        })
180        .collect()
181}
182
183/// Convert SVD matrix to piecewise Legendre polynomials
184///
185/// This function converts SVD results (U or V matrices) to piecewise Legendre
186/// polynomial representation.
187///
188/// # Arguments
189///
190/// * `u_or_v` - SVD result matrix (rows = Gauss points, cols = singular values)
191/// * `segments` - Segment boundaries
192/// * `gauss_rule` - Gauss quadrature rule
193/// * `n_gauss` - Number of Gauss points per segment
194///
195/// # Returns
196///
197/// Vector of piecewise Legendre polynomials. The `k`-th polynomial has `l = k`,
198/// its column in `u_or_v`; for a centrosymmetric SVE that is the index within
199/// the even or odd block, which `merge_results` renumbers.
200///
201/// # Errors
202///
203/// * [`Error::InvalidParameter`] if `segments` has fewer than 2 entries
204/// * The errors of [`PiecewiseLegendrePoly::new`] for the segments
205pub(crate) fn svd_to_polynomials<T: CustomNumeric>(
206    u_or_v: &Mat<T>,
207    segments: &[T],
208    gauss_rule: &Rule<f64>,
209    n_gauss: usize,
210) -> Result<Vec<PiecewiseLegendrePoly>, Error> {
211    if segments.len() < 2 {
212        return Err(Error::InvalidParameter {
213            name: "segments",
214            value: format!("{} boundaries", segments.len()),
215            reason: "must have at least 2 entries".to_string(),
216        });
217    }
218    let n_segments = segments.len() - 1;
219    let n_svals = u_or_v.shape().1;
220    let n_rows = u_or_v.shape().0;
221
222    // Reshape to 3D: (n_gauss, n_segments, n_svals)
223    // Rows beyond the row count of u_or_v (if any) are left as zero
224    let mut tensor_3d = Mat3::<f64>::zeros([n_gauss, n_segments, n_svals]);
225    for i in 0..n_gauss {
226        for j in 0..n_segments {
227            for k in 0..n_svals {
228                let row_idx = j * n_gauss + i;
229                if row_idx < n_rows {
230                    tensor_3d[[i, j, k]] = u_or_v[[row_idx, k]].to_f64();
231                } else {
232                    tensor_3d[[i, j, k]] = 0.0;
233                }
234            }
235        }
236    }
237
238    // Create Legendre collocation matrix
239    let cmat = legendre_collocation_matrix(gauss_rule);
240
241    // Transform to Legendre basis
242    let cmat_shape = *cmat.shape();
243    let mut u_data = Mat3::<f64>::zeros([cmat_shape.0, n_segments, n_svals]);
244    for j in 0..n_segments {
245        for k in 0..n_svals {
246            for i in 0..cmat_shape.0 {
247                let mut sum = 0.0;
248                for l in 0..n_gauss {
249                    sum += cmat[[i, l]] * tensor_3d[[l, j, k]];
250                }
251                u_data[[i, j, k]] = sum;
252            }
253        }
254    }
255
256    // Apply segment length normalization: sqrt(0.5 * delta_segment)
257    let mut dsegs = Vec::new();
258    for i in 0..segments.len() - 1 {
259        dsegs.push(segments[i + 1].to_f64() - segments[i].to_f64());
260    }
261
262    let u_data_shape = *u_data.shape();
263    for j in 0..n_segments {
264        let norm = (0.5 * dsegs[j]).sqrt();
265        for i in 0..u_data_shape.0 {
266            for k in 0..n_svals {
267                u_data[[i, j, k]] *= norm;
268            }
269        }
270    }
271
272    // Create polynomials
273    let mut polys = Vec::new();
274    let knots: Vec<f64> = segments.iter().map(|&x| x.to_f64()).collect();
275    let delta_x: Vec<f64> = knots.windows(2).map(|w| w[1] - w[0]).collect();
276
277    for k in 0..n_svals {
278        // Extract data for this singular value: (n_coeffs, n_segments)
279        let u_data_shape = u_data.shape();
280        let mut data = Mat::<f64>::zeros([u_data_shape.0, n_segments]);
281        for i in 0..u_data_shape.0 {
282            for j in 0..n_segments {
283                data[[i, j]] = u_data[[i, j, k]];
284            }
285        }
286
287        polys.push(PiecewiseLegendrePoly::new(
288            data,
289            knots.clone(),
290            k as i32,
291            Some(delta_x.clone()),
292            0, // no symmetry
293        )?);
294    }
295
296    Ok(polys)
297}
298
299/// Canonicalize singular function signs
300///
301/// Fix the gauge freedom in SVD by demanding u[l](xmax) >= 0, where xmax is
302/// the right end of the domain of u[l]. The pairs (u[l], v[l]) are flipped
303/// together.
304pub(crate) fn canonicalize_signs(
305    u_polys: Vec<PiecewiseLegendrePoly>,
306    v_polys: Vec<PiecewiseLegendrePoly>,
307) -> (Vec<PiecewiseLegendrePoly>, Vec<PiecewiseLegendrePoly>) {
308    u_polys
309        .into_iter()
310        .zip(v_polys)
311        .map(|(u, v)| {
312            if u.evaluate(u.xmax) < 0.0 {
313                (u.negated(), v.negated())
314            } else {
315                (u, v)
316            }
317        })
318        .unzip()
319}
320
321/// Singular functions and values of one SVD block: `(u, s, v)`
322///
323/// Plain vectors, unlike [`PiecewiseLegendrePolyVector`], can be empty.
324pub(crate) type SvdBlock = (
325    Vec<PiecewiseLegendrePoly>,
326    Vec<f64>,
327    Vec<PiecewiseLegendrePoly>,
328);
329
330/// Merge even and odd SVE results
331///
332/// Either block may be empty (a `PiecewiseLegendrePolyVector` built through
333/// its public field): truncating an SVE can remove all singular values of one
334/// parity.
335///
336/// # Arguments
337///
338/// * `result_even` - (u, s, v) for even symmetry
339/// * `result_odd` - (u, s, v) for odd symmetry
340/// * `epsilon` - Accuracy parameter
341///
342/// # Returns
343///
344/// Merged SVEResult with singular values sorted in decreasing order. The `l`
345/// of each returned polynomial is its position in this merged result, not
346/// its index within the even or odd block.
347///
348/// # Errors
349///
350/// [`Error::EmptyInput`] if both blocks are empty: an SVE result has at least
351/// one singular value
352pub(crate) fn merge_results(
353    result_even: (
354        PiecewiseLegendrePolyVector,
355        Vec<f64>,
356        PiecewiseLegendrePolyVector,
357    ),
358    result_odd: (
359        PiecewiseLegendrePolyVector,
360        Vec<f64>,
361        PiecewiseLegendrePolyVector,
362    ),
363    epsilon: f64,
364) -> Result<crate::sve::SVEResult, Error> {
365    let (u_even, s_even, v_even) = result_even;
366    let (u_odd, s_odd, v_odd) = result_odd;
367    merge_blocks(
368        (u_even.polyvec, s_even, v_even.polyvec),
369        (u_odd.polyvec, s_odd, v_odd.polyvec),
370        epsilon,
371    )
372}
373
374/// [`merge_results`] on plain vectors
375///
376/// The SVE strategy keeps each block in plain vectors until this merge, so
377/// that a block emptied by truncation is merged like any other: keeping only
378/// the largest singular value (`max_num_svals = Some(1)`, or `cutoff =
379/// Some(1.0)`) leaves the odd block empty.
380///
381/// # Errors
382///
383/// [`Error::EmptyInput`] if both blocks are empty
384pub(crate) fn merge_blocks(
385    result_even: SvdBlock,
386    result_odd: SvdBlock,
387    epsilon: f64,
388) -> Result<crate::sve::SVEResult, Error> {
389    use crate::sve::SVEResult;
390
391    let (u_even, s_even, v_even) = result_even;
392    let (u_odd, s_odd, v_odd) = result_odd;
393    if s_even.is_empty() && s_odd.is_empty() {
394        return Err(Error::EmptyInput {
395            name: "singular values",
396        });
397    }
398
399    // Create indices with symmetry info
400    let mut indices: Vec<(usize, bool)> = Vec::new();
401    for i in 0..s_even.len() {
402        indices.push((i, true)); // true = even
403    }
404    for i in 0..s_odd.len() {
405        indices.push((i, false)); // false = odd
406    }
407
408    // Sort by singular values (descending)
409    indices.sort_by(|a, b| {
410        let s_a = if a.1 { s_even[a.0] } else { s_odd[a.0] };
411        let s_b = if b.1 { s_even[b.0] } else { s_odd[b.0] };
412        s_b.partial_cmp(&s_a).unwrap_or(std::cmp::Ordering::Equal)
413    });
414
415    // Build sorted arrays.
416    //
417    // Each polynomial still carries `l = idx`, its column in the even or odd
418    // SVD block (see `svd_to_polynomials`). Renumber it to its position in the
419    // merged result, so that `l` is the index of the singular function for
420    // every SVE result (convention-matched with SparseIR.jl v1
421    // `postprocess(::CentrosymmSVE)`, which sets `l = i - 1` after sorting).
422    // `PiecewiseLegendreFT` takes the parity (-1)^l from it; that equals
423    // `symm` because the even and odd singular values interlace.
424    let mut u_polys = Vec::new();
425    let mut v_polys = Vec::new();
426    let mut s_sorted = Vec::new();
427
428    for (l, (idx, is_even)) in indices.into_iter().enumerate() {
429        let (u_block, s_block, v_block) = if is_even {
430            (&u_even, &s_even, &v_even)
431        } else {
432            (&u_odd, &s_odd, &v_odd)
433        };
434        let l = l as i32;
435        u_polys.push(PiecewiseLegendrePoly {
436            l,
437            ..u_block[idx].clone()
438        });
439        v_polys.push(PiecewiseLegendrePoly {
440            l,
441            ..v_block[idx].clone()
442        });
443        s_sorted.push(s_block[idx]);
444    }
445
446    // Canonicalize signs: ensure u[l](xmax) >= 0. The merged blocks are not
447    // empty (checked above) and share their knots, so the vectors are built
448    // through their field.
449    let (canonical_u, canonical_v) = canonicalize_signs(u_polys, v_polys);
450    SVEResult::new(
451        PiecewiseLegendrePolyVector::from_polys_unchecked(canonical_u),
452        s_sorted,
453        PiecewiseLegendrePolyVector::from_polys_unchecked(canonical_v),
454        epsilon,
455    )
456}
457
458#[cfg(test)]
459mod tests {
460    use super::*;
461
462    #[test]
463    fn test_remove_weights() {
464        let matrix = Mat::<f64>::from_fn([2, 2], |idx| (idx[0] * 2 + idx[1] + 1) as f64);
465        let weights = vec![1.0, 4.0];
466
467        let result = remove_weights(&matrix, &weights, true);
468
469        // Both U and V: remove from rows (Gauss points)
470        // First row: [1.0, 2.0] / sqrt(1.0) = [1.0, 2.0]
471        // Second row: [3.0, 4.0] / sqrt(4.0) = [1.5, 2.0]
472        assert!((result[[0, 0]] - 1.0).abs() < 1e-10);
473        assert!((result[[0, 1]] - 2.0).abs() < 1e-10);
474        assert!((result[[1, 0]] - 1.5).abs() < 1e-10);
475        assert!((result[[1, 1]] - 2.0).abs() < 1e-10);
476    }
477}