Skip to main content

sparse_ir_sve/
poly.rs

1//! Piecewise Legendre polynomials
2//!
3//! This module provides high-performance piecewise Legendre polynomial
4//! functionality compatible with the C++ implementation.
5
6use crate::error::Error;
7use crate::matrix::{Mat, Mat3};
8
9/// A single piecewise Legendre polynomial
10#[derive(Debug, Clone)]
11pub struct PiecewiseLegendrePoly {
12    /// Polynomial order (degree of Legendre polynomials in each segment)
13    pub(crate) polyorder: usize,
14    /// Minimum x value of the domain
15    pub(crate) xmin: f64,
16    /// Maximum x value of the domain
17    pub(crate) xmax: f64,
18    /// Knot points defining the segments
19    pub(crate) knots: Vec<f64>,
20    /// Segment widths (for numerical stability)
21    pub(crate) delta_x: Vec<f64>,
22    /// Coefficient matrix: [degree][segment_index]
23    pub(crate) data: Mat<f64>,
24    /// Symmetry parameter
25    pub(crate) symm: i32,
26    /// Index of this function in the sequence of singular functions it belongs
27    /// to (0-based, in order of non-increasing singular value)
28    ///
29    /// SVE results set it to the position of the function in the result, and
30    /// `PiecewiseLegendrePolyVector::from_3d_data` to the position in the
31    /// vector.
32    pub(crate) l: i32,
33    /// Segment midpoints
34    pub(crate) xm: Vec<f64>,
35    /// Inverse segment widths
36    pub(crate) inv_xs: Vec<f64>,
37    /// Normalization factors
38    pub(crate) norms: Vec<f64>,
39}
40
41/// `Ok` if there are `nsegments + 1` finite knots and every segment length is
42/// a positive normal double (so that `2 / length` is finite)
43fn check_knots(knots: &[f64], nsegments: usize) -> Result<(), Error> {
44    if knots.len() != nsegments + 1 {
45        return Err(Error::InvalidParameter {
46            name: "knots",
47            value: format!("{} knots", knots.len()),
48            reason: format!(
49                "must have {} entries, one more than the segments of data",
50                nsegments + 1
51            ),
52        });
53    }
54    if let Some((i, k)) = knots.iter().enumerate().find(|(_, k)| !k.is_finite()) {
55        return Err(Error::InvalidParameter {
56            name: "knots",
57            value: format!("{k:?} at index {i}"),
58            reason: "must be finite".to_string(),
59        });
60    }
61    for i in 1..knots.len() {
62        let length = knots[i] - knots[i - 1];
63        if !(length > 0.0 && length.is_normal()) {
64            return Err(Error::InvalidParameter {
65                name: "knots",
66                value: format!("{:?} after {:?} at index {i}", knots[i], knots[i - 1]),
67                reason: "must be strictly increasing, with each segment length a normal double"
68                    .to_string(),
69            });
70        }
71    }
72    Ok(())
73}
74
75/// `Ok` if `delta_x` has one entry per segment, each equal to the knot
76/// spacing `e = knots[i + 1] - knots[i]` within
77/// `max(1e-10 * |e|, 8 * f64::EPSILON * max(|knots[i]|, |knots[i + 1]|))`
78/// (NaN is rejected)
79///
80/// The first term is a relative tolerance on the segment length. The second
81/// covers the rounding of the knots, which grows with their magnitude: knots
82/// and widths scaled separately (as when the functions of an SVE on [-1, 1]
83/// are mapped onto a longer interval) differ by a few units in the last place
84/// of the knots, which next to large knots can exceed 1e-10 times a narrow
85/// segment.
86fn check_delta_x(delta_x: &[f64], knots: &[f64]) -> Result<(), Error> {
87    let nsegments = knots.len() - 1;
88    if delta_x.len() != nsegments {
89        return Err(Error::InvalidParameter {
90            name: "delta_x",
91            value: format!("{} entries", delta_x.len()),
92            reason: format!("must have one entry per segment ({nsegments})"),
93        });
94    }
95    for (i, &d) in delta_x.iter().enumerate() {
96        let expected = knots[i + 1] - knots[i];
97        let rounding = 8.0 * f64::EPSILON * knots[i].abs().max(knots[i + 1].abs());
98        let tolerance = (1e-10 * expected.abs()).max(rounding);
99        if !((d - expected).abs() <= tolerance) {
100            return Err(Error::InvalidParameter {
101                name: "delta_x",
102                value: format!("{d:?} at index {i}"),
103                reason: format!(
104                    "must equal the knot spacing {expected:?} to a relative 1e-10, or to 8 machine epsilons times the magnitude of the knots"
105                ),
106            });
107        }
108    }
109    Ok(())
110}
111
112impl PiecewiseLegendrePoly {
113    /// Create a new PiecewiseLegendrePoly from data and knots
114    ///
115    /// `data` holds the Legendre coefficients, one column per segment; the
116    /// `nsegments + 1` knots bound the segments. `delta_x` (the segment
117    /// widths) is computed from the knots when `None`. `symm` is the parity of
118    /// the polynomial: 1 (even), -1 (odd) or 0 (no definite parity).
119    ///
120    /// # Errors
121    ///
122    /// * [`Error::EmptyInput`] if `data` has no row or no column
123    /// * [`Error::InvalidParameter`] if `knots` does not have one entry more
124    ///   than `data` has columns, a knot is not finite, or a segment length
125    ///   `knots[i] - knots[i - 1]` is not a positive normal double (this
126    ///   includes decreasing knots, NaN, lengths that overflow and subnormal
127    ///   lengths); or if `delta_x` does not have one entry per segment or
128    ///   differs from the knot spacing `e` by more than
129    ///   `max(1e-10 * |e|, 8 * f64::EPSILON * max(|knots[i]|, |knots[i + 1]|))`
130    /// * [`Error::InvalidParameter`] if `symm` is not -1, 0 or 1
131    pub fn new(
132        data: Mat<f64>,
133        knots: Vec<f64>,
134        l: i32,
135        delta_x: Option<Vec<f64>>,
136        symm: i32,
137    ) -> Result<Self, Error> {
138        let polyorder = data.shape().0;
139        let nsegments = data.shape().1;
140        if polyorder == 0 || nsegments == 0 {
141            return Err(Error::EmptyInput { name: "data" });
142        }
143        check_knots(&knots, nsegments)?;
144
145        // Compute delta_x if not provided
146        let delta_x =
147            delta_x.unwrap_or_else(|| (1..knots.len()).map(|i| knots[i] - knots[i - 1]).collect());
148        check_delta_x(&delta_x, &knots)?;
149        if !matches!(symm, -1..=1) {
150            return Err(Error::InvalidParameter {
151                name: "symm",
152                value: symm.to_string(),
153                reason: "must be -1, 0 or 1".to_string(),
154            });
155        }
156
157        // Compute segment midpoints
158        let xm: Vec<f64> = (0..nsegments)
159            .map(|i| 0.5 * (knots[i] + knots[i + 1]))
160            .collect();
161
162        // Compute inverse segment widths
163        let inv_xs: Vec<f64> = delta_x.iter().map(|&dx| 2.0 / dx).collect();
164
165        // Compute normalization factors
166        let norms: Vec<f64> = inv_xs.iter().map(|&inv_x| inv_x.sqrt()).collect();
167
168        Ok(Self {
169            polyorder,
170            xmin: knots[0],
171            xmax: knots[knots.len() - 1],
172            knots,
173            delta_x,
174            data,
175            symm,
176            l,
177            xm,
178            inv_xs,
179            norms,
180        })
181    }
182
183    /// Create a new PiecewiseLegendrePoly with new data but same structure
184    ///
185    /// Crate-internal: `new_data` is not checked against the knots, so a
186    /// caller could break the invariants of the type.
187    pub(crate) fn with_data(&self, new_data: Mat<f64>) -> Self {
188        Self {
189            data: new_data,
190            ..self.clone()
191        }
192    }
193
194    /// Get the symmetry parameter
195    pub fn symm(&self) -> i32 {
196        self.symm
197    }
198
199    /// The polynomial with every coefficient negated
200    ///
201    /// Knots, widths and normalizations are those of `self`, so this equals
202    /// `new` on the negated data without repeating its checks.
203    pub(crate) fn negated(&self) -> Self {
204        self.with_data(Mat::<f64>::from_fn(self.data.dims(), |idx| -self.data[idx]))
205    }
206
207    /// Rescale domain: create a new polynomial with the same data but different knots
208    ///
209    /// This is useful for transforming from one domain to another, e.g.,
210    /// from [-1, 1] to [0, b].
211    ///
212    /// # Arguments
213    ///
214    /// * `new_knots` - New knot points
215    /// * `new_delta_x` - Optional new segment widths (computed from knots if None)
216    /// * `new_symm` - Optional new symmetry parameter (keeps old if None)
217    ///
218    /// # Returns
219    ///
220    /// New polynomial with rescaled domain
221    ///
222    /// # Errors
223    ///
224    /// The errors of [`new`](Self::new) for the new knots and widths
225    pub fn rescale_domain(
226        &self,
227        new_knots: Vec<f64>,
228        new_delta_x: Option<Vec<f64>>,
229        new_symm: Option<i32>,
230    ) -> Result<Self, Error> {
231        Self::new(
232            self.data.clone(),
233            new_knots,
234            self.l,
235            new_delta_x,
236            new_symm.unwrap_or(self.symm),
237        )
238    }
239
240    /// Scale all data values by a constant factor
241    ///
242    /// This is useful for normalizations, e.g., multiplying by √c to keep
243    /// the functions normalized after the domain is scaled by c.
244    ///
245    /// # Arguments
246    ///
247    /// * `factor` - Scaling factor to multiply all data by
248    ///
249    /// # Returns
250    ///
251    /// New polynomial with scaled data
252    pub fn scale_data(&self, factor: f64) -> Self {
253        Self::with_data(
254            self,
255            Mat::<f64>::from_fn(self.data.dims(), |idx| self.data[idx] * factor),
256        )
257    }
258
259    /// `Ok` if `x` lies in [xmin, xmax] (NaN does not)
260    fn check_in_domain(&self, name: &'static str, x: f64) -> Result<(), Error> {
261        if x >= self.xmin && x <= self.xmax {
262            Ok(())
263        } else {
264            Err(Error::OutOfDomain {
265                name,
266                value: x,
267                domain: (self.xmin, self.xmax),
268            })
269        }
270    }
271
272    /// Evaluate the polynomial at a given point
273    ///
274    /// # Panics
275    ///
276    /// Panics if `x` is outside [xmin, xmax] or NaN; see [`Self::try_evaluate`].
277    pub fn evaluate(&self, x: f64) -> f64 {
278        self.try_evaluate(x).unwrap_or_else(|e| panic!("{e}"))
279    }
280
281    /// [`Self::evaluate`] returning an error instead of panicking
282    ///
283    /// # Errors
284    ///
285    /// [`Error::OutOfDomain`] if `x` is outside [xmin, xmax] or NaN
286    pub fn try_evaluate(&self, x: f64) -> Result<f64, Error> {
287        self.check_in_domain("x", x)?;
288        Ok(self.evaluate_in_domain(x))
289    }
290
291    /// [`Self::evaluate`] for an `x` already checked to lie in the domain
292    fn evaluate_in_domain(&self, x: f64) -> f64 {
293        let (i, x_tilde) = self.split_in_domain(x);
294        // Extract column i into a Vec
295        let coeffs: Vec<f64> = (0..self.data.shape().0)
296            .map(|row| self.data[[row, i]])
297            .collect();
298        let value = legendre_series(x_tilde, &coeffs);
299        value * self.norms[i]
300    }
301
302    /// Evaluate the polynomial at multiple points
303    ///
304    /// # Panics
305    ///
306    /// Panics if a point is outside [xmin, xmax] or NaN; see
307    /// [`Self::try_evaluate_many`].
308    pub fn evaluate_many(&self, xs: &[f64]) -> Vec<f64> {
309        self.try_evaluate_many(xs).unwrap_or_else(|e| panic!("{e}"))
310    }
311
312    /// [`Self::evaluate_many`] returning an error instead of panicking
313    ///
314    /// # Errors
315    ///
316    /// [`Error::OutOfDomain`] for the first point of `xs` that is outside
317    /// [xmin, xmax] or NaN; no point is evaluated then
318    pub fn try_evaluate_many(&self, xs: &[f64]) -> Result<Vec<f64>, Error> {
319        for &x in xs {
320            self.check_in_domain("xs", x)?;
321        }
322        Ok(xs.iter().map(|&x| self.evaluate_in_domain(x)).collect())
323    }
324
325    /// Split x into segment index and normalized x
326    ///
327    /// # Panics
328    ///
329    /// Panics if `x` is outside [xmin, xmax] or NaN; see [`Self::try_split`].
330    pub fn split(&self, x: f64) -> (usize, f64) {
331        self.try_split(x).unwrap_or_else(|e| panic!("{e}"))
332    }
333
334    /// [`Self::split`] returning an error instead of panicking
335    ///
336    /// # Errors
337    ///
338    /// [`Error::OutOfDomain`] if `x` is outside [xmin, xmax] or NaN
339    pub fn try_split(&self, x: f64) -> Result<(usize, f64), Error> {
340        self.check_in_domain("x", x)?;
341        Ok(self.split_in_domain(x))
342    }
343
344    /// [`Self::split`] for an `x` already checked to lie in the domain
345    fn split_in_domain(&self, x: f64) -> (usize, f64) {
346        // Find the segment containing x
347        for i in 0..self.knots.len() - 1 {
348            if x >= self.knots[i] && x <= self.knots[i + 1] {
349                // Transform x to [-1, 1] for Legendre polynomials
350                let x_tilde = 2.0 * (x - self.xm[i]) / self.delta_x[i];
351                return (i, x_tilde);
352            }
353        }
354
355        // Handle edge case: x exactly at the last knot
356        let last_idx = self.knots.len() - 2;
357        let x_tilde = 2.0 * (x - self.xm[last_idx]) / self.delta_x[last_idx];
358        (last_idx, x_tilde)
359    }
360
361    /// Compute derivative of the polynomial
362    ///
363    /// The result has `polyorder` equal to the number of its coefficient rows
364    /// (at least 1).
365    pub fn deriv(&self, n: usize) -> Self {
366        if n == 0 {
367            return self.clone();
368        }
369
370        // Compute derivative coefficients
371        let mut ddata = self.data.clone();
372        for _ in 0..n {
373            ddata = self.compute_derivative_coefficients(&ddata);
374        }
375
376        // Apply scaling factors (C++: ddata.col(i) *= std::pow(inv_xs[i], n))
377        let ddata_shape = *ddata.shape();
378        for i in 0..ddata_shape.1 {
379            let inv_x_power = self.inv_xs[i].powi(n as i32);
380            for j in 0..ddata_shape.0 {
381                ddata[[j, i]] *= inv_x_power;
382            }
383        }
384
385        // Update symmetry: C++: int new_symm = std::pow(-1, n) * symm;
386        let new_symm = if n % 2 == 0 { self.symm } else { -self.symm };
387
388        Self {
389            polyorder: ddata.shape().0,
390            data: ddata,
391            symm: new_symm,
392            ..self.clone()
393        }
394    }
395
396    /// Compute derivative coefficients using the same algorithm as C++ legder function
397    fn compute_derivative_coefficients(&self, coeffs: &Mat<f64>) -> Mat<f64> {
398        let (nrows, ncols) = *coeffs.shape();
399        let ders: Vec<Vec<f64>> = (0..ncols)
400            .map(|col| legder(&(0..nrows).map(|row| coeffs[[row, col]]).collect::<Vec<_>>()))
401            .collect();
402        let der_rows = nrows.saturating_sub(1).max(1);
403        Mat::<f64>::from_fn([der_rows, ncols], |idx| ders[idx[1]][idx[0]])
404    }
405
406    /// Compute derivatives at a point x
407    ///
408    /// Returns the values of the derivatives of order 0 to `polyorder - 1`.
409    ///
410    /// # Panics
411    ///
412    /// Panics if `x` is outside [xmin, xmax] or NaN; see [`Self::try_derivs`].
413    pub fn derivs(&self, x: f64) -> Vec<f64> {
414        self.try_derivs(x).unwrap_or_else(|e| panic!("{e}"))
415    }
416
417    /// [`Self::derivs`] returning an error instead of panicking
418    ///
419    /// # Errors
420    ///
421    /// [`Error::OutOfDomain`] if `x` is outside [xmin, xmax] or NaN
422    pub fn try_derivs(&self, x: f64) -> Result<Vec<f64>, Error> {
423        let (i, x_tilde) = self.try_split(x)?;
424        // Differentiate only the segment containing x, one order at a time,
425        // and scale the coefficients (not the sum) as `deriv` does.
426        let mut coeffs: Vec<f64> = (0..self.data.shape().0)
427            .map(|row| self.data[[row, i]])
428            .collect();
429        let mut results = Vec::with_capacity(self.polyorder);
430        for n in 0..self.polyorder {
431            if n > 0 {
432                coeffs = legder(&coeffs);
433            }
434            let inv_x_power = self.inv_xs[i].powi(n as i32);
435            let scaled: Vec<f64> = coeffs.iter().map(|&c| c * inv_x_power).collect();
436            results.push(legendre_series(x_tilde, &scaled) * self.norms[i]);
437        }
438        Ok(results)
439    }
440
441    /// Compute overlap integral with a function
442    pub fn overlap<F>(&self, f: F) -> f64
443    where
444        F: Fn(f64) -> f64,
445    {
446        let mut integral = 0.0;
447
448        for i in 0..self.knots.len() - 1 {
449            let segment_integral =
450                self.gauss_legendre_quadrature(self.knots[i], self.knots[i + 1], |x| {
451                    self.evaluate(x) * f(x)
452                });
453            integral += segment_integral;
454        }
455
456        integral
457    }
458
459    /// Gauss-Legendre quadrature over [a, b]
460    fn gauss_legendre_quadrature<F>(&self, a: f64, b: f64, f: F) -> f64
461    where
462        F: Fn(f64) -> f64,
463    {
464        // 5-point Gauss-Legendre quadrature
465        const XG: [f64; 5] = [
466            -0.906179845938664,
467            -0.538469310105683,
468            0.0,
469            0.538469310105683,
470            0.906179845938664,
471        ];
472        const WG: [f64; 5] = [
473            0.236926885056189,
474            0.478628670499366,
475            0.568888888888889,
476            0.478628670499366,
477            0.236926885056189,
478        ];
479
480        let c1 = (b - a) / 2.0;
481        let c2 = (b + a) / 2.0;
482
483        let mut integral = 0.0;
484        for j in 0..5 {
485            let x = c1 * XG[j] + c2;
486            integral += WG[j] * f(x);
487        }
488
489        integral * c1
490    }
491
492    /// Find roots of the polynomial using C++ compatible algorithm
493    pub fn roots(&self) -> Vec<f64> {
494        let xmid = (self.xmax + self.xmin) / 2.0;
495
496        // Exploit symmetry: only search the right half, then mirror.
497        // This matches the Python 1.x / Julia v1 algorithm and guarantees
498        // exactly symmetric root positions.
499        let grid = if self.symm != 0 {
500            let nsegments = self.knots.len() - 1;
501            let mid_idx = nsegments / 2;
502            if (self.knots[mid_idx] - xmid).abs() < 1e-15 {
503                self.knots[mid_idx..].to_vec()
504            } else {
505                let mut g = vec![xmid];
506                g.extend(self.knots.iter().filter(|&&x| x > xmid));
507                g
508            }
509        } else {
510            self.knots.clone()
511        };
512
513        let refined_grid = self.refine_grid(&grid, 4);
514        let roots_half = self.find_all_roots(&refined_grid);
515
516        if self.symm == 1 {
517            // Even symmetry: roots on right half, mirror to left
518            let mut all_roots: Vec<f64> = roots_half
519                .iter()
520                .rev()
521                .map(|&r| (self.xmax + self.xmin) - r)
522                .collect();
523            all_roots.extend_from_slice(&roots_half);
524            all_roots
525        } else if self.symm == -1 {
526            // Odd symmetry: there must be a zero at xmid
527            let mut right = roots_half;
528            if !right.is_empty() {
529                // Remove the root at xmid if found (may be slightly off),
530                // or if f(xmid) and f'(xmid) have opposite signs (spurious zero)
531                let f_mid = self.evaluate(xmid);
532                let f_deriv_mid = self.deriv(1).evaluate(xmid);
533                if (right[0] - xmid).abs() < 1e-13 || f_mid * f_deriv_mid < 0.0 {
534                    right.remove(0);
535                }
536            }
537            let mut all_roots: Vec<f64> = right
538                .iter()
539                .rev()
540                .map(|&r| (self.xmax + self.xmin) - r)
541                .collect();
542            all_roots.push(xmid);
543            all_roots.extend_from_slice(&right);
544            all_roots
545        } else {
546            // No symmetry: search the full domain
547            let full_grid = self.refine_grid(&self.knots, 4);
548            self.find_all_roots(&full_grid)
549        }
550    }
551
552    /// Refine grid by factor alpha (C++ compatible)
553    fn refine_grid(&self, grid: &[f64], alpha: usize) -> Vec<f64> {
554        let mut refined = Vec::new();
555
556        for i in 0..grid.len() - 1 {
557            let start = grid[i];
558            let step = (grid[i + 1] - grid[i]) / (alpha as f64);
559            for j in 0..alpha {
560                refined.push(start + (j as f64) * step);
561            }
562        }
563        refined.push(grid[grid.len() - 1]);
564        refined
565    }
566
567    /// Find all roots using refined grid (C++ compatible)
568    fn find_all_roots(&self, xgrid: &[f64]) -> Vec<f64> {
569        if xgrid.is_empty() {
570            return Vec::new();
571        }
572
573        // Evaluate function at all grid points
574        let fx: Vec<f64> = xgrid.iter().map(|&x| self.evaluate(x)).collect();
575
576        // Find exact zeros (direct hits)
577        let mut x_hit = Vec::new();
578        for i in 0..fx.len() {
579            if fx[i] == 0.0 {
580                x_hit.push(xgrid[i]);
581            }
582        }
583
584        // Find sign changes
585        let mut sign_change = Vec::new();
586        for i in 0..fx.len() - 1 {
587            let has_sign_change = fx[i].signum() != fx[i + 1].signum();
588            let not_hit = fx[i] != 0.0 && fx[i + 1] != 0.0;
589            let sc = has_sign_change && not_hit;
590            sign_change.push(sc);
591        }
592
593        // If no sign changes, return only direct hits
594        if sign_change.iter().all(|&sc| !sc) {
595            x_hit.sort_by(|a, b| a.partial_cmp(b).unwrap());
596            return x_hit;
597        }
598
599        // Find intervals with sign changes
600        let mut a_intervals = Vec::new();
601        let mut b_intervals = Vec::new();
602        let mut fa_values = Vec::new();
603
604        for i in 0..sign_change.len() {
605            if sign_change[i] {
606                a_intervals.push(xgrid[i]);
607                b_intervals.push(xgrid[i + 1]);
608                fa_values.push(fx[i]);
609            }
610        }
611
612        // Calculate epsilon for convergence
613        let max_elm = xgrid.iter().map(|&x| x.abs()).fold(0.0, f64::max);
614        let epsilon_x = f64::EPSILON * max_elm;
615
616        // Use bisection for each interval with sign change
617        for i in 0..a_intervals.len() {
618            let root = self.bisect(a_intervals[i], b_intervals[i], fa_values[i], epsilon_x);
619            x_hit.push(root);
620        }
621
622        // Sort and return
623        x_hit.sort_by(|a, b| a.partial_cmp(b).unwrap());
624        x_hit
625    }
626
627    /// Bisection method to find root (C++ compatible)
628    fn bisect(&self, a: f64, b: f64, fa: f64, eps: f64) -> f64 {
629        let mut a = a;
630        let mut b = b;
631        let mut fa = fa;
632
633        loop {
634            let mid = (a + b) / 2.0;
635            if self.close_enough(a, mid, eps) {
636                return mid;
637            }
638
639            let fmid = self.evaluate(mid);
640            if fa.signum() != fmid.signum() {
641                b = mid;
642            } else {
643                a = mid;
644                fa = fmid;
645            }
646        }
647    }
648
649    /// Check if two values are close enough (C++ compatible)
650    fn close_enough(&self, a: f64, b: f64, eps: f64) -> bool {
651        (a - b).abs() <= eps
652    }
653
654    /// Lower end of the domain
655    pub fn xmin(&self) -> f64 {
656        self.xmin
657    }
658    /// Upper end of the domain
659    pub fn xmax(&self) -> f64 {
660        self.xmax
661    }
662    /// Index of the function in its sequence of singular functions
663    /// (0-based, in order of non-increasing singular value)
664    pub fn l(&self) -> i32 {
665        self.l
666    }
667    /// The domain `(xmin, xmax)`
668    pub fn domain(&self) -> (f64, f64) {
669        (self.xmin, self.xmax)
670    }
671    /// Segment boundaries, strictly increasing from `xmin` to `xmax`
672    pub fn knots(&self) -> &[f64] {
673        &self.knots
674    }
675    /// Segment lengths
676    pub fn delta_x(&self) -> &[f64] {
677        &self.delta_x
678    }
679    /// Legendre coefficients, `polyorder × nsegments` (one column per
680    /// segment)
681    pub fn data(&self) -> &Mat<f64> {
682        &self.data
683    }
684    /// Normalization of the Legendre polynomials on each segment
685    pub fn norms(&self) -> &[f64] {
686        &self.norms
687    }
688    /// Number of Legendre coefficients per segment (degree + 1)
689    pub fn polyorder(&self) -> usize {
690        self.polyorder
691    }
692}
693
694/// The Legendre series Σ_n coeffs[n] P_n(x), by the three-term recurrence
695pub(crate) fn legendre_series(x: f64, coeffs: &[f64]) -> f64 {
696    if coeffs.is_empty() {
697        return 0.0;
698    }
699
700    let mut result = 0.0;
701    let mut p_prev = 1.0; // P_0(x) = 1
702    let mut p_curr = x; // P_1(x) = x
703
704    // Add first two terms
705    if !coeffs.is_empty() {
706        result += coeffs[0] * p_prev;
707    }
708    if coeffs.len() > 1 {
709        result += coeffs[1] * p_curr;
710    }
711
712    // Use recurrence relation: P_{n+1}(x) = ((2n+1)x*P_n(x) - n*P_{n-1}(x))/(n+1)
713    for n in 1..coeffs.len() - 1 {
714        let p_next =
715            ((2.0 * (n as f64) + 1.0) * x * p_curr - (n as f64) * p_prev) / ((n + 1) as f64);
716        result += coeffs[n + 1] * p_next;
717        p_prev = p_curr;
718        p_curr = p_next;
719    }
720
721    result
722}
723
724/// Coefficients of the derivative of the Legendre series `c`
725/// (the same algorithm as the C++ legder function with cnt = 1)
726fn legder(c: &[f64]) -> Vec<f64> {
727    if c.len() <= 1 {
728        return vec![0.0];
729    }
730    let mut c = c.to_vec();
731    let n = c.len() - 1;
732    let mut der = vec![0.0; n];
733    for j in (2..=n).rev() {
734        der[j - 1] = (2.0 * (j as f64) - 1.0) * c[j];
735        c[j - 2] += c[j];
736    }
737    if n > 1 {
738        der[1] = 3.0 * c[2];
739    }
740    der[0] = c[1];
741    der
742}
743
744/// Vector of piecewise Legendre polynomials
745#[derive(Debug, Clone)]
746pub struct PiecewiseLegendrePolyVector {
747    /// Individual polynomials
748    pub(crate) polyvec: Vec<PiecewiseLegendrePoly>,
749}
750
751impl PiecewiseLegendrePolyVector {
752    /// Constructor with a vector of PiecewiseLegendrePoly
753    ///
754    /// # Errors
755    ///
756    /// * [`Error::EmptyInput`] if `polyvec` is empty
757    /// * [`Error::InvalidParameter`] if a polynomial has other knots or
758    ///   another data shape than the first: the accessors of the vector
759    ///   (`get_knots`, `get_data`, ...) describe all of them by the first
760    pub fn new(polyvec: Vec<PiecewiseLegendrePoly>) -> Result<Self, Error> {
761        let Some(first) = polyvec.first() else {
762            return Err(Error::EmptyInput { name: "polyvec" });
763        };
764        if let Some(i) = polyvec
765            .iter()
766            .position(|p| p.knots != first.knots || p.data.shape() != first.data.shape())
767        {
768            return Err(Error::InvalidParameter {
769                name: "polyvec",
770                value: format!("polynomial {i}"),
771                reason: "must have the knots and the data shape of polynomial 0".to_string(),
772            });
773        }
774        Ok(Self { polyvec })
775    }
776
777    /// Constructor that skips the checks of [`Self::new`]
778    ///
779    /// For the SVE, which builds every polynomial of a vector from the same
780    /// knots and the same data shape and may legitimately build an empty
781    /// vector (a symmetrized half of an expansion with no singular value of
782    /// that parity).
783    pub(crate) fn from_polys_unchecked(polyvec: Vec<PiecewiseLegendrePoly>) -> Self {
784        Self { polyvec }
785    }
786
787    /// The polynomials
788    pub fn polys(&self) -> &[PiecewiseLegendrePoly] {
789        &self.polyvec
790    }
791
792    /// Constructor with a 3D array, knots, and symmetry vector
793    ///
794    /// `data3d` has the shape `(polyorder, nsegments, npolys)`; polynomial `i`
795    /// gets `l = i` and the symmetry `symm[i]` (0 if `symm` is `None`).
796    ///
797    /// # Errors
798    ///
799    /// * [`Error::EmptyInput`] if `data3d` has no polynomial
800    /// * [`Error::InvalidParameter`] if `symm` does not have one entry per
801    ///   polynomial
802    /// * The errors of [`PiecewiseLegendrePoly::new`] for the data and knots
803    pub fn from_3d_data(
804        data3d: Mat3<f64>,
805        knots: Vec<f64>,
806        symm: Option<Vec<i32>>,
807    ) -> Result<Self, Error> {
808        let npolys = data3d.shape().2;
809        if npolys == 0 {
810            return Err(Error::EmptyInput { name: "data3d" });
811        }
812        let mut polyvec = Vec::with_capacity(npolys);
813
814        if let Some(ref symm_vec) = symm {
815            if symm_vec.len() != npolys {
816                return Err(Error::InvalidParameter {
817                    name: "symm",
818                    value: format!("{} entries", symm_vec.len()),
819                    reason: format!("must have one entry per polynomial ({npolys})"),
820                });
821            }
822        }
823
824        // Compute delta_x from knots
825        let delta_x: Vec<f64> = (1..knots.len()).map(|i| knots[i] - knots[i - 1]).collect();
826
827        for i in 0..npolys {
828            // Extract 2D data for this polynomial
829            let data3d_shape = data3d.shape();
830            let mut data = Mat::<f64>::from_elem([data3d_shape.0, data3d_shape.1], 0.0);
831            for j in 0..data3d_shape.0 {
832                for k in 0..data3d_shape.1 {
833                    data[[j, k]] = data3d[[j, k, i]];
834                }
835            }
836
837            let poly = PiecewiseLegendrePoly::new(
838                data,
839                knots.clone(),
840                i as i32,
841                Some(delta_x.clone()),
842                symm.as_ref().map_or(0, |s| s[i]),
843            )?;
844
845            polyvec.push(poly);
846        }
847
848        Ok(Self { polyvec })
849    }
850
851    /// Number of polynomials
852    pub fn len(&self) -> usize {
853        self.polyvec.len()
854    }
855
856    /// Whether there is no polynomial
857    pub fn is_empty(&self) -> bool {
858        self.polyvec.is_empty()
859    }
860
861    /// Rescale domain for all polynomials in the vector
862    ///
863    /// Creates a new PiecewiseLegendrePolyVector where each polynomial has
864    /// the same data but new knots and delta_x.
865    ///
866    /// # Arguments
867    ///
868    /// * `new_knots` - New knot points (same for all polynomials)
869    /// * `new_delta_x` - Optional new segment widths
870    /// * `new_symm` - Optional vector of new symmetry parameters (one per polynomial)
871    ///
872    /// # Returns
873    ///
874    /// New vector with rescaled domains
875    ///
876    /// # Errors
877    ///
878    /// * [`Error::InvalidParameter`] if `new_symm` does not have one entry per
879    ///   polynomial
880    /// * The errors of [`PiecewiseLegendrePoly::rescale_domain`]
881    pub fn rescale_domain(
882        &self,
883        new_knots: Vec<f64>,
884        new_delta_x: Option<Vec<f64>>,
885        new_symm: Option<Vec<i32>>,
886    ) -> Result<Self, Error> {
887        if let Some(symm) = &new_symm {
888            if symm.len() != self.polyvec.len() {
889                return Err(Error::InvalidParameter {
890                    name: "new_symm",
891                    value: format!("{} entries", symm.len()),
892                    reason: format!(
893                        "must have one entry per polynomial ({})",
894                        self.polyvec.len()
895                    ),
896                });
897            }
898        }
899        let polyvec = self
900            .polyvec
901            .iter()
902            .enumerate()
903            .map(|(i, poly)| {
904                let symm = new_symm.as_ref().map(|s| s[i]);
905                poly.rescale_domain(new_knots.clone(), new_delta_x.clone(), symm)
906            })
907            .collect::<Result<_, _>>()?;
908        Ok(Self { polyvec })
909    }
910
911    /// Scale all data values by a constant factor
912    ///
913    /// Multiplies the data of all polynomials by the same factor.
914    ///
915    /// # Arguments
916    ///
917    /// * `factor` - Scaling factor to multiply all data by
918    ///
919    /// # Returns
920    ///
921    /// New vector with scaled data
922    pub fn scale_data(&self, factor: f64) -> Self {
923        let polyvec = self
924            .polyvec
925            .iter()
926            .map(|poly| poly.scale_data(factor))
927            .collect();
928
929        Self { polyvec }
930    }
931
932    /// Get polynomial by index (immutable)
933    pub fn get(&self, index: usize) -> Option<&PiecewiseLegendrePoly> {
934        self.polyvec.get(index)
935    }
936
937    /// Get polynomial by index (mutable) - deprecated, use immutable design instead
938    #[deprecated(
939        note = "PiecewiseLegendrePolyVector is designed to be immutable. Use get() and create new instances for modifications."
940    )]
941    pub fn get_mut(&mut self, index: usize) -> Option<&mut PiecewiseLegendrePoly> {
942        self.polyvec.get_mut(index)
943    }
944
945    /// Extract a single polynomial as a vector
946    pub fn slice_single(&self, index: usize) -> Option<Self> {
947        self.polyvec.get(index).map(|poly| Self {
948            polyvec: vec![poly.clone()],
949        })
950    }
951
952    /// Extract multiple polynomials by indices, in the order of `indices`
953    ///
954    /// # Errors
955    ///
956    /// * [`Error::EmptyInput`] if `indices` is empty
957    /// * [`Error::InvalidParameter`] for the first index that is out of range
958    ///   or repeats an earlier one
959    pub fn slice_multi(&self, indices: &[usize]) -> Result<Self, Error> {
960        if indices.is_empty() {
961            return Err(Error::EmptyInput { name: "indices" });
962        }
963        let len = self.polyvec.len();
964        let mut seen = vec![false; len];
965        for &idx in indices {
966            if idx >= len {
967                return Err(Error::InvalidParameter {
968                    name: "indices",
969                    value: format!("{idx}"),
970                    reason: format!("must be less than the size {len}"),
971                });
972            }
973            if seen[idx] {
974                return Err(Error::InvalidParameter {
975                    name: "indices",
976                    value: format!("{idx}"),
977                    reason: "must not repeat".to_string(),
978                });
979            }
980            seen[idx] = true;
981        }
982
983        let new_polyvec: Vec<_> = indices
984            .iter()
985            .map(|&idx| self.polyvec[idx].clone())
986            .collect();
987
988        Ok(Self {
989            polyvec: new_polyvec,
990        })
991    }
992
993    /// Evaluate all polynomials at a single point
994    ///
995    /// # Panics
996    ///
997    /// Panics if `x` is outside the domain of a polynomial or NaN; see
998    /// [`Self::try_evaluate_at`].
999    pub fn evaluate_at(&self, x: f64) -> Vec<f64> {
1000        self.try_evaluate_at(x).unwrap_or_else(|e| panic!("{e}"))
1001    }
1002
1003    /// [`Self::evaluate_at`] returning an error instead of panicking
1004    ///
1005    /// # Errors
1006    ///
1007    /// [`Error::OutOfDomain`] if `x` is outside the domain of a polynomial
1008    /// or NaN
1009    pub fn try_evaluate_at(&self, x: f64) -> Result<Vec<f64>, Error> {
1010        self.polyvec
1011            .iter()
1012            .map(|poly| poly.try_evaluate(x))
1013            .collect()
1014    }
1015
1016    /// Evaluate all polynomials at multiple points
1017    ///
1018    /// The result has the shape `(size, xs.len())`.
1019    ///
1020    /// # Panics
1021    ///
1022    /// Panics if a point is outside the domain of a polynomial or NaN; see
1023    /// [`Self::try_evaluate_at_many`].
1024    pub fn evaluate_at_many(&self, xs: &[f64]) -> Mat<f64> {
1025        self.try_evaluate_at_many(xs)
1026            .unwrap_or_else(|e| panic!("{e}"))
1027    }
1028
1029    /// [`Self::evaluate_at_many`] returning an error instead of panicking
1030    ///
1031    /// # Errors
1032    ///
1033    /// [`Error::OutOfDomain`] for the first point of `xs` that is outside
1034    /// the domain of a polynomial or NaN; every point is checked before any
1035    /// is evaluated
1036    pub fn try_evaluate_at_many(&self, xs: &[f64]) -> Result<Mat<f64>, Error> {
1037        // `new` gives every polynomial the knots of the first, so checking the
1038        // points against the first checks them against all of them.
1039        if let Some(first) = self.polyvec.first() {
1040            for &x in xs {
1041                first.check_in_domain("xs", x)?;
1042            }
1043        }
1044        let n_funcs = self.polyvec.len();
1045        let n_points = xs.len();
1046        let mut results = Mat::<f64>::from_elem([n_funcs, n_points], 0.0);
1047
1048        for (i, poly) in self.polyvec.iter().enumerate() {
1049            for (j, &x) in xs.iter().enumerate() {
1050                results[[i, j]] = poly.evaluate_in_domain(x);
1051            }
1052        }
1053
1054        Ok(results)
1055    }
1056
1057    pub fn xmin(&self) -> f64 {
1058        if self.polyvec.is_empty() {
1059            panic!("Cannot get xmin from empty PiecewiseLegendrePolyVector");
1060        }
1061        self.polyvec[0].xmin
1062    }
1063
1064    pub fn xmax(&self) -> f64 {
1065        if self.polyvec.is_empty() {
1066            panic!("Cannot get xmax from empty PiecewiseLegendrePolyVector");
1067        }
1068        self.polyvec[0].xmax
1069    }
1070
1071    /// The knots of all the polynomials, merged where closer than
1072    /// `tolerance` (1e-10 by default)
1073    pub fn knots(&self, tolerance: Option<f64>) -> Vec<f64> {
1074        if self.polyvec.is_empty() {
1075            panic!("Cannot get knots from empty PiecewiseLegendrePolyVector");
1076        }
1077        const DEFAULT_TOLERANCE: f64 = 1e-10;
1078        let tolerance = tolerance.unwrap_or(DEFAULT_TOLERANCE);
1079
1080        // Collect all knots from all polynomials
1081        let mut all_knots = Vec::new();
1082        for poly in &self.polyvec {
1083            for &knot in &poly.knots {
1084                all_knots.push(knot);
1085            }
1086        }
1087
1088        // Sort and remove duplicates
1089        {
1090            all_knots.sort_by(|a, b| a.partial_cmp(b).unwrap());
1091            all_knots.dedup_by(|a, b| (*a - *b).abs() < tolerance);
1092        }
1093        all_knots
1094    }
1095
1096    /// Segment lengths of the first polynomial
1097    pub fn delta_x(&self) -> Vec<f64> {
1098        if self.polyvec.is_empty() {
1099            panic!("Cannot get delta_x from empty PiecewiseLegendrePolyVector");
1100        }
1101        self.polyvec[0].delta_x.clone()
1102    }
1103
1104    /// Number of Legendre coefficients per segment (degree + 1)
1105    pub fn polyorder(&self) -> usize {
1106        if self.polyvec.is_empty() {
1107            panic!("Cannot get polyorder from empty PiecewiseLegendrePolyVector");
1108        }
1109        self.polyvec[0].polyorder
1110    }
1111
1112    /// Normalization of the Legendre polynomials on each segment
1113    pub fn norms(&self) -> &[f64] {
1114        if self.polyvec.is_empty() {
1115            panic!("Cannot get norms from empty PiecewiseLegendrePolyVector");
1116        }
1117        &self.polyvec[0].norms
1118    }
1119
1120    /// Parity of each polynomial: 1 even, -1 odd, 0 none
1121    pub fn symm(&self) -> Vec<i32> {
1122        if self.polyvec.is_empty() {
1123            panic!("Cannot get symm from empty PiecewiseLegendrePolyVector");
1124        }
1125        self.polyvec.iter().map(|poly| poly.symm).collect()
1126    }
1127
1128    /// Legendre coefficients as an `nsegments × polyorder × npolys` array:
1129    /// element `[s, l, i]` is the coefficient of degree `l` on segment `s` of
1130    /// polynomial `i`
1131    ///
1132    /// The first two axes are in the opposite order to those of
1133    /// [`PiecewiseLegendrePoly::data`] and of the array that
1134    /// [`Self::from_3d_data`] takes.
1135    pub fn data(&self) -> Mat3<f64> {
1136        if self.polyvec.is_empty() {
1137            panic!("Cannot get data from empty PiecewiseLegendrePolyVector");
1138        }
1139
1140        let nsegments = self.polyvec[0].data.shape().1;
1141        let polyorder = self.polyvec[0].polyorder;
1142        let npolys = self.polyvec.len();
1143
1144        let mut data = Mat3::<f64>::from_elem([nsegments, polyorder, npolys], 0.0);
1145
1146        for (poly_idx, poly) in self.polyvec.iter().enumerate() {
1147            for segment in 0..nsegments {
1148                for degree in 0..polyorder {
1149                    data[[segment, degree, poly_idx]] = poly.data[[degree, segment]];
1150                }
1151            }
1152        }
1153
1154        data
1155    }
1156
1157    /// Find roots of all polynomials
1158    pub fn roots(&self, tolerance: Option<f64>) -> Vec<f64> {
1159        if self.polyvec.is_empty() {
1160            panic!("Cannot get roots from empty PiecewiseLegendrePolyVector");
1161        }
1162        const DEFAULT_TOLERANCE: f64 = 1e-10;
1163        let tolerance = tolerance.unwrap_or(DEFAULT_TOLERANCE);
1164        let mut all_roots = Vec::new();
1165
1166        for poly in &self.polyvec {
1167            let poly_roots = poly.roots();
1168            for root in poly_roots {
1169                all_roots.push(root);
1170            }
1171        }
1172
1173        // Sort in descending order and remove duplicates (like C++ implementation)
1174        {
1175            all_roots.sort_by(|a, b| b.partial_cmp(a).unwrap());
1176            all_roots.dedup_by(|a, b| (*a - *b).abs() < tolerance);
1177        }
1178        all_roots
1179    }
1180
1181    /// Get reference to last polynomial
1182    ///
1183    /// C++ equivalent: u.polyvec.back()
1184    pub fn last(&self) -> &PiecewiseLegendrePoly {
1185        self.polyvec
1186            .last()
1187            .expect("Cannot get last from empty PiecewiseLegendrePolyVector")
1188    }
1189
1190    /// Get the number of roots
1191    pub fn nroots(&self, tolerance: Option<f64>) -> usize {
1192        if self.polyvec.is_empty() {
1193            panic!("Cannot get nroots from empty PiecewiseLegendrePolyVector");
1194        }
1195        self.roots(tolerance).len()
1196    }
1197}
1198
1199impl std::ops::Index<usize> for PiecewiseLegendrePolyVector {
1200    type Output = PiecewiseLegendrePoly;
1201
1202    fn index(&self, index: usize) -> &Self::Output {
1203        &self.polyvec[index]
1204    }
1205}
1206
1207#[cfg(test)]
1208#[path = "poly_tests.rs"]
1209mod poly_tests;