1use 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#[derive(Debug, Clone)]
17pub struct PowerModel {
18 pub(crate) moments: Vec<f64>,
19}
20
21impl PowerModel {
22 pub fn new(moments: Vec<f64>) -> Self {
24 Self { moments }
25 }
26}
27
28#[derive(Debug, Clone)]
33pub struct PiecewiseLegendreFT<S: StatisticsType> {
34 pub(crate) poly: PiecewiseLegendrePoly,
36 pub(crate) n_asymp: f64,
38 pub(crate) model: PowerModel,
40 _phantom: std::marker::PhantomData<fn() -> S>,
42}
43
44pub type FermionicPiecewiseLegendreFT = PiecewiseLegendreFT<Fermionic>;
46pub type BosonicPiecewiseLegendreFT = PiecewiseLegendreFT<Bosonic>;
47
48impl<S: StatisticsType> PiecewiseLegendreFT<S> {
49 pub fn new(poly: PiecewiseLegendrePoly, _stat: S, n_asymp: Option<f64>) -> Result<Self, Error> {
62 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 pub fn get_n_asymp(&self) -> f64 {
91 self.n_asymp
92 }
93
94 pub fn get_statistics(&self) -> Statistics {
96 S::STATISTICS
97 }
98
99 pub fn zeta(&self) -> i64 {
101 match S::STATISTICS {
102 Statistics::Fermionic => 1,
103 Statistics::Bosonic => 0,
104 }
105 }
106
107 pub fn get_poly(&self) -> &PiecewiseLegendrePoly {
109 &self.poly
110 }
111
112 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 pub fn evaluate_at_n(&self, n: i64) -> Result<Complex64, Error> {
135 Ok(self.evaluate(&MatsubaraFreq::<S>::new(n)?))
136 }
137
138 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 fn power_model(poly: &PiecewiseLegendrePoly) -> PowerModel {
149 PowerModel::new(Self::power_moments(
153 &poly.derivs(poly.xmax()),
154 &poly.derivs(poly.xmin()),
155 ))
156 }
157
158 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 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 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 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 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 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 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 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 let xmid_0: Vec<f64> = (0..n_segments)
260 .map(|i| knots[i + 1] - delta_x_half[i])
261 .collect();
262
263 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 let diff = match shift {
273 -1 => xmid_m1[i],
274 0 => xmid_0[i],
275 1 => xmid_p1[i],
276 _ => xmid_0[i], };
278 xmid_diff.push(diff);
279 }
280
281 (xmid_diff, extra_shift)
282 }
283
284 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 let power = ((wn * (extra_shift[j] as i64 + 1)) % 4 + 4) % 4; let im_power = im_unit.powi(power as i32);
298
299 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 pub fn get_tnl(l: i32, w: f64) -> Complex64 {
315 let abs_w = w.abs();
316
317 let sph_bessel = spherical_bessel_j(l, abs_w);
319
320 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 if w < 0.0 { result.conj() } else { result }
327 }
328}
329
330struct 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#[derive(Debug, Clone)]
367pub struct PiecewiseLegendreFTVector<S: StatisticsType> {
368 pub(crate) polyvec: Vec<PiecewiseLegendreFT<S>>,
369 _phantom: std::marker::PhantomData<fn() -> S>,
371}
372
373pub type FermionicPiecewiseLegendreFTVector = PiecewiseLegendreFTVector<Fermionic>;
375pub type BosonicPiecewiseLegendreFTVector = PiecewiseLegendreFTVector<Bosonic>;
376
377impl<S: StatisticsType> PiecewiseLegendreFTVector<S> {
378 pub fn new() -> Self {
380 Self {
381 polyvec: Vec::new(),
382 _phantom: std::marker::PhantomData,
383 }
384 }
385
386 pub fn from_vector(polyvec: Vec<PiecewiseLegendreFT<S>>) -> Self {
388 Self {
389 polyvec,
390 _phantom: std::marker::PhantomData,
391 }
392 }
393
394 pub fn len(&self) -> usize {
396 self.polyvec.len()
397 }
398
399 pub fn is_empty(&self) -> bool {
401 self.polyvec.is_empty()
402 }
403
404 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 pub fn size(&self) -> usize {
430 self.polyvec.len()
431 }
432
433 pub fn get_polys(&self) -> &[PiecewiseLegendreFT<S>] {
435 &self.polyvec
436 }
437
438 pub fn get(&self, index: usize) -> Option<&PiecewiseLegendreFT<S>> {
440 self.polyvec.get(index)
441 }
442
443 pub fn get_mut(&mut self, index: usize) -> Option<&mut PiecewiseLegendreFT<S>> {
445 self.polyvec.get_mut(index)
446 }
447
448 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 pub fn similar(&self) -> Self {
468 Self::new()
469 }
470
471 pub fn n_asymp(&self) -> f64 {
473 self.polyvec.first().map_or(f64::INFINITY, |p| p.n_asymp)
474 }
475
476 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 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
518impl<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
533impl<S: StatisticsType> Default for PiecewiseLegendreFTVector<S> {
535 fn default() -> Self {
536 Self::new()
537 }
538}
539
540const 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
598pub(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 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
626pub(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 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#[derive(Clone, Copy)]
657enum Part {
658 Real,
659 Imaginary,
660}
661
662fn 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
693fn 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
708fn 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
729fn 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 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
759fn 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 if prev_val.signum() != val.signum() && prev_val != 0.0 && val != 0.0 {
774 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
784fn 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 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 let refined = bisect_discr_extremum(f, xgrid[i], xgrid[i + 2]);
810 results.push(refined);
811 }
812 }
813
814 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 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
829fn symmetrize_matsubara_inplace(xs: &mut Vec<i64>) {
831 if xs.is_empty() {
832 return;
833 }
834
835 xs.retain(|&x| x != 0);
837
838 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
847pub(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 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 let freqs: Vec<MatsubaraFreq<S>> = DEFAULT_GRID
932 .iter()
933 .map(|&k| MatsubaraFreq::new(2 * k + zeta))
934 .collect::<Result<_, _>>()?;
935 let used = PiecewiseLegendreFTVector::from_vector(uhat.polyvec[..n_fit].to_vec());
939 let values: Vec<Vec<Complex64>> = used.evaluate_at_many(&freqs);
940 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 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;