Trait sparse_interp::PolyTraits[−][src]

pub trait PolyTraits {
    type Coeff;
    type SparseInterpEval: EvalTypes<Coeff = Self::Coeff>;
    type SparseInterpInfo;
    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)>>;

    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>,
    { ... }
}

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 SparseInterpEval: EvalTypes<Coeff = Self::Coeff>[src]

The evaluation needed for sparse interpolation.

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 sparse_interp_prep(
    sparsity: usize,
    expons: impl Iterator<Item = usize>,
    max_coeff: &Self::Coeff
) -> (<Self::SparseInterpEval as EvalTypes>::EvalInfo, Self::SparseInterpInfo)[src]

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.

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

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.

Loading content...

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>, [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.

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

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>, [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().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.

Loading content...

Implementors

impl<C> PolyTraits for ClassicalTraits<C> where
    C: Clone + Mul<Output = C> + AddAssign,
    DefConv<C, Complex64>: TwoWay<Source = C, Dest = Complex64>, [src]

type Coeff = C

type SparseInterpEval = EvalTrait<Self, Complex64>

type SparseInterpInfo = (usize, Vec<(usize, Complex64)>, RelativeParams<Complex64, f64>)

Loading content...