Struct snarkvm_algorithms::fft::domain::EvaluationDomain

source ·

pub struct EvaluationDomain<F: FftField> {
    pub size: u64,
    pub log_size_of_group: u32,
    pub size_as_field_element: F,
    pub size_inv: F,
    pub group_gen: F,
    pub group_gen_inv: F,
    pub generator_inv: F,
}

Expand description

Defines a domain over which finite field (I)FFTs can be performed. Works only for fields that have a large multiplicative subgroup of size that is a power-of-2.

Fields§

§size: u64

The size of the domain.

§log_size_of_group: u32

log_2(self.size).

§size_as_field_element: F

Size of the domain as a field element.

§size_inv: F

Inverse of the size in the field.

§group_gen: F

A generator of the subgroup.

§group_gen_inv: F

Inverse of the generator of the subgroup.

§generator_inv: F

Inverse of the multiplicative generator of the finite field.

Implementations§

source §

impl<F: FftField> EvaluationDomain<F>

source

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

Sample an element that is not in the domain.

source

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

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

source

pub 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.

source

pub fn size(&self) -> usize

Return the size of self.

source

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

Compute an FFT.

source

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

Compute an FFT, modifying the vector in place.

source

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

Compute an IFFT.

source

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

Compute an IFFT, modifying the vector in place.

source

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

Compute an FFT over a coset of the domain.

source

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

Compute an FFT over a coset of the domain, modifying the input vector in place.

source

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

Compute an IFFT over a coset of the domain.

source

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

Compute an IFFT over a coset of the domain, modifying the input vector in place.

source

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

Evaluate all the lagrange polynomials defined by this domain at the point tau.

source

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

Return the sparse vanishing polynomial.

source

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

This evaluates the vanishing polynomial for this domain at tau. For multiplicative subgroups, this polynomial is z(X) = X^self.size - 1.

source

pub fn elements(&self) -> Elements<F> ⓘ

Return an iterator over the elements of the domain.

source

pub fn divide_by_vanishing_poly_on_coset_in_place(&self, evals: &mut [F])

The target polynomial is the zero polynomial in our evaluation domain, so we must perform division over a coset.

source

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

Given an index in the other subdomain, return an index into this domain self This assumes the other’s elements are also self’s first elements

source

pub fn mul_polynomials_in_evaluation_domain( &self, self_evals: Vec<F>, other_evals: &[F] ) -> Result<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.

source §