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.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).
rust
use ark_poly::{
polynomial::multivariate::{SparsePolynomial, SparseTerm, Term},
DenseMVPolynomial, Polynomial,
};
use ark_test_curves::bls12_381::Fq;
// Create a multivariate polynomial in 3 variables, with 4 terms:
// f(x_0, x_1, x_2) = 2*x_0^3 + x_0*x_2 + x_1*x_2 + 5
let poly = SparsePolynomial::from_coefficients_vec(
3,
vec![
(Fq::from(2), SparseTerm::new(vec![(0, 3)])),
(Fq::from(1), SparseTerm::new(vec![(0, 1), (2, 1)])),
(Fq::from(1), SparseTerm::new(vec![(1, 1), (2, 1)])),
(Fq::from(5), SparseTerm::new(vec![])),
],
);
assert_eq!(poly.evaluate(&vec![Fq::from(2), Fq::from(3), Fq::from(6)]), Fq::from(51));
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.
```rust use arktestcurves::bls12381::Fq; use arkpoly::{DenseMultilinearExtension, MultilinearExtension, SparseMultilinearExtension}; use arkpoly::{ polynomial::multivariate::{SparsePolynomial, SparseTerm, Term}, DenseMVPolynomial, Polynomial, }; use arkstd::One;
// Create a multivariate polynomial in 3 variables:
// f(x0, x1, x2) = 2*x0^3 + x0*x2 + x1*x2
let f = SparsePolynomial::fromcoefficientsvec(
3,
vec![
(Fq::from(2), SparseTerm::new(vec![(0, 3)])),
(Fq::from(1), SparseTerm::new(vec![(0, 1), (2, 1)])),
(Fq::from(1), SparseTerm::new(vec![(1, 1), (2, 1)])),
(Fq::from(0), SparseTerm::new(vec![])),
],
);
// g is the multilinear extension of f, defined by the evaluations of f on the Boolean hypercube:
// f(0, 0, 0) = 20^3 + 00 + 00 = 0
// f(1, 0, 0) = 21^3 + 00 + 00 = 2
// ...
// f(1, 1, 1) = 21^3 + 11 + 1*1 = 4
let g: DenseMultilinearExtension
// We can also define a MLE g'(x0, x1, x2) by providing the list of non-zero evaluations:
let gprime: SparseMultilinearExtension
```
TODO