poly

ark-poly

This crate implements traits and implementations for polynomials, FFT-friendly subsets of a field (dubbed "domains"), and FFTs for these domains.

Polynomials

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.
• DenseUVPolynomial : Specifies that a Polynomial is actually a univariate polynomial.
• DenseMVPolynomial: 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 DenseUVPolynomial 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 DenseUVPolynomial 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).

Evaluations

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.

Domains

TODO