Struct sparse_interp::Poly

#[repr(transparent)]pub struct Poly<T, U> { /* fields omitted */ }

Generic struct to hold a polynomial and traits for operations.

The idea here is to combine some representation of the polynomial (say, a vector of coefficients) with an implementation of PolyTraits, to allow implementing all the standard arithmetic and other user-facing polynomial operations.

let f = ClassicalPoly::<f64>::new(vec![1., 2., 3.]);
let g = ClassicalPoly::<f64>::new(vec![4., 5.]);

assert_eq!(&f * &g, ClassicalPoly::new(vec![4., 13., 22., 15.]));
assert_eq!(&f + &g, ClassicalPoly::new(vec![5., 7., 3.]));

Type aliases are provided for various combinations that will work well. So far the only alias is ClassicalPoly.

Implementations

impl<U> Poly<Vec<U::Coeff>, U> where
    U: PolyTraits,
    U::Coeff: Zero, 

pub fn new(rep: Vec<U::Coeff>) -> Self

Creates a new Poly from a vector of coefficients.

impl<T, U> Poly<T, U> where
    U: PolyTraits,
    T: Borrow<[U::Coeff]>,
    U::Coeff: Zero, 

pub fn new_norm(rep: T) -> Self

Creates a new Poly from the underlying representation which has nonzero leading coefficient.

Panics

Panics if rep if not empty and has a leading coefficient which is zero.

impl<T, U> Poly<T, U> where
    U: PolyTraits,
    T: Borrow<[U::Coeff]>,
    U::Coeff: Clone + Zero + for<'c> MulAssign<&'c U::Coeff> + for<'c> AddAssign<&'c U::Coeff>, 

pub fn eval(&self, x: &U::Coeff) -> U::Coeff

Evaluate this polynomial at the given point.

Uses Horner’s rule to perform the evaluation using exactly d multiplications and d additions, where d is the degree of self.

pub fn mp_eval_prep<'a>(pts: impl Iterator<Item = &'a U::Coeff>) -> U::EvalInfo where
    U::Coeff: 'a, 

Perform pre-processing for multi-point evaluation.

pts is an iterator over the desired evaluation points.

See PolyTraits::mp_eval_prep() for more details.

pub fn mp_eval_post(&self, info: &U::EvalInfo) -> Vec<U::Coeff>

Perform multi-point evaluation after pre-processing.

info should be the result of calling Self::mp_eval_prep().

pub fn mp_eval<'a>(
    &self,
    pts: impl Iterator<Item = &'a U::Coeff>
) -> Vec<U::Coeff> where
    U::Coeff: 'a, 

Evaluate this polynomial at all of the given points.

Performs multi-point evaluation using the underlying trait algorithms. In general, this can be much more efficient than repeatedly calling [self.eval()].

impl<T, U> Poly<T, U> where
    U: PolyTraits, 

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

Perform pre-processing for sparse interpolation.

• Evaluations will be at consecutive powers of theta.
• sparsity is an upper bound on the number of nonzero terms in the evaluated polynomial.
• expons is an iteration over the possible exponents which may appear in nonzero terms.

See PolyTraits::sparse_interp_prep() for more details.

pub fn sparse_interp_post(
    evals: &[U::Coeff],
    info: &U::SparseInterpInfo,
    close: &impl CloseTo<Item = U::Coeff>
) -> Option<Vec<(usize, U::Coeff)>>

Perform sparse interpolation after pre-processing.

• evals should correspond to evaluations of some unknown power at consecutive powers of the theta used in preprocessing.
• info should be the result of calling Self::sparse_interp_prep().
• The parameters for close depend on the underlying field and the trait’s interpolation algorithm.

On success, a vector of (exponent, nonzero coefficient) pairs is returned, sorted by increasing exponent values.

pub fn sparse_interp(
    theta: &U::Coeff,
    sparsity: usize,
    expons: impl Iterator<Item = usize>,
    evals: &[U::Coeff],
    close: &impl CloseTo<Item = U::Coeff>
) -> Option<Vec<(usize, U::Coeff)>>

Perform sparse interpolation.

• Evaluations will be at consecutive powers of theta.
• sparsity is an upper bound on the number of nonzero terms in the evaluated polynomial.
• expons is an iteration over the possible exponents which may appear in nonzero terms.
• evals should correspond to evaluations of some unknown power at consecutive powers of the theta used in preprocessing.
• The parameters for close depend on the underlying field and the trait’s interpolation algorithm.

On success, a vector of (exponent, nonzero coefficient) pairs is returned, sorted by increasing exponent values. #[inline(always)]

Trait Implementations

impl<'a, 'b, T, U, V, W> Add<&'b Poly<V, W>> for &'a Poly<T, U> where
    U: PolyTraits,
    W: PolyTraits,
    &'a T: IntoIterator<Item = &'a U::Coeff>,
    &'b V: IntoIterator<Item = &'b W::Coeff>,
    &'a U::Coeff: Add<&'b W::Coeff, Output = U::Coeff>,
    U::Coeff: AddAssign<&'b W::Coeff>,
    U::Coeff: Clone + Zero, 

type Output = Poly<Vec<U::Coeff>, U>

The resulting type after applying the + operator.

fn add(self, rhs: &'b Poly<V, W>) -> Self::Output

Performs the + operation.

impl<T, U, V, W> Add<Poly<V, W>> for Poly<T, U> where
    U: PolyTraits,
    W: PolyTraits,
    T: IntoIterator<Item = U::Coeff>,
    V: IntoIterator<Item = W::Coeff>,
    U::Coeff: Zero + From<W::Coeff> + Add<W::Coeff, Output = U::Coeff>, 

type Output = Poly<Vec<U::Coeff>, U>

The resulting type after applying the + operator.

fn add(self, rhs: Poly<V, W>) -> Self::Output

Performs the + operation.

impl<T: Debug, U: Debug> Debug for Poly<T, U>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, U> Default for Poly<T, U> where
    T: Default, 

fn default() -> Self

Returns the “default value” for a type.

impl<T, U> Eq for Poly<T, U> where
    U: PolyTraits,
    T: Borrow<[U::Coeff]>,
    U::Coeff: Eq, 

impl<T, U> FromIterator<<U as PolyTraits>::Coeff> for Poly<T, U> where
    U: PolyTraits,
    T: FromIterator<U::Coeff> + Borrow<[U::Coeff]>,
    U::Coeff: Zero, 

fn from_iter<V>(iter: V) -> Self where
    V: IntoIterator<Item = U::Coeff>, 

Creates a value from an iterator.

impl<'a, 'b, T, U, V> Mul<&'b Poly<V, U>> for &'a Poly<T, U> where
    U: PolyTraits,
    T: Borrow<[U::Coeff]>,
    V: Borrow<[U::Coeff]>,
    U::Coeff: Zero, 

type Output = Poly<Box<[U::Coeff]>, U>

The resulting type after applying the * operator.

fn mul(self, rhs: &'b Poly<V, U>) -> Self::Output

Performs the * operation.

impl<T, U, V, W> PartialEq<Poly<V, W>> for Poly<T, U> where
    U: PolyTraits,
    W: PolyTraits,
    T: Borrow<[U::Coeff]>,
    V: Borrow<[W::Coeff]>,
    U::Coeff: PartialEq<W::Coeff>, 

fn eq(&self, other: &Poly<V, W>) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.