Skip to main content

PolyTraits

sparse_interp

Trait PolyTraits 

Source 
pub trait PolyTraits {
    type Coeff;
    type SparseInterpEval: EvalTypes<Coeff = Self::Coeff>;
    type SparseInterpInfo;

    // Required methods
    fn slice_mul(
        out: &mut [Self::Coeff],
        lhs: &[Self::Coeff],
        rhs: &[Self::Coeff],
    );
    fn sparse_interp_prep(
        sparsity: usize,
        expons: impl Iterator<Item = usize>,
        max_coeff: &Self::Coeff,
    ) -> (<Self::SparseInterpEval as EvalTypes>::EvalInfo, Self::SparseInterpInfo);
    fn sparse_interp_slice(
        evals: &[<Self::SparseInterpEval as EvalTypes>::Eval],
        info: &Self::SparseInterpInfo,
    ) -> Result<Vec<(usize, Self::Coeff)>>;

    // Provided methods
    fn mp_eval_prep<U>(
        pts: impl Iterator<Item = U>,
    ) -> <EvalTrait<Self, U> as EvalTypes>::EvalInfo
       where EvalTrait<Self, U>: EvalTypes<Coeff = Self::Coeff, Eval = U> { ... }
    fn mp_eval_slice<U>(
        out: &mut impl Extend<U>,
        coeffs: &[Self::Coeff],
        info: &<EvalTrait<Self, U> as EvalTypes>::EvalInfo,
    ) -> Result<()>
       where EvalTrait<Self, U>: EvalTypes<Coeff = Self::Coeff, Eval = U> { ... }
}
Expand description

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.

Required Associated Types§

Source

type Coeff

The type of polynomial coefficients.

Source

type SparseInterpEval: EvalTypes<Coeff = Self::Coeff>

The evaluation needed for sparse interpolation.

Source

type SparseInterpInfo

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

Required Methods§

Source

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

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.]);
Source

fn sparse_interp_prep( sparsity: usize, expons: impl Iterator<Item = usize>, max_coeff: &Self::Coeff, ) -> (<Self::SparseInterpEval as EvalTypes>::EvalInfo, Self::SparseInterpInfo)

Pre-processing for sparse interpolation.

This method must be called prior to calling Self::sparse_interp_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
  • The coefficients of f are bounded by max_coeff in magnitude.

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.

Source

fn sparse_interp_slice( evals: &[<Self::SparseInterpEval as EvalTypes>::Eval], info: &Self::SparseInterpInfo, ) -> Result<Vec<(usize, Self::Coeff)>>

Sparse interpolation following evaluation.

The evaluations in eval should correspond to what was specified by Self::sparse_interp_prep().

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.

Provided Methods§

Source

fn mp_eval_prep<U>( pts: impl Iterator<Item = U>, ) -> <EvalTrait<Self, U> as EvalTypes>::EvalInfo
where EvalTrait<Self, U>: EvalTypes<Coeff = Self::Coeff, Eval = U>,

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.

The default implementation should be used; it relies on the EvalTypes::prep() trait method specialized for the coefficient and evaluation types.

Source

fn mp_eval_slice<U>( out: &mut impl Extend<U>, coeffs: &[Self::Coeff], info: &<EvalTrait<Self, U> as EvalTypes>::EvalInfo, ) -> Result<()>
where EvalTrait<Self, U>: EvalTypes<Coeff = Self::Coeff, Eval = U>,

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().copied());

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.]);

The provided implementation should generally be used; it relies on the EvalTypes::post() trait method specialized for the coefficient and evaluation types.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§