Struct EvaluationDomain

pub struct EvaluationDomain<F: Field> { /* private fields */ }

This structure contains precomputed constants and other details needed for performing operations on an evaluation domain of size $2^k$ and an extended domain of size $2^{k} * j$ with $j \neq 0$.

Implementations

impl<F: WithSmallOrderMulGroup<3>> EvaluationDomain<F>

pub fn new(j: u32, k: u32) -> Self

This constructs a new evaluation domain object based on the provided values $j, k$.

pub fn lagrange_from_vec(&self, values: Vec<F>) -> Polynomial<F, LagrangeCoeff>

Obtains a polynomial in Lagrange form when given a vector of Lagrange coefficients of size n; panics if the provided vector is the wrong length.

pub fn lagrange_assigned_from_vec( &self, values: Vec<Assigned<F>>, ) -> Polynomial<Assigned<F>, LagrangeCoeff>

pub fn coeff_from_vec(&self, values: Vec<F>) -> Polynomial<F, Coeff>

Obtains a polynomial in coefficient form when given a vector of coefficients of size n; panics if the provided vector is the wrong length.

pub fn lagrange_vec_to_extended( &self, values: Vec<Polynomial<F, LagrangeCoeff>>, ) -> Polynomial<F, ExtendedLagrangeCoeff>

Obtains a polynomial in ExtendedLagrange form when given a vector of Lagrange polynomials with total size extended_n; panics if the provided vector is the wrong length.

pub fn extended_from_lagrange_vec( &self, values: Vec<Polynomial<F, LagrangeCoeff>>, ) -> Polynomial<F, ExtendedLagrangeCoeff>

Obtains a polynomial in ExtendedLagrange form when given a vector of Lagrange polynomials with total size extended_n; panics if the provided vector is the wrong length.

pub fn empty_coeff(&self) -> Polynomial<F, Coeff>

Returns an empty (zero) polynomial in the coefficient basis

pub fn empty_lagrange(&self) -> Polynomial<F, LagrangeCoeff>

Returns an empty (zero) polynomial in the Lagrange coefficient basis

pub fn constant_lagrange(&self, scalar: F) -> Polynomial<F, LagrangeCoeff>

Returns a constant polynomial in the Lagrange coefficient basis

pub fn empty_extended(&self) -> Polynomial<F, ExtendedLagrangeCoeff>

Returns an empty (zero) polynomial in the extended Lagrange coefficient basis

pub fn constant_extended( &self, scalar: F, ) -> Polynomial<F, ExtendedLagrangeCoeff>

Returns a constant polynomial in the extended Lagrange coefficient basis

pub fn lagrange_to_coeff( &self, a: Polynomial<F, LagrangeCoeff>, ) -> Polynomial<F, Coeff>

This takes us from an n-length vector into the coefficient form.

This function will panic if the provided vector is not the correct length.

pub fn coeff_to_extended( &self, p: &Polynomial<F, Coeff>, ) -> Polynomial<F, ExtendedLagrangeCoeff>

This takes us from an n-length coefficient vector into a coset of the extended evaluation domain, rotating by rotation if desired.

pub fn coeff_to_extended_parts( &self, a: &Polynomial<F, Coeff>, ) -> Vec<Polynomial<F, LagrangeCoeff>>

This takes us from an n-length coefficient vector into parts of the extended evaluation domain. For example, for a polynomial with size n, and an extended domain of size mn, we can compute all parts independently, which are FFT(f(zeta * X), n) FFT(f(zeta * extended_omega * X), n) … FFT(f(zeta * extended_omega^{m-1} * X), n)

pub fn batched_coeff_to_extended_parts( &self, a: &[Polynomial<F, Coeff>], ) -> Vec<Vec<Polynomial<F, LagrangeCoeff>>>

This takes us from several n-length coefficient vectors each into parts of the extended evaluation domain. For example, for a polynomial with size n, and an extended domain of size mn, we can compute all parts independently, which are FFT(f(zeta * X), n) FFT(f(zeta * extended_omega * X), n) … FFT(f(zeta * extended_omega^{m-1} * X), n)

pub fn coeff_to_extended_part( &self, a: Polynomial<F, Coeff>, extended_omega_factor: F, ) -> Polynomial<F, LagrangeCoeff>

This takes us from an n-length coefficient vector into a part of the extended evaluation domain. For example, for a polynomial with size n, and an extended domain of size mn, we can compute one of the m parts separately, which is FFT(f(zeta * extended_omega_factor * X), n) where extended_omega_factor is extended_omega^i with i in [0, m).

pub fn rotate_extended( &self, poly: &Polynomial<F, ExtendedLagrangeCoeff>, rotation: Rotation, ) -> Polynomial<F, ExtendedLagrangeCoeff>

Rotate the extended domain polynomial over the original domain.

pub fn extended_to_coeff( &self, a: Polynomial<F, ExtendedLagrangeCoeff>, ) -> Vec<F>

This takes us from the extended evaluation domain and gets us the quotient polynomial coefficients.

This function will panic if the provided vector is not the correct length.

pub fn lagrange_vecs_to_extended( &self, a: Vec<Vec<Polynomial<F, LagrangeCoeff>>>, ) -> Polynomial<F, ExtendedLagrangeCoeff>

This takes us from the a list of lagrange-based polynomials with different degrees and gets their extended lagrange-based summation.

pub fn divide_by_vanishing_poly( &self, a: Polynomial<F, ExtendedLagrangeCoeff>, ) -> Polynomial<F, ExtendedLagrangeCoeff>

This divides the polynomial (in the extended domain) by the vanishing polynomial of the $2^k$ size domain.

pub fn k(&self) -> u32

Get the size of the domain

pub fn extended_k(&self) -> u32

Get the size of the extended domain

pub fn extended_len(&self) -> usize

Get the size of the extended domain

pub fn get_omega(&self) -> F

Get $\omega$, the generator of the $2^k$ order multiplicative subgroup.

pub fn get_omega_inv(&self) -> F

Get $\omega^{-1}$, the inverse of the generator of the $2^k$ order multiplicative subgroup.

pub fn get_extended_omega(&self) -> F

Get the generator of the extended domain’s multiplicative subgroup.

pub fn rotate_omega(&self, value: F, rotation: Rotation) -> F

Multiplies a value by some power of $\omega$, essentially rotating over the domain.

pub fn l_i_range<I: IntoIterator<Item = i32> + Clone>( &self, x: F, xn: F, rotations: I, ) -> Vec<F>

Computes evaluations (at the point x, where xn = x^n) of Lagrange basis polynomials l_i(X) defined such that l_i(omega^i) = 1 and l_i(omega^j) = 0 for all j != i at each provided rotation i.

Implementation

The polynomial $$\prod_{j=0,j \neq i}^{n - 1} (X - \omega^j)$$ has a root at all points in the domain except $\omega^i$, where it evaluates to $$\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)$$ and so we divide that polynomial by this value to obtain $l_i(X)$. Since $$\prod_{j=0,j \neq i}^{n - 1} (X - \omega^j) = \frac{X^n - 1}{X - \omega^i}$$ then $l_i(x)$ for some $x$ is evaluated as $$\left(\frac{x^n - 1}{x - \omega^i}\right) \cdot \left(\frac{1}{\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)}\right).$$ We refer to $$1 \over \prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)$$ as the barycentric weight of $\omega^i$.

We know that for $i = 0$ $$\frac{1}{\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)} = \frac{1}{n}.$$

If we multiply $(1 / n)$ by $\omega^i$ then we obtain $$\frac{1}{\prod_{j=0,j \neq 0}^{n - 1} (\omega^i - \omega^j)} = \frac{1}{\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)}$$ which is the barycentric weight of $\omega^i$.

pub fn get_quotient_poly_degree(&self) -> usize

Gets the quotient polynomial’s degree (as a multiple of n)

pub fn pinned(&self) -> PinnedEvaluationDomain<'_, F>

Obtain a pinned version of this evaluation domain; a structure with the minimal parameters needed to determine the rest of the evaluation domain.

pub fn get_n(&self) -> u64

Get the private field n

pub fn get_fft_data(&self, l: usize) -> &FFTData<F>

Get the private fft_data

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<F: Debug + Field> Debug for EvaluationDomain<F>

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

Formats the value using the given formatter.