Struct Poly

pub struct Poly<T, U> { /* private fields */ }

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 + AddAssign + MulAssign,

pub fn eval<V>(&self, x: &V) -> Result<V>

where DefConv<U::Coeff, V>: OneWay<Source = U::Coeff, Dest = V>, V: Clone + Zero + AddAssign + MulAssign,

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<V>( pts: impl Iterator<Item = V>, ) -> <EvalTrait<U, V> as EvalTypes>::EvalInfo

where EvalTrait<U, V>: EvalTypes<Coeff = U::Coeff, Eval = V>,

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<V>( &self, info: &<EvalTrait<U, V> as EvalTypes>::EvalInfo, ) -> Result<Vec<V>>

where EvalTrait<U, V>: EvalTypes<Coeff = U::Coeff, Eval = V>,

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

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

impl<T, U> Poly<T, U>

where U: PolyTraits,

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

Perform pre-processing for sparse interpolation.

• 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.
• max_coeff is an upper bound on the magnitude of any coefficient.

See PolyTraits::sparse_interp_prep() for more details.

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

Perform sparse interpolation after evaluation.

Beforehand, Self::sparse_interp_prep() must be called to generate two info structs for evaluation and interpolation. These can be used repeatedly to evaluate and interpolate many polynomials with the same sparsity and degree bounds.

• evals should correspond evaluations according to the EvalInfo struct returned from preprocessing. at consecutive powers of the theta used in preprocessing.
• info should come from a previous call to Self::sparse_interp_prep().

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

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> + Clone + Zero,

type Output = Poly<Vec<<U as PolyTraits>::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 as PolyTraits>::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> 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 as PolyTraits>::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

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, U> Eq for Poly<T, U>

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