ark-poly 0.4.0-alpha

A library for efficient polynomial arithmetic via FFTs over finite fields
Documentation

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.

The evaluations module also provides the following traits for defining multivariate polynomials in lagrange form:

This crate provides some data structures to implement these traits.

Domains

TODO