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", so this trait is not object safe.

Implementors§