This crate implements traits and implementations for polynomials, FFT-friendly subsets of a field (dubbed "domains"), and FFTs for these domains.
The polynomial module provides the following traits for defining polynomials in coefficient form:
Polynomial:
Requires implementors to support common operations on polynomials,
such as Add, Sub, Zero, evaluation at a point, degree, etc,
and defines methods to serialize to and from the coefficient representation of the polynomial.UVPolynomial :
Specifies that a Polynomial is actually a univariate polynomial.MVPolynomial:
Specifies that a Polynomial is actually a multivariate polynomial.This crate also provides the following data structures that implement these traits:
univariate/DensePolynomial:
Represents degree d univariate polynomials via a list of d + 1 coefficients.
This struct implements the UVPolynomial trait.univariate/SparsePolynomial:
Represents degree d univariate polynomials via a list containing all non-zero monomials.
This should only be used when most coefficients of the polynomial are zero.
This struct implements the Polynomial trait
(but not the UVPolynomial trait).multivariate/SparsePolynomial:
Represents multivariate polynomials via a list containing all non-zero monomials.This crate also provides the univariate/DenseOrSparsePolynomial enum, which allows the user to abstract over the type of underlying univariate polynomial (dense or sparse).
The evaluations module provides data structures to represent univariate polynomials in lagrange form.
univariate/Evaluations
Represents a univariate polynomial in evaluation form, which can be used for FFT.The evaluations module also provides the following traits for defining multivariate polynomials in lagrange form:
multivariate/multilinear/MultilinearExtension
Specifies a multilinear polynomial evaluated over boolean hypercube.This crate provides some data structures to implement these traits.
multivariate/multilinear/DenseMultilinearExtension
Represents multilinear extension via a list of evaluations over boolean hypercube.
multivariate/multilinear/SparseMultilinearExtension
Represents multilinear extension via a list of non-zero evaluations over boolean hypercube.
TODO