Struct halo2_backend::poly::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 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 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, a: 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 lagrange_extended( &self, idx: usize ) -> Polynomial<F, ExtendedLagrangeCoeff>

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

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.