Enum GeneralEvaluationDomain 

pub enum GeneralEvaluationDomain<F: Field> {
    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,

Reads Self from reader using the compressed form if applicable. Performs validation if applicable.

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

where R: Read,

Reads Self from reader using the compressed form if applicable, without validating the deserialized value.

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

where R: Read,

Reads Self from reader using the uncompressed form. Performs validation if applicable.

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

where R: Read,

Reads Self from reader using the uncompressed form, without validating the deserialized value.

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

Returns the size in bytes of the serialized version of self with the given compression mode.

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

where W: Write,

Serializes self into writer using the compressed form if applicable.

fn compressed_size(&self) -> usize

Returns the size in bytes of the compressed serialized version of self.

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

where W: Write,

Serializes self into writer using the uncompressed form.

fn uncompressed_size(&self) -> usize

Returns the size in bytes of the uncompressed serialized version of self.

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug + Field> 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 + Field> 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 + Field> 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>

Checks whether self is valid. If self is valid, returns Ok(()). Otherwise, returns an error describing the failure. This method is called by deserialize_with_mode if validate is Validate::Yes.

const TRIVIAL_CHECK: bool = false

Whether the check method is trivial (i.e. always returns Ok(())). If this is true, the batch_check method will skip all checks and return Ok(()). This should be set to true for types where check is trivial, e.g. integers, field elements, etc. This is false by default. This is primarily an optimization to skip unnecessary checks in batch_check.

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

where Self: 'a,

Checks whether all items in batch are valid. If all items are valid, returns Ok(()). Otherwise, returns an error describing the first failure.

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

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

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