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}