Enum GeneralEvaluationDomain

pub enum GeneralEvaluationDomain<F: FftField> {
    Radix2(Radix2EvaluationDomain<F>),
    MixedRadix(MixedRadixEvaluationDomain<F>),
}

Defines a domain over which finite field (I)FFTs can be performed. Generally tries to build a radix-2 domain and falls back to a mixed-radix domain if the radix-2 multiplicative subgroup is too small.

Examples

use ark_poly::{GeneralEvaluationDomain, EvaluationDomain};
use ark_poly::{univariate::DensePolynomial, Polynomial, DenseUVPolynomial};
use ark_ff::FftField;

// The field we are using is FFT-friendly, with 2-adicity of 32.
// We can efficiently evaluate polynomials over this field on up to 2^32 points.
use ark_test_curves::bls12_381::Fr;

let small_domain = GeneralEvaluationDomain::<Fr>::new(4).unwrap();
let evals = vec![Fr::from(1u8), Fr::from(2u8), Fr::from(3u8), Fr::from(4u8)];
// From a vector of evaluations, we can recover the polynomial.
let coeffs = small_domain.ifft(&evals);
let poly = DensePolynomial::from_coefficients_vec(coeffs.clone());
assert_eq!(poly.degree(), 3);

// We could also evaluate this polynomial at a large number of points efficiently, e.g. for Reed-Solomon encoding.
let large_domain = GeneralEvaluationDomain::<Fr>::new(1<<10).unwrap();
let new_evals = large_domain.fft(&coeffs);

Variants

Radix2(Radix2EvaluationDomain<F>)

Radix-2 domain

MixedRadix(MixedRadixEvaluationDomain<F>)

Mixed-radix domain

Trait Implementations

impl<F: FftField> CanonicalDeserialize for GeneralEvaluationDomain<F>

fn deserialize_with_mode<R: Read>( reader: R, compress: Compress, validate: Validate, ) -> Result<Self, SerializationError>

The general deserialize method that takes in customization flags.

fn deserialize_compressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

fn deserialize_compressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

fn deserialize_uncompressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

fn deserialize_uncompressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

impl<F: FftField> CanonicalSerialize for GeneralEvaluationDomain<F>

fn serialize_with_mode<W: Write>( &self, writer: W, compress: Compress, ) -> Result<(), SerializationError>

The general serialize method that takes in customization flags.

fn serialized_size(&self, compress: Compress) -> usize

fn serialize_compressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

fn compressed_size(&self) -> usize

fn serialize_uncompressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

fn uncompressed_size(&self) -> usize

impl<F: Clone + FftField> Clone for GeneralEvaluationDomain<F>

fn clone(&self) -> GeneralEvaluationDomain<F>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug + FftField> Debug for GeneralEvaluationDomain<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: FftField> EvaluationDomain<F> for GeneralEvaluationDomain<F>

fn new(num_coeffs: usize) -> Option<Self>

Construct a domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

If the field specifies a small subgroup for a mixed-radix FFT and the radix-2 FFT cannot be constructed, this method tries constructing a mixed-radix FFT instead.

fn elements(&self) -> GeneralElements<F>

Return an iterator over the elements of the domain.

type Elements = GeneralElements<F>

The type of the elements iterator.

fn get_coset(&self, offset: F) -> Option<Self>

Construct a coset domain from a subgroup domain

fn compute_size_of_domain(num_coeffs: usize) -> Option<usize>

Return the size of a domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

fn size(&self) -> usize

Return the size of self.

fn log_size_of_group(&self) -> u64

Return log_2(size) of self.

fn size_inv(&self) -> F

Return the inverse of self.size_as_field_element().

fn group_gen(&self) -> F

Return the generator for the multiplicative subgroup that defines this domain.

fn group_gen_inv(&self) -> F

Return the group inverse of self.group_gen().

fn coset_offset(&self) -> F

Return the group offset that defines this domain.

fn coset_offset_inv(&self) -> F

Return the inverse of self.offset().

fn coset_offset_pow_size(&self) -> F

Return offset^size.

fn fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)

Compute a FFT, modifying the vector in place.

fn ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)

Compute a IFFT, modifying the vector in place.

fn evaluate_all_lagrange_coefficients(&self, tau: F) -> Vec<F>

Evaluate all the lagrange polynomials defined by this domain at the point tau. This is computed in time O(|domain|). Then given the evaluations of a degree d polynomial P over this domain, where d < |domain|, P(tau) can be computed as P(tau) = sum_{i in [|Domain|]} L_{i, Domain}(tau) * P(g^i). L_{i, Domain} is the value of the i-th lagrange coefficient in the returned vector.

fn vanishing_polynomial(&self) -> SparsePolynomial<F>

Return the sparse vanishing polynomial.

fn evaluate_vanishing_polynomial(&self, tau: F) -> F

This evaluates the vanishing polynomial for this domain at tau.

fn sample_element_outside_domain<R: Rng>(&self, rng: &mut R) -> F

Sample an element that is not in the domain.

fn new_coset(num_coeffs: usize, offset: F) -> Option<Self>

Construct a coset domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

fn size_as_field_element(&self) -> F

Return the size of self as a field element.

fn fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>

Compute a FFT.

fn ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>

Compute a IFFT.

fn distribute_powers<T: DomainCoeff<F>>(coeffs: &mut [T], g: F)

Multiply the i-th element of coeffs with g^i.

fn distribute_powers_and_mul_by_const<T: DomainCoeff<F>>( coeffs: &mut [T], g: F, c: F, )

Multiply the i-th element of coeffs with c*g^i.

fn filter_polynomial(&self, subdomain: &Self) -> DensePolynomial<F>

Return the filter polynomial of self with respect to the subdomain subdomain. Assumes that subdomain is contained within self.

fn evaluate_filter_polynomial(&self, subdomain: &Self, tau: F) -> F

This evaluates at tau the filter polynomial for self with respect to the subdomain subdomain.

fn element(&self, i: usize) -> F

Returns the i-th element of the domain.

fn reindex_by_subdomain(&self, other: Self, index: usize) -> usize

Given an index which assumes the first elements of this domain are the elements of another (sub)domain, this returns the actual index into this domain.

fn mul_polynomials_in_evaluation_domain( &self, self_evals: &[F], other_evals: &[F], ) -> Vec<F>

Perform O(n) multiplication of two polynomials that are presented by their evaluations in the domain. Returns the evaluations of the product over the domain.

impl<F: Hash + FftField> Hash for GeneralEvaluationDomain<F>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<F: PartialEq + FftField> PartialEq for GeneralEvaluationDomain<F>

fn eq(&self, other: &GeneralEvaluationDomain<F>) -> 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<F: FftField> Valid for GeneralEvaluationDomain<F>

fn check(&self) -> Result<(), SerializationError>

fn batch_check<'a>( batch: impl Iterator<Item = &'a Self> + Send, ) -> Result<(), SerializationError>

where Self: 'a,

impl<F: Copy + FftField> Copy for GeneralEvaluationDomain<F>

impl<F: Eq + FftField> Eq for GeneralEvaluationDomain<F>

impl<F: FftField> StructuralPartialEq for GeneralEvaluationDomain<F>