Skip to main content

sparse_ir_basis/
polyfourier.rs

1//! Piecewise Legendre polynomial Fourier transform implementation for SparseIR
2//!
3//! This module provides Fourier transform functionality for piecewise Legendre
4//! polynomials, enabling evaluation in Matsubara frequency domain.
5
6use num_complex::Complex64;
7use std::f64::consts::PI;
8
9use crate::error::Error;
10use crate::freq::MatsubaraFreq;
11use crate::poly::{PiecewiseLegendrePoly, PiecewiseLegendrePolyVector};
12use crate::special_functions::spherical_bessel_j;
13use crate::traits::{Bosonic, Fermionic, Statistics, StatisticsType};
14
15/// Power model for asymptotic behavior
16#[derive(Debug, Clone)]
17pub struct PowerModel {
18    pub(crate) moments: Vec<f64>,
19}
20
21impl PowerModel {
22    /// Create a new power model with given moments
23    pub fn new(moments: Vec<f64>) -> Self {
24        Self { moments }
25    }
26}
27
28/// Piecewise Legendre polynomial with Fourier transform capability
29///
30/// This represents a piecewise Legendre polynomial that can be evaluated
31/// in the Matsubara frequency domain using Fourier transform.
32#[derive(Debug, Clone)]
33pub struct PiecewiseLegendreFT<S: StatisticsType> {
34    /// The underlying piecewise Legendre polynomial
35    pub(crate) poly: PiecewiseLegendrePoly,
36    /// Asymptotic cutoff frequency index
37    pub(crate) n_asymp: f64,
38    /// Power model for asymptotic behavior
39    pub(crate) model: PowerModel,
40    // `fn() -> S` keeps the type Send + Sync whatever `S` is (it holds no S)
41    _phantom: std::marker::PhantomData<fn() -> S>,
42}
43
44// Type aliases for convenience
45pub type FermionicPiecewiseLegendreFT = PiecewiseLegendreFT<Fermionic>;
46pub type BosonicPiecewiseLegendreFT = PiecewiseLegendreFT<Bosonic>;
47
48impl<S: StatisticsType> PiecewiseLegendreFT<S> {
49    /// Create a new PiecewiseLegendreFT from a polynomial and statistics
50    ///
51    /// # Arguments
52    /// * `poly` - The underlying piecewise Legendre polynomial
53    /// * `stat` - Statistics type (Fermionic or Bosonic)
54    /// * `n_asymp` - Asymptotic cutoff frequency index (default: infinity)
55    ///
56    /// # Errors
57    ///
58    /// * [`Error::InvalidParameter`] if the domain of `poly` is not [-1, 1]
59    ///   within 1e-12, or `n_asymp` is NaN or negative (infinity, the
60    ///   default, disables the asymptotic model)
61    pub fn new(poly: PiecewiseLegendrePoly, _stat: S, n_asymp: Option<f64>) -> Result<Self, Error> {
62        // Validate domain
63        if !((poly.xmin() + 1.0).abs() <= 1e-12 && (poly.xmax() - 1.0).abs() <= 1e-12) {
64            return Err(Error::InvalidParameter {
65                name: "poly",
66                value: format!("a polynomial on [{:?}, {:?}]", poly.xmin(), poly.xmax()),
67                reason: "must be defined on [-1, 1] (within 1e-12)".to_string(),
68            });
69        }
70        if let Some(n) = n_asymp.filter(|n| !(*n >= 0.0)) {
71            return Err(Error::InvalidParameter {
72                name: "n_asymp",
73                value: format!("{n:?}"),
74                reason: "must be non-negative (infinity disables the asymptotic model)".to_string(),
75            });
76        }
77
78        let n_asymp = n_asymp.unwrap_or(f64::INFINITY);
79        let model = Self::power_model(&poly);
80
81        Ok(Self {
82            poly,
83            n_asymp,
84            model,
85            _phantom: std::marker::PhantomData,
86        })
87    }
88
89    /// Get the asymptotic cutoff frequency index
90    pub fn get_n_asymp(&self) -> f64 {
91        self.n_asymp
92    }
93
94    /// Get the statistics type
95    pub fn get_statistics(&self) -> Statistics {
96        S::STATISTICS
97    }
98
99    /// Get the zeta value for this statistics type
100    pub fn zeta(&self) -> i64 {
101        match S::STATISTICS {
102            Statistics::Fermionic => 1,
103            Statistics::Bosonic => 0,
104        }
105    }
106
107    /// Get a reference to the underlying polynomial
108    pub fn get_poly(&self) -> &PiecewiseLegendrePoly {
109        &self.poly
110    }
111
112    /// Evaluate the Fourier transform at a Matsubara frequency
113    ///
114    /// # Arguments
115    /// * `omega` - Matsubara frequency
116    ///
117    /// # Returns
118    /// The complex Fourier transform value
119    pub fn evaluate(&self, omega: &MatsubaraFreq<S>) -> Complex64 {
120        let n = omega.get_n();
121        if (n as f64).abs() < self.n_asymp {
122            self.compute_unl_inner(&self.poly, n)
123        } else {
124            self.giw(n)
125        }
126    }
127
128    /// Evaluate at integer Matsubara index
129    ///
130    /// # Errors
131    ///
132    /// [`Error::InvalidMatsubaraIndex`] if `n` has the wrong parity for the
133    /// statistics (it returned 0 before)
134    pub fn evaluate_at_n(&self, n: i64) -> Result<Complex64, Error> {
135        Ok(self.evaluate(&MatsubaraFreq::<S>::new(n)?))
136    }
137
138    /// Evaluate at multiple Matsubara indices
139    ///
140    /// # Errors
141    ///
142    /// The error of [`Self::evaluate_at_n`] for the first invalid index
143    pub fn evaluate_at_ns(&self, ns: &[i64]) -> Result<Vec<Complex64>, Error> {
144        ns.iter().map(|&n| self.evaluate_at_n(n)).collect()
145    }
146
147    /// Create power model for asymptotic behavior
148    fn power_model(poly: &PiecewiseLegendrePoly) -> PowerModel {
149        // Evaluate at the ends of the domain: `new` accepts an xmin/xmax
150        // within 1e-12 of -1/1, where derivs(-1.0)/derivs(1.0) would be
151        // outside the domain.
152        PowerModel::new(Self::power_moments(
153            &poly.derivs(poly.xmax()),
154            &poly.derivs(poly.xmin()),
155        ))
156    }
157
158    /// Asymptotic power moments from the boundary derivatives at both ends
159    ///
160    /// `M_m = -( statsign · (-1)^(m+1) · u^(m)(+1) + (-1)^m · u^(m)(-1) ) / sqrt(2)`,
161    /// where `deriv_p[m]` / `deriv_m[m]` is the order-m derivative at x = +1 / -1.
162    /// No parity is assumed, so this holds for functions without definite
163    /// parity (`symm == 0`, e.g. from the full-domain SVE (`SVEOptions::full_domain`)); for a function
164    /// of parity `(-1)^l` it reduces to the one-sided form with
165    /// `u^(m)(-1) = (-1)^(l+m) u^(m)(+1)`.
166    fn power_moments(deriv_p: &[f64], deriv_m: &[f64]) -> Vec<f64> {
167        let statsign = match S::STATISTICS {
168            Statistics::Fermionic => -1.0,
169            Statistics::Bosonic => 1.0,
170        };
171        deriv_p
172            .iter()
173            .zip(deriv_m)
174            .enumerate()
175            .map(|(m, (&dp, &dm))| {
176                let sign_p = (-1.0_f64).powi((m + 1) as i32);
177                let sign_m = (-1.0_f64).powi(m as i32);
178                -(statsign * sign_p * dp + sign_m * dm) / 2.0_f64.sqrt()
179            })
180            .collect()
181    }
182
183    /// Compute the inner Fourier transform (for small frequencies)
184    fn compute_unl_inner(&self, poly: &PiecewiseLegendrePoly, wn: i64) -> Complex64 {
185        Self::contract_inner(poly, &InnerFactors::new::<S>(poly, poly.polyorder(), wn))
186    }
187
188    /// Inner transform from precomputed segment-wise factors
189    ///
190    /// Sums `data[order, j] · T_nl[order, j] · phase[j]` over the orders of each
191    /// segment j first (real × complex over the contiguous column j of the
192    /// column-major `data`), then divides each segment sum by `norms[j]` once.
193    fn contract_inner(poly: &PiecewiseLegendrePoly, f: &InnerFactors) -> Complex64 {
194        let polyorder = poly.polyorder();
195        debug_assert_eq!(f.nseg, poly.knots().len() - 1);
196        debug_assert!(polyorder <= f.polyorder);
197        let mut res = Complex64::new(0.0, 0.0);
198        for j in 0..f.nseg {
199            let col = &poly.data().col(j)[..polyorder];
200            let w_re = &f.w_re[j * f.polyorder..j * f.polyorder + polyorder];
201            let w_im = &f.w_im[j * f.polyorder..j * f.polyorder + polyorder];
202            let (mut acc_re, mut acc_im) = (0.0, 0.0);
203            for o in 0..polyorder {
204                acc_re += col[o] * w_re[o];
205                acc_im += col[o] * w_im[o];
206            }
207            res += Complex64::new(acc_re, acc_im) / poly.norms()[j];
208        }
209        res / 2.0_f64.sqrt()
210    }
211
212    /// Compute asymptotic behavior (for large frequencies)
213    fn giw(&self, wn: i64) -> Complex64 {
214        let iw = Complex64::new(0.0, PI / 2.0 * wn as f64);
215        if wn == 0 {
216            return Complex64::new(0.0, 0.0);
217        }
218
219        let inv_iw = 1.0 / iw;
220
221        inv_iw * Self::evalpoly(inv_iw, &self.model.moments)
222    }
223
224    /// Evaluate polynomial at complex point (Horner's method)
225    fn evalpoly(x: Complex64, coeffs: &[f64]) -> Complex64 {
226        let mut result = Complex64::new(0.0, 0.0);
227        for i in (0..coeffs.len()).rev() {
228            result = result * x + Complex64::new(coeffs[i], 0.0);
229        }
230        result
231    }
232
233    /// Compute midpoint relative to nearest integer
234    ///
235    /// Returns (xmid_diff, extra_shift) where:
236    /// - xmid_diff: midpoint values for numerical stability
237    /// - extra_shift: nearest integer shift (-1, 0, or 1)
238    fn shift_xmid(knots: &[f64], delta_x: &[f64]) -> (Vec<f64>, Vec<i32>) {
239        let n_segments = delta_x.len();
240        let delta_x_half: Vec<f64> = delta_x.iter().map(|&dx| dx / 2.0).collect();
241
242        // xmid_m1: cumsum(Δx) - Δx_half
243        let mut xmid_m1 = Vec::with_capacity(n_segments);
244        let mut cumsum = 0.0;
245        for i in 0..n_segments {
246            cumsum += delta_x[i];
247            xmid_m1.push(cumsum - delta_x_half[i]);
248        }
249
250        // xmid_p1: -reverse(cumsum(reverse(Δx))) + Δx_half
251        let mut xmid_p1 = Vec::with_capacity(n_segments);
252        let mut cumsum_rev = 0.0;
253        for i in (0..n_segments).rev() {
254            cumsum_rev += delta_x[i];
255            xmid_p1.insert(0, -cumsum_rev + delta_x_half[i]);
256        }
257
258        // xmid_0: knots[1:] - Δx_half
259        let xmid_0: Vec<f64> = (0..n_segments)
260            .map(|i| knots[i + 1] - delta_x_half[i])
261            .collect();
262
263        // Determine shift and diff
264        let mut xmid_diff = Vec::with_capacity(n_segments);
265        let mut extra_shift = Vec::with_capacity(n_segments);
266
267        for i in 0..n_segments {
268            let shift = xmid_0[i].round() as i32;
269            extra_shift.push(shift);
270
271            // Choose appropriate xmid based on shift
272            let diff = match shift {
273                -1 => xmid_m1[i],
274                0 => xmid_0[i],
275                1 => xmid_p1[i],
276                _ => xmid_0[i], // Fallback
277            };
278            xmid_diff.push(diff);
279        }
280
281        (xmid_diff, extra_shift)
282    }
283
284    /// Compute stable phase factors
285    ///
286    /// Computes: im^mod(wn * (extra_shift + 1), 4) * cispi(wn * xmid_diff / 2)
287    /// where cispi(x) = exp(i*π*x)
288    fn phase_stable(poly: &PiecewiseLegendrePoly, wn: i64) -> Vec<Complex64> {
289        let (xmid_diff, extra_shift) = Self::shift_xmid(poly.knots(), poly.delta_x());
290        let mut phase_wi = Vec::with_capacity(xmid_diff.len());
291
292        let im_unit = Complex64::new(0.0, 1.0);
293
294        for j in 0..xmid_diff.len() {
295            // Compute im^mod(wn * (extra_shift[j] + 1), 4)
296            let power = ((wn * (extra_shift[j] as i64 + 1)) % 4 + 4) % 4; // Ensure positive mod
297            let im_power = im_unit.powi(power as i32);
298
299            // Compute cispi(wn * xmid_diff[j] / 2) = exp(i*π*wn*xmid_diff/2)
300            let arg = PI * wn as f64 * xmid_diff[j] / 2.0;
301            let cispi = Complex64::new(arg.cos(), arg.sin());
302
303            phase_wi.push(im_power * cispi);
304        }
305
306        phase_wi
307    }
308
309    /// Get T_nl coefficient (special function)
310    ///
311    /// This implements the T_nl function which is related to spherical Bessel functions:
312    /// T_nl(w) = 2 * i^l * j_l(|w|) * (w < 0 ? conj : identity)
313    /// where j_l is the spherical Bessel function of the first kind.
314    pub fn get_tnl(l: i32, w: f64) -> Complex64 {
315        let abs_w = w.abs();
316
317        // Use the high-precision spherical Bessel function from special_functions
318        let sph_bessel = spherical_bessel_j(l, abs_w);
319
320        // Compute 2 * i^l
321        let im_unit = Complex64::new(0.0, 1.0);
322        let im_power = im_unit.powi(l);
323        let result = 2.0 * im_power * sph_bessel;
324
325        // Apply conjugation for negative w
326        if w < 0.0 { result.conj() } else { result }
327    }
328}
329
330/// Segment-wise factors of the inner Fourier transform at one frequency:
331/// `w[order, j] = T_nl[order, j] · phase[j]`, stored as separate real and
332/// imaginary parts, segment-major (index `j * polyorder + order`, matching the
333/// column-major polynomial data). They depend only on the knots, so
334/// polynomials sharing knots can share them.
335struct InnerFactors {
336    nseg: usize,
337    polyorder: usize,
338    w_re: Vec<f64>,
339    w_im: Vec<f64>,
340}
341
342impl InnerFactors {
343    fn new<S: StatisticsType>(poly: &PiecewiseLegendrePoly, polyorder: usize, wn: i64) -> Self {
344        let wred = PI / 4.0 * wn as f64;
345        let phase = PiecewiseLegendreFT::<S>::phase_stable(poly, wn);
346        let nseg = phase.len();
347        let mut w_re = Vec::with_capacity(polyorder * nseg);
348        let mut w_im = Vec::with_capacity(polyorder * nseg);
349        for (&dx, &ph) in poly.delta_x().iter().zip(&phase) {
350            for order in 0..polyorder {
351                let w = PiecewiseLegendreFT::<S>::get_tnl(order as i32, wred * dx) * ph;
352                w_re.push(w.re);
353                w_im.push(w.im);
354            }
355        }
356        Self {
357            nseg,
358            polyorder,
359            w_re,
360            w_im,
361        }
362    }
363}
364
365/// Vector of PiecewiseLegendreFT polynomials
366#[derive(Debug, Clone)]
367pub struct PiecewiseLegendreFTVector<S: StatisticsType> {
368    pub(crate) polyvec: Vec<PiecewiseLegendreFT<S>>,
369    // `fn() -> S` keeps the type Send + Sync whatever `S` is (it holds no S)
370    _phantom: std::marker::PhantomData<fn() -> S>,
371}
372
373// Type aliases for convenience
374pub type FermionicPiecewiseLegendreFTVector = PiecewiseLegendreFTVector<Fermionic>;
375pub type BosonicPiecewiseLegendreFTVector = PiecewiseLegendreFTVector<Bosonic>;
376
377impl<S: StatisticsType> PiecewiseLegendreFTVector<S> {
378    /// Create an empty vector
379    pub fn new() -> Self {
380        Self {
381            polyvec: Vec::new(),
382            _phantom: std::marker::PhantomData,
383        }
384    }
385
386    /// Create from a vector of PiecewiseLegendreFT
387    pub fn from_vector(polyvec: Vec<PiecewiseLegendreFT<S>>) -> Self {
388        Self {
389            polyvec,
390            _phantom: std::marker::PhantomData,
391        }
392    }
393
394    /// Get the number of polynomials in the vector
395    pub fn len(&self) -> usize {
396        self.polyvec.len()
397    }
398
399    /// Check if the vector is empty
400    pub fn is_empty(&self) -> bool {
401        self.polyvec.is_empty()
402    }
403
404    /// Create from PiecewiseLegendrePolyVector and statistics
405    ///
406    /// # Errors
407    ///
408    /// The errors of [`PiecewiseLegendreFT::new`] for the first polynomial
409    /// that it rejects
410    pub fn from_poly_vector(
411        polys: &PiecewiseLegendrePolyVector,
412        _stat: S,
413        n_asymp: Option<f64>,
414    ) -> Result<Self, Error> {
415        let mut polyvec = Vec::with_capacity(polys.len());
416
417        for poly in polys.polys() {
418            let ft_poly = PiecewiseLegendreFT::new(poly.clone(), _stat, n_asymp)?;
419            polyvec.push(ft_poly);
420        }
421
422        Ok(Self {
423            polyvec,
424            _phantom: std::marker::PhantomData,
425        })
426    }
427
428    /// Get the size of the vector
429    pub fn size(&self) -> usize {
430        self.polyvec.len()
431    }
432
433    /// The transformed polynomials, in order
434    pub fn get_polys(&self) -> &[PiecewiseLegendreFT<S>] {
435        &self.polyvec
436    }
437
438    /// Get element by index (immutable)
439    pub fn get(&self, index: usize) -> Option<&PiecewiseLegendreFT<S>> {
440        self.polyvec.get(index)
441    }
442
443    /// Get element by index (mutable)
444    pub fn get_mut(&mut self, index: usize) -> Option<&mut PiecewiseLegendreFT<S>> {
445        self.polyvec.get_mut(index)
446    }
447
448    /// Set element at index
449    ///
450    /// # Errors
451    /// [`Error::InvalidParameter`] if `index` is not less than the length;
452    /// the vector is then unchanged
453    pub fn set(&mut self, index: usize, poly: PiecewiseLegendreFT<S>) -> Result<(), Error> {
454        let len = self.polyvec.len();
455        if index >= len {
456            return Err(Error::InvalidParameter {
457                name: "index",
458                value: index.to_string(),
459                reason: format!("must be less than the length {len}"),
460            });
461        }
462        self.polyvec[index] = poly;
463        Ok(())
464    }
465
466    /// Create a similar empty vector
467    pub fn similar(&self) -> Self {
468        Self::new()
469    }
470
471    /// Get n_asymp from the first element (if any)
472    pub fn n_asymp(&self) -> f64 {
473        self.polyvec.first().map_or(f64::INFINITY, |p| p.n_asymp)
474    }
475
476    /// Evaluate all polynomials at a Matsubara frequency
477    ///
478    /// When all polynomials share their knots (as the functions of one basis
479    /// do), the segment-wise factors of the inner transform are computed once.
480    pub fn evaluate_at(&self, omega: &MatsubaraFreq<S>) -> Vec<Complex64> {
481        let Some(first) = self.polyvec.first() else {
482            return Vec::new();
483        };
484        let shared_knots = self.polyvec.iter().all(|p| {
485            p.poly.knots() == first.poly.knots() && p.poly.delta_x() == first.poly.delta_x()
486        });
487        if !shared_knots {
488            return self.polyvec.iter().map(|p| p.evaluate(omega)).collect();
489        }
490        let n = omega.get_n();
491        let polyorder = self
492            .polyvec
493            .iter()
494            .map(|p| p.poly.polyorder())
495            .max()
496            .unwrap_or(0);
497        let mut factors = None;
498        self.polyvec
499            .iter()
500            .map(|p| {
501                if (n as f64).abs() < p.n_asymp {
502                    let f = factors
503                        .get_or_insert_with(|| InnerFactors::new::<S>(&first.poly, polyorder, n));
504                    PiecewiseLegendreFT::<S>::contract_inner(&p.poly, f)
505                } else {
506                    p.giw(n)
507                }
508            })
509            .collect()
510    }
511
512    /// Evaluate all polynomials at multiple Matsubara frequencies
513    pub fn evaluate_at_many(&self, omegas: &[MatsubaraFreq<S>]) -> Vec<Vec<Complex64>> {
514        omegas.iter().map(|omega| self.evaluate_at(omega)).collect()
515    }
516}
517
518// Indexing operators
519impl<S: StatisticsType> std::ops::Index<usize> for PiecewiseLegendreFTVector<S> {
520    type Output = PiecewiseLegendreFT<S>;
521
522    fn index(&self, index: usize) -> &Self::Output {
523        &self.polyvec[index]
524    }
525}
526
527impl<S: StatisticsType> std::ops::IndexMut<usize> for PiecewiseLegendreFTVector<S> {
528    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
529        &mut self.polyvec[index]
530    }
531}
532
533// Default implementations
534impl<S: StatisticsType> Default for PiecewiseLegendreFTVector<S> {
535    fn default() -> Self {
536        Self::new()
537    }
538}
539
540// ===== Matsubara sampling point selection =====
541
542/// Grid of reduced Matsubara indices k (n = 2k + ζ) for sampling candidates
543/// Matches C++ DEFAULT_GRID: [0:2^6-1] followed by exponential spacing up to 2^25
544/// Generated from Julia: [range(0; length=2^6); trunc.(Int, exp2.(range(6, 25; length=32 * (25 - 6) + 1)))]
545const DEFAULT_GRID: &[i64] = &[
546    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
547    26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
548    50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 68, 69, 71, 72, 74, 76, 77,
549    79, 81, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 103, 105, 107, 109, 112, 114, 117, 119, 122,
550    125, 128, 130, 133, 136, 139, 142, 145, 148, 152, 155, 158, 162, 165, 169, 173, 177, 181, 184,
551    189, 193, 197, 201, 206, 210, 215, 219, 224, 229, 234, 239, 245, 250, 256, 261, 267, 273, 279,
552    285, 291, 297, 304, 311, 317, 324, 331, 339, 346, 354, 362, 369, 378, 386, 394, 403, 412, 421,
553    430, 439, 449, 459, 469, 479, 490, 501, 512, 523, 534, 546, 558, 570, 583, 595, 608, 622, 635,
554    649, 663, 678, 693, 708, 724, 739, 756, 772, 789, 806, 824, 842, 861, 879, 899, 918, 939, 959,
555    980, 1002, 1024, 1046, 1069, 1092, 1116, 1141, 1166, 1191, 1217, 1244, 1271, 1299, 1327, 1357,
556    1386, 1417, 1448, 1479, 1512, 1545, 1579, 1613, 1649, 1685, 1722, 1759, 1798, 1837, 1878, 1919,
557    1961, 2004, 2048, 2092, 2138, 2185, 2233, 2282, 2332, 2383, 2435, 2488, 2543, 2599, 2655, 2714,
558    2773, 2834, 2896, 2959, 3024, 3090, 3158, 3227, 3298, 3370, 3444, 3519, 3596, 3675, 3756, 3838,
559    3922, 4008, 4096, 4185, 4277, 4371, 4466, 4564, 4664, 4766, 4870, 4977, 5086, 5198, 5311, 5428,
560    5547, 5668, 5792, 5919, 6049, 6181, 6316, 6455, 6596, 6741, 6888, 7039, 7193, 7351, 7512, 7676,
561    7844, 8016, 8192, 8371, 8554, 8742, 8933, 9129, 9328, 9533, 9741, 9955, 10173, 10396, 10623,
562    10856, 11094, 11336, 11585, 11838, 12098, 12363, 12633, 12910, 13193, 13482, 13777, 14078,
563    14387, 14702, 15024, 15353, 15689, 16032, 16384, 16742, 17109, 17484, 17866, 18258, 18657,
564    19066, 19483, 19910, 20346, 20792, 21247, 21712, 22188, 22673, 23170, 23677, 24196, 24726,
565    25267, 25820, 26386, 26964, 27554, 28157, 28774, 29404, 30048, 30706, 31378, 32065, 32768,
566    33485, 34218, 34968, 35733, 36516, 37315, 38132, 38967, 39821, 40693, 41584, 42494, 43425,
567    44376, 45347, 46340, 47355, 48392, 49452, 50535, 51641, 52772, 53928, 55108, 56315, 57548,
568    58809, 60096, 61412, 62757, 64131, 65536, 66971, 68437, 69936, 71467, 73032, 74631, 76265,
569    77935, 79642, 81386, 83168, 84989, 86850, 88752, 90695, 92681, 94711, 96785, 98904, 101070,
570    103283, 105545, 107856, 110217, 112631, 115097, 117618, 120193, 122825, 125514, 128263, 131072,
571    133942, 136875, 139872, 142935, 146064, 149263, 152531, 155871, 159284, 162772, 166337, 169979,
572    173701, 177504, 181391, 185363, 189422, 193570, 197809, 202140, 206566, 211090, 215712, 220435,
573    225262, 230195, 235236, 240387, 245650, 251029, 256526, 262144, 267884, 273750, 279744, 285870,
574    292129, 298526, 305063, 311743, 318569, 325545, 332674, 339958, 347402, 355009, 362783, 370727,
575    378845, 387141, 395618, 404281, 413133, 422180, 431424, 440871, 450525, 460390, 470472, 480774,
576    491301, 502059, 513053, 524288, 535768, 547500, 559488, 571740, 584259, 597053, 610126, 623487,
577    637139, 651091, 665348, 679917, 694805, 710019, 725567, 741455, 757690, 774282, 791236, 808562,
578    826267, 844360, 862849, 881743, 901051, 920781, 940944, 961548, 982603, 1004119, 1026107,
579    1048576, 1071536, 1095000, 1118977, 1143480, 1168519, 1194106, 1220253, 1246974, 1274279,
580    1302182, 1330696, 1359834, 1389611, 1420039, 1451134, 1482910, 1515381, 1548564, 1582473,
581    1617125, 1652535, 1688721, 1725699, 1763487, 1802102, 1841563, 1881888, 1923096, 1965207,
582    2008239, 2052214, 2097152, 2143073, 2190000, 2237955, 2286960, 2337038, 2388212, 2440507,
583    2493948, 2548558, 2604364, 2661392, 2719669, 2779222, 2840079, 2902269, 2965820, 3030763,
584    3097128, 3164947, 3234250, 3305071, 3377443, 3451399, 3526975, 3604205, 3683127, 3763777,
585    3846193, 3930414, 4016479, 4104428, 4194304, 4286147, 4380001, 4475911, 4573920, 4674076,
586    4776425, 4881015, 4987896, 5097116, 5208729, 5322785, 5439339, 5558445, 5680159, 5804538,
587    5931641, 6061527, 6194257, 6329894, 6468501, 6610142, 6754886, 6902798, 7053950, 7208411,
588    7366255, 7527555, 7692387, 7860828, 8032958, 8208857, 8388608, 8572294, 8760003, 8951822,
589    9147841, 9348153, 9552851, 9762031, 9975792, 10194233, 10417458, 10645571, 10878678, 11116890,
590    11360318, 11609077, 11863283, 12123055, 12388515, 12659788, 12937002, 13220285, 13509772,
591    13805597, 14107900, 14416823, 14732510, 15055110, 15384774, 15721657, 16065917, 16417714,
592    16777216, 17144589, 17520006, 17903645, 18295683, 18696307, 19105702, 19524063, 19951584,
593    20388467, 20834916, 21291142, 21757357, 22233781, 22720637, 23218155, 23726566, 24246110,
594    24777031, 25319577, 25874004, 26440571, 27019544, 27611195, 28215801, 28833647, 29465021,
595    30110221, 30769549, 31443315, 32131834, 32835429, 33554432,
596];
597
598/// Find sign changes of a Matsubara basis function
599///
600/// Returns Matsubara frequencies where the function changes sign.
601///
602/// # Errors
603///
604/// [`Error::NotSupported`] if `u_hat` has no definite parity (symm = 0);
605/// such functions get their points from [`pair_sampling_points`] instead
606pub(crate) fn sign_changes<S: StatisticsType + 'static>(
607    u_hat: &PiecewiseLegendreFT<S>,
608    positive_only: bool,
609) -> Result<Vec<MatsubaraFreq<S>>, Error> {
610    let f = func_for_part(u_hat)?;
611    let x0 = find_all(&f, DEFAULT_GRID);
612
613    // Convert to Matsubara indices: n = 2*x + zeta
614    let mut indices: Vec<i64> = x0.iter().map(|&x| 2 * x + u_hat.zeta()).collect();
615
616    if !positive_only {
617        symmetrize_matsubara_inplace(&mut indices);
618    }
619
620    Ok(indices
621        .iter()
622        .filter_map(|&n| MatsubaraFreq::<S>::new(n).ok())
623        .collect())
624}
625
626/// Find extrema of a Matsubara basis function
627///
628/// Returns Matsubara frequencies where the function has local extrema.
629///
630/// # Errors
631///
632/// [`Error::NotSupported`] if `u_hat` has no definite parity (symm = 0);
633/// such functions get their points from [`pair_sampling_points`] instead
634pub(crate) fn find_extrema<S: StatisticsType + 'static>(
635    u_hat: &PiecewiseLegendreFT<S>,
636    positive_only: bool,
637) -> Result<Vec<MatsubaraFreq<S>>, Error> {
638    let f = func_for_part(u_hat)?;
639    let x0 = discrete_extrema(&f, DEFAULT_GRID);
640
641    // Convert to Matsubara indices: n = 2*x + zeta
642    let mut indices: Vec<i64> = x0.iter().map(|&x| 2 * x + u_hat.zeta()).collect();
643
644    if !positive_only {
645        symmetrize_matsubara_inplace(&mut indices);
646    }
647
648    Ok(indices
649        .iter()
650        .filter_map(|&n| MatsubaraFreq::<S>::new(n).ok())
651        .collect())
652}
653
654/// The part of a Matsubara basis function whose sign changes choose the
655/// default sampling points
656#[derive(Clone, Copy)]
657enum Part {
658    Real,
659    Imaginary,
660}
661
662/// The part of `û(iν)` that carries its sign changes, from the parity `symm`
663/// of `u` and the statistics: for an even `u` (symm = 1) the fermionic `û`
664/// is imaginary and the bosonic `û` real, for an odd `u` (symm = -1) the
665/// other way round
666///
667/// # Errors
668///
669/// [`Error::NotSupported`] if `symm` is not ±1: the singular functions of an
670/// SVE that is not centrosymmetric have no parity.
671fn part_with_the_sign_changes<S: StatisticsType>(symm: i32) -> Result<Part, Error> {
672    match (symm, S::STATISTICS) {
673        (1, Statistics::Bosonic) | (-1, Statistics::Fermionic) => Ok(Part::Real),
674        (1, Statistics::Fermionic) | (-1, Statistics::Bosonic) => Ok(Part::Imaginary),
675        _ => Err(Error::NotSupported {
676            what: format!(
677                "default Matsubara sampling points, which need basis functions of definite \
678                 parity (symm = ±1, from a centrosymmetric SVE); got symm = {symm}"
679            ),
680        }),
681    }
682}
683
684impl Part {
685    fn of(self, value: Complex64) -> f64 {
686        match self {
687            Part::Real => value.re,
688            Part::Imaginary => value.im,
689        }
690    }
691}
692
693/// Create a function that extracts the part of `poly_ft` that carries its
694/// sign changes (see [`part_with_the_sign_changes`])
695fn func_for_part<S: StatisticsType + 'static>(
696    poly_ft: &PiecewiseLegendreFT<S>,
697) -> Result<Box<dyn Fn(i64) -> f64>, Error> {
698    let part = part_with_the_sign_changes::<S>(poly_ft.poly.symm())?;
699    let zeta = poly_ft.zeta();
700    let poly_ft_clone = poly_ft.clone();
701
702    Ok(Box::new(move |n: i64| {
703        let omega = MatsubaraFreq::<S>::new(2 * n + zeta).unwrap();
704        part.of(poly_ft_clone.evaluate(&omega))
705    }))
706}
707
708/// Integer bisection: find the zero crossing of f in [a, b] where f(a) and f(b)
709/// have different signs. Returns the largest integer x such that f(x) has the
710/// same sign as f(a). Matches Julia's `bisect` implementation.
711fn bisect(f: &dyn Fn(i64) -> f64, a: i64, b: i64, fa: f64) -> i64 {
712    let mut lo = a;
713    let mut hi = b;
714    let mut flo = fa;
715
716    while (hi - lo).abs() > 1 {
717        let mid = lo + (hi - lo) / 2;
718        let fmid = f(mid);
719        if flo.signum() != fmid.signum() {
720            hi = mid;
721        } else {
722            lo = mid;
723            flo = fmid;
724        }
725    }
726    lo
727}
728
729/// Integer bisection for extrema: find the discrete extremum of f in [a, b].
730/// Returns the integer x in [a, b] that maximizes |f(x)|.
731/// Matches Julia's `bisect_discr_extremum` implementation.
732fn bisect_discr_extremum(f: &dyn Fn(i64) -> f64, a: i64, b: i64) -> i64 {
733    let mut lo = a;
734    let mut hi = b;
735
736    while hi - lo > 2 {
737        let mid1 = lo + (hi - lo) / 3;
738        let mid2 = hi - (hi - lo) / 3;
739        if f(mid1).abs() < f(mid2).abs() {
740            lo = mid1;
741        } else {
742            hi = mid2;
743        }
744    }
745
746    // Check all remaining candidates
747    let mut best = lo;
748    let mut best_val = f(lo).abs();
749    for x in (lo + 1)..=hi {
750        let val = f(x).abs();
751        if val > best_val {
752            best = x;
753            best_val = val;
754        }
755    }
756    best
757}
758
759/// Find all sign changes of a function on a grid, using bisection to locate
760/// the precise integer position within each grid interval.
761/// Matches Julia's `find_all` with `bisect`.
762fn find_all(f: &dyn Fn(i64) -> f64, xgrid: &[i64]) -> Vec<i64> {
763    if xgrid.is_empty() {
764        return Vec::new();
765    }
766
767    let mut results = Vec::new();
768    let mut prev_val = f(xgrid[0]);
769
770    for i in 1..xgrid.len() {
771        let val = f(xgrid[i]);
772        // Detect sign change (both values must be nonzero)
773        if prev_val.signum() != val.signum() && prev_val != 0.0 && val != 0.0 {
774            // Bisect to find precise integer location of the zero
775            let root = bisect(f, xgrid[i - 1], xgrid[i], prev_val);
776            results.push(root);
777        }
778        prev_val = val;
779    }
780
781    results
782}
783
784/// Find discrete extrema of a function on a grid, using bisection to locate
785/// the precise integer position within each grid interval.
786/// Also checks boundary extrema. Matches Julia v1 / Python 1.x `discrete_extrema`.
787fn discrete_extrema(f: &dyn Fn(i64) -> f64, xgrid: &[i64]) -> Vec<i64> {
788    if xgrid.len() < 3 {
789        return Vec::new();
790    }
791
792    let fx: Vec<f64> = xgrid.iter().map(|&x| f(x)).collect();
793    let absfx: Vec<f64> = fx.iter().map(|v| v.abs()).collect();
794
795    // Forward differences: gx[i] = fx[i+1] - fx[i]
796    // signdfdx[i] = signbit(gx[i])
797    // A derivative sign change at index i means the extremum is strictly
798    // between xgrid[i] and xgrid[i+2].
799    let signdfdx: Vec<bool> = fx
800        .windows(2)
801        .map(|w| (w[1] - w[0]).is_sign_negative())
802        .collect();
803
804    let mut results = Vec::new();
805
806    for i in 0..signdfdx.len() - 1 {
807        if signdfdx[i] != signdfdx[i + 1] {
808            // Extremum between xgrid[i] and xgrid[i+2]
809            let refined = bisect_discr_extremum(f, xgrid[i], xgrid[i + 2]);
810            results.push(refined);
811        }
812    }
813
814    // Boundary: first point is extremum if |f| decreases or sign changes inwards
815    let sfx: Vec<bool> = fx.iter().map(|v| v.is_sign_negative()).collect();
816    if absfx[0] > absfx[1] || sfx[0] != sfx[1] {
817        results.insert(0, xgrid[0]);
818    }
819
820    // Boundary: last point is extremum if |f| decreases or sign changes inwards
821    let n = fx.len();
822    if absfx[n - 1] > absfx[n - 2] || sfx[n - 1] != sfx[n - 2] {
823        results.push(xgrid[n - 1]);
824    }
825
826    results
827}
828
829/// Symmetrize Matsubara indices by adding negative frequencies
830fn symmetrize_matsubara_inplace(xs: &mut Vec<i64>) {
831    if xs.is_empty() {
832        return;
833    }
834
835    // Remove zero if present
836    xs.retain(|&x| x != 0);
837
838    // Add negative frequencies
839    let positives: Vec<i64> = xs.iter().filter(|&&x| x > 0).copied().collect();
840    let mut negatives: Vec<i64> = positives.iter().map(|&x| -x).collect();
841
842    xs.append(&mut negatives);
843    xs.sort();
844    xs.dedup();
845}
846
847/// Matsubara sampling frequencies for fitting the first `n_points` functions
848/// of `uhat`, selected as symmetric pairs; the default points of functions
849/// without a definite parity
850///
851/// The sign changes of `û_L` that choose the default points of functions with
852/// a parity (as in SparseIR.jl) need `û_L` to be purely real or purely
853/// imaginary. This selection needs no parity.
854///
855/// The selected set is symmetric, `{±n_k}`. Since `û_l(-n) = conj(û_l(n))`
856/// for a real `u_l(τ)`, fitting at `±n_k` is equivalent to fitting the real
857/// and imaginary parts at `n_k`, so the selection is made on the real matrix
858/// whose rows are `Re û_l(n_k)` and `Im û_l(n_k)`: two rows per frequency
859/// `n_k > 0`, and for bosons one row, `Re û_l(0)`, for `n = 0`, which is
860/// always selected. The rows are chosen by an interpolative decomposition
861/// (the pivoted QR of the rows, taking pairs; see the `pair_select` module),
862/// as Kaye, Chen and Parcollet do for the DLR (Phys. Rev. B 105, 235115
863/// (2022)), until there are at least `n_points` rows: an even number for
864/// fermions, an odd one for bosons, as for the sign changes. When `uhat` has
865/// the next function, the selection is made on `n_points` rounded up to that
866/// parity, so that it is square.
867///
868/// Candidates are the frequencies `n = 2k + ζ >= 0` for `k` on the grid of
869/// the sign-change search (as in SparseIR.jl): every `k` below 64, then
870/// about 32 points per octave (spacing about 2%). The selected frequencies
871/// are points of this grid, unlike the sign changes, which are bisected to
872/// the exact integer; at high frequency, where the grid is sparse, the
873/// functions vary slowly in `n`.
874///
875/// With `mitigate`, about 10% more frequencies are added (oversampling), in
876/// ± pairs, each pair the one that most decreases the noise variance
877/// `trace((FᵀF)⁻¹)` of the fit (A-optimal).
878///
879/// With `positive_only`, the frequencies `n_k >= 0` are returned (as used
880/// for fitting real-valued imaginary-time functions); otherwise `±n_k`.
881/// Returned sorted; empty if `n_points` is 0.
882///
883/// # Errors
884///
885/// * [`Error::EmptyInput`] if `uhat` is empty
886/// * [`Error::InvalidParameter`] if `n_points` exceeds the number of
887///   functions of `uhat`
888/// * [`Error::DecompositionFailed`] if the rows of the functions on the grid
889///   have rank below `n_points`, so that fewer points than requested would
890///   be returned
891pub(crate) fn pair_sampling_points<S: StatisticsType + 'static>(
892    uhat: &PiecewiseLegendreFTVector<S>,
893    n_points: usize,
894    positive_only: bool,
895    mitigate: bool,
896) -> Result<Vec<MatsubaraFreq<S>>, Error> {
897    use crate::pair_select::select_pairs;
898    use nalgebra::DMatrix;
899
900    if uhat.is_empty() {
901        return Err(Error::EmptyInput { name: "uhat" });
902    }
903    if n_points > uhat.len() {
904        return Err(Error::InvalidParameter {
905            name: "n_points",
906            value: n_points.to_string(),
907            reason: format!(
908                "the pair selection fits at most the {} functions given",
909                uhat.len()
910            ),
911        });
912    }
913    if n_points == 0 {
914        return Ok(Vec::new());
915    }
916    let bosonic = S::STATISTICS == Statistics::Bosonic;
917    // Rows of the selection: n_points rounded up to the parity of the
918    // statistics; as many functions are fitted when uhat has them.
919    let n_rows = if bosonic {
920        n_points + 1 - n_points % 2
921    } else {
922        n_points + n_points % 2
923    };
924    let n_fit = if n_rows <= uhat.len() {
925        n_rows
926    } else {
927        n_points
928    };
929    let zeta = i64::from(!bosonic);
930    // The candidates 2k + ζ have the parity of the statistics.
931    let freqs: Vec<MatsubaraFreq<S>> = DEFAULT_GRID
932        .iter()
933        .map(|&k| MatsubaraFreq::new(2 * k + zeta))
934        .collect::<Result<_, _>>()?;
935    // Only the first n_fit functions enter the selection: evaluate just
936    // those. û_l(-n) = conj(û_l(n)) as u_l(τ) is real: only n >= 0 is
937    // evaluated.
938    let used = PiecewiseLegendreFTVector::from_vector(uhat.polyvec[..n_fit].to_vec());
939    let values: Vec<Vec<Complex64>> = used.evaluate_at_many(&freqs);
940    // n = 0 (bosons only) is the first candidate; it gives one fixed row,
941    // Re û(0)
942    let first = usize::from(bosonic);
943    let pairs = DMatrix::<f64>::from_fn(2 * (freqs.len() - first), n_fit, |i, l| {
944        let v = values[first + i / 2][l];
945        if i % 2 == 0 { v.re } else { v.im }
946    });
947    let fixed = DMatrix::<f64>::from_fn(first, n_fit, |_, l| values[0][l].re);
948    // Oversampling adds 10% more frequencies, in ± pairs
949    let n_extra = if mitigate {
950        n_points.div_ceil(10).div_ceil(2)
951    } else {
952        0
953    };
954    let selected_pairs = select_pairs(&pairs, &fixed, n_extra);
955    if first + 2 * selected_pairs.len() < n_points {
956        return Err(Error::DecompositionFailed {
957            reason: format!(
958                "the functions have rank {} below {n_points} on the candidate frequencies",
959                first + 2 * selected_pairs.len()
960            ),
961        });
962    }
963    let mut selected: Vec<MatsubaraFreq<S>> = selected_pairs
964        .into_iter()
965        .map(|p| freqs[first + p])
966        .collect();
967    if bosonic {
968        selected.push(freqs[0]);
969    }
970    if !positive_only {
971        let negative: Vec<MatsubaraFreq<S>> = selected
972            .iter()
973            .filter(|f| f.get_n() != 0)
974            .map(|&f| -f)
975            .collect();
976        selected.extend(negative);
977    }
978    selected.sort();
979    Ok(selected)
980}
981
982#[cfg(test)]
983#[path = "polyfourier_tests.rs"]
984mod polyfourier_tests;