Trait sparse_interp::PolyTraits[−][src]

pub trait PolyTraits {
    type Coeff;
    type EvalInfo;
    type SparseInterpInfo;
    fn slice_mul(
        out: &mut [Self::Coeff], 
        lhs: &[Self::Coeff], 
        rhs: &[Self::Coeff]
    );

    fn mp_eval_prep<'a>(
        pts: impl Iterator<Item = &'a Self::Coeff>
    ) -> Self::EvalInfo
    where
        Self::Coeff: 'a;

    fn mp_eval_slice(
        out: &mut impl Extend<Self::Coeff>, 
        coeffs: &[Self::Coeff], 
        info: &Self::EvalInfo
    );

    fn sparse_interp_prep(
        theta: &Self::Coeff, 
        sparsity: usize, 
        expons: impl Iterator<Item = usize>
    ) -> Self::SparseInterpInfo;

    fn sparse_interp_slice(
        evals: &[Self::Coeff], 
        info: &Self::SparseInterpInfo, 
        close: &impl CloseTo<Item = Self::Coeff>
    ) -> Option<Vec<(usize, Self::Coeff)>>;
}

Algorithms to enable polynomial arithmetic.

Generally, PolyTraits methods should not be used directly, but only within the various method impls for Poly.

This is implemented as a separate, possibly stateless traits object in order to allow selecting different underlying algorithms separately from the overall representation.

The methods here generally work on slice references so as to be representation-agnostic.

So far the only implementation is ClassicalTraits.

Associated Types

type Coeff[src]

The type of polynomial coefficients.

type EvalInfo[src]

An opaque type returned by the pre-processing method Self::mp_eval_prep().

type SparseInterpInfo[src]

An opaque type returned by the pre-processing method Self::sparse_interp_prep().

Loading content...

Required methods

fn slice_mul(out: &mut [Self::Coeff], lhs: &[Self::Coeff], rhs: &[Self::Coeff])[src]

Multiplies two polynomails (represented by slices) and stores the result in another slice.

Implementations may assume that all slices are non-empty, and that out.len() == lhs.len() + rhs.len() - 1.

let a = [1., 2., 3.];
let b = [4., 5.];
let mut c = [0.; 4];
TraitImpl::slice_mul(&mut c[..], &a[..], &b[..]);
assert_eq!(c, [1.*4., 1.*5. + 2.*4., 2.*5. + 3.*4., 3.*5.]);

fn mp_eval_prep<'a>(
    pts: impl Iterator<Item = &'a Self::Coeff>
) -> Self::EvalInfo where
    Self::Coeff: 'a, [src]

Pre-processing for multi-point evaluation.

This method must be called to specify the evaluation points prior to calling Self::mp_eval_slice().

The same pre-processed output can be used repeatedly to evaluate possibly different polynomials at the same points.

fn mp_eval_slice(
    out: &mut impl Extend<Self::Coeff>,
    coeffs: &[Self::Coeff],
    info: &Self::EvalInfo
)[src]

Multi-point evaluation.

Evaluates the polynomial (given by a slice of coefficients) at all points specified in a previous call to Self::mp_eval_prep().

let pts = [10., -5.];
let preprocess = TraitImpl::mp_eval_prep(pts.iter());

let f = [1., 2., 3.];
let mut evals = Vec::new();
TraitImpl::mp_eval_slice(&mut evals, &f[..], &preprocess);
assert_eq!(evals, vec![321., 66.]);

let g = [4., 5., 6., 7.];
TraitImpl::mp_eval_slice(&mut evals, &g[..], &preprocess);
assert_eq!(evals, vec![321., 66., 7654., 4. - 5.*5. + 6.*25. - 7.*125.]);

fn sparse_interp_prep(
    theta: &Self::Coeff,
    sparsity: usize,
    expons: impl Iterator<Item = usize>
) -> Self::SparseInterpInfo[src]

Pre-processing for sparse interpolation.

This method must be called prior to calling Self::mp_eval_slice().

A later call to sparse interpolation is guaranteed to succeed only when, for some unknown polynomial f, the following are all true:

  • f has at most sparsity non-zero terms
  • The exponents of all non-zero terms of f appear in expons
  • f is evaluated at points pow(theta, i) for all i in [0..2*sparsity].

The list expons must be sorted in ascending order.

The same pre-processed output can be used repeatedly to interpolate possibly different polynomials under the same settings.

fn sparse_interp_slice(
    evals: &[Self::Coeff],
    info: &Self::SparseInterpInfo,
    close: &impl CloseTo<Item = Self::Coeff>
) -> Option<Vec<(usize, Self::Coeff)>>[src]

Sparse interpolation from special evaluation points.

The points in eval should correspond to the requirements in Self::sparse_interp_prep().

In addition the provided CloseTo impl works for the underlying sparse interpolation algorithm. For exact fields, CloseToEq should always work. For inexact fields such as f64, RelativeParams should work, but some understanding of the trait’s sparse interpolation algorithm may be required to ensure accuracy.

If those requirements are met, the function will return Some(..) containing a list of exponent-coefficient pairs, sorted in ascending order of exponents.

Otherwise, for example if the evaluated function has more non-zero terms than the pre-specified limit, this function may return None or may return Some(..) with incorrect values.

let f :[f32; 8] = [0., 0., -18.5, 0., 0., 0., 0., 31.7];
let theta: f32 = 2.1;
let eval_pts :Vec<_> = (0..4).map(|d| theta.powi(d)).collect();
let evals :Vec<_> = eval_pts.iter().map(|x| f[2] * x.powi(2) + f[7] * x.powi(7)).collect();
let close_check = RelativeParams::<f32>::new(Some(0.1), Some(0.1));

let sp_info = TraitImpl::sparse_interp_prep(&theta, 2, 0..10);
let sp_result = TraitImpl::sparse_interp_slice(&evals, &sp_info, &close_check).unwrap();
assert_eq!(sp_result.len(), 2);
assert_eq!(sp_result[0].0, 2);
assert!(close_check.close_to(&sp_result[0].1, &f[2]));
assert_eq!(sp_result[1].0, 7);
assert!(close_check.close_to(&sp_result[1].1, &f[7]));
Loading content...

Implementors

impl<C> PolyTraits for ClassicalTraits<C> where
    C: Clone + Zero + One + Neg<Output = C> + AddAssign + SubAssign + for<'a> MulAssign<&'a C> + for<'a> AddAssign<&'a C>,
    &'a C: Mul<Output = C> + Inv<Output = C>, [src]

type Coeff = C

type EvalInfo = Vec<C>

type SparseInterpInfo = (usize, Vec<(usize, C)>)

Loading content...