Skip to main content

sparse_ir_sve/
gauss.rs

1//! Gauss quadrature rules for numerical integration
2//!
3//! This module provides quadrature rules for approximating integrals by weighted sums.
4//!
5//! The integral of f(x) * omega(x) is approximated by a weighted sum:
6//!
7//! sum(f(xi) * wi for (xi, wi) in zip(x, w))
8//!
9//! where we generally have superexponential convergence for smooth f(x)
10//! with the number of quadrature points.
11
12use crate::error::Error;
13use crate::matrix::Mat;
14use crate::numeric::CustomNumeric;
15use std::fmt::Debug;
16
17/// `Ok` if there is one weight per point
18fn check_weights<T>(x: &[T], w: &[T]) -> Result<(), Error> {
19    if x.len() == w.len() {
20        Ok(())
21    } else {
22        Err(Error::InvalidParameter {
23            name: "w",
24            value: format!("{} weights", w.len()),
25            reason: format!("must have one weight per point ({})", x.len()),
26        })
27    }
28}
29
30/// Quadrature rule for numerical integration.
31///
32/// Represents an approximation of an integral by a weighted sum over discrete points.
33/// The rule contains quadrature points `x`, weights `w`, and auxiliary arrays
34/// `x_forward` and `x_backward` for efficient computation.
35#[derive(Debug, Clone)]
36pub struct Rule<T> {
37    /// Quadrature points, in non-decreasing order
38    pub(crate) x: Vec<T>,
39    /// Quadrature weights
40    pub(crate) w: Vec<T>,
41    /// Distance from left endpoint: x - a
42    pub(crate) x_forward: Vec<T>,
43    /// Distance from right endpoint: b - x
44    pub(crate) x_backward: Vec<T>,
45    /// Left endpoint of integration interval
46    pub(crate) a: T,
47    /// Right endpoint of integration interval
48    pub(crate) b: T,
49}
50
51impl<T: Copy> Rule<T> {
52    /// Quadrature points, in non-decreasing order
53    pub fn x(&self) -> &[T] {
54        &self.x
55    }
56
57    /// Quadrature weights, one per point
58    pub fn w(&self) -> &[T] {
59        &self.w
60    }
61
62    /// Distance of each point from the left endpoint: `x - a`
63    pub fn x_forward(&self) -> &[T] {
64        &self.x_forward
65    }
66
67    /// Distance of each point from the right endpoint: `b - x`
68    pub fn x_backward(&self) -> &[T] {
69        &self.x_backward
70    }
71
72    /// Left endpoint of the integration interval
73    pub fn a(&self) -> T {
74        self.a
75    }
76
77    /// Right endpoint of the integration interval
78    pub fn b(&self) -> T {
79        self.b
80    }
81}
82
83impl<T> Rule<T>
84where
85    T: CustomNumeric,
86{
87    /// Create a new quadrature rule from points and weights.
88    ///
89    /// # Arguments
90    /// * `x` - Quadrature points
91    /// * `w` - Quadrature weights
92    /// * `a` - Left endpoint
93    /// * `b` - Right endpoint
94    ///
95    /// The points are not checked for order or for lying in `[a, b]`;
96    /// [`Self::validate`] does that.
97    ///
98    /// # Errors
99    /// [`Error::InvalidParameter`] if x and w have different lengths.
100    pub fn new(x: Vec<T>, w: Vec<T>, a: T, b: T) -> Result<Self, Error> {
101        check_weights(&x, &w)?;
102
103        let x_forward: Vec<T> = x.iter().map(|&xi| xi - a).collect();
104        let x_backward: Vec<T> = x.iter().map(|&xi| b - xi).collect();
105
106        Ok(Self {
107            x,
108            w,
109            x_forward,
110            x_backward,
111            a,
112            b,
113        })
114    }
115
116    /// Create a default rule with empty arrays.
117    pub fn empty() -> Self {
118        Self {
119            x: vec![],
120            w: vec![],
121            x_forward: vec![],
122            x_backward: vec![],
123            a: <T as CustomNumeric>::from_f64_unchecked(-1.0),
124            b: <T as CustomNumeric>::from_f64_unchecked(1.0),
125        }
126    }
127
128    /// Reseat the rule to a new interval [a, b].
129    ///
130    /// Scales and translates the quadrature points and weights to the new interval.
131    pub fn reseat(&self, a: T, b: T) -> Self {
132        let scaling = (b - a) / (self.b - self.a);
133        let midpoint_old = (self.b + self.a) * <T as CustomNumeric>::from_f64_unchecked(0.5);
134        let midpoint_new = (b + a) * <T as CustomNumeric>::from_f64_unchecked(0.5);
135
136        // Transform x: scaling * (xi - midpoint_old) + midpoint_new
137        let new_x: Vec<T> = self
138            .x
139            .iter()
140            .map(|&xi| scaling * (xi - midpoint_old) + midpoint_new)
141            .collect();
142        let new_w: Vec<T> = self.w.iter().map(|&wi| wi * scaling).collect();
143        let new_x_forward: Vec<T> = self.x_forward.iter().map(|&xi| xi * scaling).collect();
144        let new_x_backward: Vec<T> = self.x_backward.iter().map(|&xi| xi * scaling).collect();
145
146        Self {
147            x: new_x,
148            w: new_w,
149            x_forward: new_x_forward,
150            x_backward: new_x_backward,
151            a,
152            b,
153        }
154    }
155
156    /// Scale the weights by a factor.
157    pub fn scale(&self, factor: T) -> Self {
158        Self {
159            x: self.x.clone(),
160            w: self.w.iter().map(|&wi| wi * factor).collect(),
161            x_forward: self.x_forward.clone(),
162            x_backward: self.x_backward.clone(),
163            a: self.a,
164            b: self.b,
165        }
166    }
167
168    /// Create a piecewise rule over multiple segments.
169    ///
170    /// # Arguments
171    /// * `edges` - Segment boundaries: at least 2, finite and strictly
172    ///   increasing, with finite segment lengths and a finite sum of the ends
173    ///   of each segment (the midpoint of the segment is computed from it)
174    ///
175    /// # Errors
176    /// [`Error::InvalidParameter`] if `edges` does not meet these conditions
177    pub fn piecewise(&self, edges: &[T]) -> Result<Self, Error> {
178        if edges.len() < 2 {
179            return Err(Error::InvalidParameter {
180                name: "edges",
181                value: format!("{} edges", edges.len()),
182                reason: "must have at least 2 entries".to_string(),
183            });
184        }
185        if let Some((i, e)) = edges
186            .iter()
187            .enumerate()
188            .find(|(_, e)| !e.to_f64().is_finite())
189        {
190            return Err(Error::InvalidParameter {
191                name: "edges",
192                value: format!("{:?} at index {i}", e.to_f64()),
193                reason: "must be finite".to_string(),
194            });
195        }
196        for i in 1..edges.len() {
197            let length = (edges[i] - edges[i - 1]).to_f64();
198            if !(length > 0.0 && length.is_finite()) {
199                return Err(Error::InvalidParameter {
200                    name: "edges",
201                    value: format!(
202                        "{:?} after {:?} at index {i}",
203                        edges[i].to_f64(),
204                        edges[i - 1].to_f64()
205                    ),
206                    reason: "must be strictly increasing, with finite segment lengths".to_string(),
207                });
208            }
209            // `reseat` computes the midpoint as (a + b) * 0.5
210            if !(edges[i] + edges[i - 1]).to_f64().is_finite() {
211                return Err(Error::InvalidParameter {
212                    name: "edges",
213                    value: format!(
214                        "{:?} after {:?} at index {i}",
215                        edges[i].to_f64(),
216                        edges[i - 1].to_f64()
217                    ),
218                    reason: "must have a finite sum of the ends of each segment".to_string(),
219                });
220            }
221        }
222
223        let mut rules = Vec::new();
224        for i in 0..edges.len() - 1 {
225            let rule = self.reseat(edges[i], edges[i + 1]);
226            rules.push(rule);
227        }
228
229        Ok(Self::join(&rules))
230    }
231
232    /// Join multiple rules into a single rule.
233    ///
234    /// # Arguments
235    /// * `rules` - Vector of rules to join (must be contiguous and sorted)
236    ///
237    /// # Panics
238    /// Panics if rules are empty, not contiguous, or not sorted.
239    pub fn join(rules: &[Self]) -> Self {
240        if rules.is_empty() {
241            return Self::empty();
242        }
243
244        let a = rules[0].a;
245        let b = rules[rules.len() - 1].b;
246
247        // Check that rules are contiguous
248        for i in 1..rules.len() {
249            if (rules[i].a - rules[i - 1].b).abs() > T::epsilon() {
250                panic!("rules must be contiguous");
251            }
252        }
253
254        // Concatenate all arrays
255        let mut x_vec = Vec::new();
256        let mut w_vec = Vec::new();
257        let mut x_forward_vec = Vec::new();
258        let mut x_backward_vec = Vec::new();
259
260        for rule in rules {
261            // Adjust x_forward and x_backward for global coordinates
262            let x_forward_adj: Vec<T> =
263                rule.x_forward.iter().map(|&xi| xi + (rule.a - a)).collect();
264            let x_backward_adj: Vec<T> = rule
265                .x_backward
266                .iter()
267                .map(|&xi| xi + (b - rule.b))
268                .collect();
269
270            x_vec.extend(rule.x.iter().cloned());
271            w_vec.extend(rule.w.iter().cloned());
272            x_forward_vec.extend(x_forward_adj.iter().cloned());
273            x_backward_vec.extend(x_backward_adj.iter().cloned());
274        }
275
276        // Sort by x values to maintain order
277        let mut indices: Vec<usize> = (0..x_vec.len()).collect();
278        indices.sort_by(|&a, &b| x_vec[a].partial_cmp(&x_vec[b]).unwrap());
279
280        let sorted_x: Vec<T> = indices.iter().map(|&i| x_vec[i]).collect();
281        let sorted_w: Vec<T> = indices.iter().map(|&i| w_vec[i]).collect();
282
283        // Recalculate x_forward and x_backward after sorting
284        let sorted_x_forward: Vec<T> = sorted_x.iter().map(|&xi| xi - a).collect();
285        let sorted_x_backward: Vec<T> = sorted_x.iter().map(|&xi| b - xi).collect();
286
287        Self {
288            x: sorted_x,
289            w: sorted_w,
290            x_forward: sorted_x_forward,
291            x_backward: sorted_x_backward,
292            a,
293            b,
294        }
295    }
296
297    /// Convert the rule to a different numeric type.
298    pub fn convert<U>(&self) -> Rule<U>
299    where
300        U: CustomNumeric + Copy + Debug + std::fmt::Display,
301    {
302        let x: Vec<U> = self
303            .x
304            .iter()
305            .map(|&xi| <U as CustomNumeric>::from_f64_unchecked(xi.to_f64()))
306            .collect();
307        let w: Vec<U> = self
308            .w
309            .iter()
310            .map(|&wi| <U as CustomNumeric>::from_f64_unchecked(wi.to_f64()))
311            .collect();
312        let x_forward: Vec<U> = self
313            .x_forward
314            .iter()
315            .map(|&xi| <U as CustomNumeric>::from_f64_unchecked(xi.to_f64()))
316            .collect();
317        let x_backward: Vec<U> = self
318            .x_backward
319            .iter()
320            .map(|&xi| <U as CustomNumeric>::from_f64_unchecked(xi.to_f64()))
321            .collect();
322        let a = <U as CustomNumeric>::from_f64_unchecked(self.a.to_f64());
323        let b = <U as CustomNumeric>::from_f64_unchecked(self.b.to_f64());
324
325        Rule {
326            x,
327            w,
328            x_forward,
329            x_backward,
330            a,
331            b,
332        }
333    }
334
335    /// Validate the rule for consistency.
336    ///
337    /// # Returns
338    /// `true` if the rule is valid, `false` otherwise.
339    pub fn validate(&self) -> bool {
340        // Check interval validity
341        if self.a >= self.b {
342            return false;
343        }
344
345        // Check array lengths
346        if self.x.len() != self.w.len() {
347            return false;
348        }
349
350        if self.x.len() != self.x_forward.len() || self.x.len() != self.x_backward.len() {
351            return false;
352        }
353
354        // Check that all points are within [a, b]
355        for &xi in self.x.iter() {
356            if xi < self.a || xi > self.b {
357                return false;
358            }
359        }
360
361        // Check that points are sorted
362        for i in 1..self.x.len() {
363            if self.x[i] <= self.x[i - 1] {
364                return false;
365            }
366        }
367
368        // Check x_forward and x_backward consistency
369        for i in 0..self.x.len() {
370            let expected_forward = self.x[i] - self.a;
371            let expected_backward = self.b - self.x[i];
372
373            if (self.x_forward[i] - expected_forward).abs() > T::epsilon() {
374                return false;
375            }
376            if (self.x_backward[i] - expected_backward).abs() > T::epsilon() {
377                return false;
378            }
379        }
380
381        true
382    }
383}
384
385/// Compute Gauss-Legendre quadrature nodes and weights using Newton's method.
386fn gauss_legendre_nodes_weights<T>(n: usize) -> (Vec<T>, Vec<T>)
387where
388    T: CustomNumeric + Copy + Debug + std::fmt::Display + 'static,
389{
390    if n == 0 {
391        return (Vec::new(), Vec::new());
392    }
393
394    if n == 1 {
395        return (
396            vec![<T as CustomNumeric>::from_f64_unchecked(0.0)],
397            vec![<T as CustomNumeric>::from_f64_unchecked(2.0)],
398        );
399    }
400
401    let mut x = Vec::with_capacity(n);
402    let mut w = Vec::with_capacity(n);
403
404    // Use Newton's method to find roots of Legendre polynomial
405    let m = n.div_ceil(2);
406
407    // Use high-precision constants via CustomNumeric trait
408    let pi = T::pi();
409
410    for i in 0..m {
411        // Convert integers directly to avoid f64 intermediate
412        let i_val = <T as CustomNumeric>::from_f64_unchecked(i as f64);
413        let n_val = <T as CustomNumeric>::from_f64_unchecked(n as f64);
414        let three_quarters = <T as CustomNumeric>::from_f64_unchecked(0.75);
415        let half = <T as CustomNumeric>::from_f64_unchecked(0.5);
416
417        // Initial guess using Chebyshev nodes
418        let mut z = (pi * (i_val + three_quarters) / (n_val + half)).cos();
419
420        // Newton's method to refine the root
421        for _ in 0..10 {
422            let (p0, p1) = legendre_polynomial_and_derivative(n, z);
423            if p0.abs() < T::epsilon() {
424                break;
425            }
426            z = z - p0 / p1;
427        }
428
429        // Compute weight using high-precision constants
430        let two = <T as CustomNumeric>::from_f64_unchecked(2.0);
431        let one = <T as CustomNumeric>::from_f64_unchecked(1.0);
432        let (_, p1) = legendre_polynomial_and_derivative(n, z);
433        let weight = two / ((one - z * z) * p1 * p1);
434
435        x.push(-z);
436        w.push(weight);
437
438        if i != n - 1 - i {
439            x.push(z);
440            w.push(weight);
441        }
442    }
443
444    // Sort by x values
445    let mut indices: Vec<usize> = (0..n).collect();
446    indices.sort_by(|&a, &b| x[a].partial_cmp(&x[b]).unwrap());
447
448    let sorted_x: Vec<T> = indices.iter().map(|&i| x[i]).collect();
449    let sorted_w: Vec<T> = indices.iter().map(|&i| w[i]).collect();
450
451    (sorted_x, sorted_w)
452}
453
454/// Compute Legendre polynomial P_n(x) and its derivative using recurrence relation.
455fn legendre_polynomial_and_derivative<T>(n: usize, x: T) -> (T, T)
456where
457    T: CustomNumeric + Copy + Debug + std::fmt::Display + 'static,
458{
459    if n == 0 {
460        return (
461            <T as CustomNumeric>::from_f64_unchecked(1.0),
462            <T as CustomNumeric>::from_f64_unchecked(0.0),
463        );
464    }
465
466    if n == 1 {
467        return (x, <T as CustomNumeric>::from_f64_unchecked(1.0));
468    }
469
470    let mut p0 = <T as CustomNumeric>::from_f64_unchecked(1.0);
471    let mut p1 = x;
472    let mut dp0 = <T as CustomNumeric>::from_f64_unchecked(0.0);
473    let mut dp1 = <T as CustomNumeric>::from_f64_unchecked(1.0);
474
475    for k in 2..=n {
476        let k_f = <T as CustomNumeric>::from_f64_unchecked(k as f64);
477        let k1_f = <T as CustomNumeric>::from_f64_unchecked((k - 1) as f64);
478        let _k2_f = <T as CustomNumeric>::from_f64_unchecked((k - 2) as f64);
479
480        let p2 = ((<T as CustomNumeric>::from_f64_unchecked(2.0) * k1_f
481            + <T as CustomNumeric>::from_f64_unchecked(1.0))
482            * x
483            * p1
484            - k1_f * p0)
485            / k_f;
486        let dp2 = ((<T as CustomNumeric>::from_f64_unchecked(2.0) * k1_f
487            + <T as CustomNumeric>::from_f64_unchecked(1.0))
488            * (p1 + x * dp1)
489            - k1_f * dp0)
490            / k_f;
491
492        p0 = p1;
493        p1 = p2;
494        dp0 = dp1;
495        dp1 = dp2;
496    }
497
498    (p1, dp1)
499}
500
501/// The Gauss-Legendre rule with `n` points on [-1, 1], in `T`, by Newton's
502/// method on the Legendre polynomial
503///
504/// `n = 0` gives the empty rule on [-1, 1].
505pub fn legendre<T: CustomNumeric + 'static>(n: usize) -> Rule<T> {
506    if n == 0 {
507        return Rule::empty();
508    }
509
510    let (x, w) = gauss_legendre_nodes_weights(n);
511
512    Rule::new(
513        x,
514        w,
515        <T as CustomNumeric>::from_f64_unchecked(-1.0),
516        <T as CustomNumeric>::from_f64_unchecked(1.0),
517    )
518    .expect("the Gauss-Legendre nodes and weights have the same length")
519}
520
521/// The Gauss-Legendre rule the SVE discretizes with: [`legendre`] in `f64`,
522/// xprec's rule in `Df64`
523pub(crate) fn sve_legendre<T: CustomNumeric + 'static>(n: usize) -> Rule<T> {
524    let convert = |v: &[crate::Df64]| v.iter().map(|&x| T::convert_from(x)).collect();
525    let (x, w) = if std::any::TypeId::of::<T>() == std::any::TypeId::of::<f64>() {
526        let (x, w) = gauss_legendre_nodes_weights::<f64>(n);
527        (
528            x.into_iter().map(T::from_f64_unchecked).collect(),
529            w.into_iter().map(T::from_f64_unchecked).collect(),
530        )
531    } else {
532        let mut x = vec![crate::Df64::ZERO; n];
533        let mut w = vec![crate::Df64::ZERO; n];
534        if n > 0 {
535            xprec::gauss::gauss_legendre(&mut x, &mut w);
536        }
537        (convert(&x), convert(&w))
538    };
539    Rule::new(
540        x,
541        w,
542        T::from_f64_unchecked(-1.0),
543        T::from_f64_unchecked(1.0),
544    )
545    .expect("the Gauss-Legendre nodes and weights have the same length")
546}
547
548/// Create Legendre Vandermonde matrix for polynomial interpolation
549///
550/// # Arguments
551/// * `x` - Points where polynomials are evaluated
552/// * `degree` - Maximum degree of Legendre polynomials
553///
554/// # Returns
555/// Matrix V where V[i,j] = P_j(x_i), with P_j being the j-th Legendre polynomial
556pub fn legendre_vandermonde<T: CustomNumeric>(x: &[T], degree: usize) -> Mat<T> {
557    let n = x.len();
558    let mut v = Mat::<T>::from_elem([n, degree + 1], T::zero());
559
560    // First column is all ones (P_0(x) = 1)
561    for i in 0..n {
562        v[[i, 0]] = T::from_f64_unchecked(1.0);
563    }
564
565    // Second column is x (P_1(x) = x)
566    if degree > 0 {
567        for i in 0..n {
568            v[[i, 1]] = x[i];
569        }
570    }
571
572    // Recurrence relation: P_n(x) = ((2n-1)x*P_{n-1}(x) - (n-1)*P_{n-2}(x)) / n
573    for j in 2..=degree {
574        for i in 0..n {
575            let n_f64 = j as f64;
576            let term1 = T::from_f64_unchecked(2.0 * n_f64 - 1.0) * x[i] * v[[i, j - 1]];
577            let term2 = T::from_f64_unchecked(n_f64 - 1.0) * v[[i, j - 2]];
578            v[[i, j]] = (term1 - term2) / T::from_f64_unchecked(n_f64);
579        }
580    }
581
582    v
583}
584
585#[cfg(test)]
586#[path = "gauss_tests.rs"]
587mod tests;