Struct halo2_proofs::poly::EvaluationDomain

source ·
pub struct EvaluationDomain<F>
where F: Field,
{ /* private fields */ }
Expand description

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§

source§

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

source

pub fn new(j: u32, k: u32) -> EvaluationDomain<F>

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

source

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.

source

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.

source

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

Returns an empty (zero) polynomial in the coefficient basis

source

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

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

source

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

Returns a constant polynomial in the Lagrange coefficient basis

source

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

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

source

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

Returns a constant polynomial in the extended Lagrange coefficient basis

source

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.

source

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.

source

pub fn lagrange_extended( &self, idx: usize ) -> Polynomial<F, ExtendedLagrangeCoeff>

source

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

Rotate the extended domain polynomial over the original domain.

source

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.

source

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.

source

pub fn k(&self) -> u32

Get the size of the domain

source

pub fn extended_k(&self) -> u32

Get the size of the extended domain

source

pub fn extended_len(&self) -> usize

Get the size of the extended domain

source

pub fn get_omega(&self) -> F

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

source

pub fn get_omega_inv(&self) -> F

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

source

pub fn get_extended_omega(&self) -> F

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

source

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

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

source

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

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

source

pub fn get_quotient_poly_degree(&self) -> usize

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

source

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§

source§

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

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<F> Freeze for EvaluationDomain<F>
where F: Freeze,

§

impl<F> RefUnwindSafe for EvaluationDomain<F>
where F: RefUnwindSafe,

§

impl<F> Send for EvaluationDomain<F>

§

impl<F> Sync for EvaluationDomain<F>

§

impl<F> Unpin for EvaluationDomain<F>
where F: Unpin,

§

impl<F> UnwindSafe for EvaluationDomain<F>
where F: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
§

impl<T> Conv for T

§

fn conv<T>(self) -> T
where Self: Into<T>,

Converts self into T using Into<T>. Read more
§

impl<T> FmtForward for T

§

fn fmt_binary(self) -> FmtBinary<Self>
where Self: Binary,

Causes self to use its Binary implementation when Debug-formatted.
§

fn fmt_display(self) -> FmtDisplay<Self>
where Self: Display,

Causes self to use its Display implementation when Debug-formatted.
§

fn fmt_lower_exp(self) -> FmtLowerExp<Self>
where Self: LowerExp,

Causes self to use its LowerExp implementation when Debug-formatted.
§

fn fmt_lower_hex(self) -> FmtLowerHex<Self>
where Self: LowerHex,

Causes self to use its LowerHex implementation when Debug-formatted.
§

fn fmt_octal(self) -> FmtOctal<Self>
where Self: Octal,

Causes self to use its Octal implementation when Debug-formatted.
§

fn fmt_pointer(self) -> FmtPointer<Self>
where Self: Pointer,

Causes self to use its Pointer implementation when Debug-formatted.
§

fn fmt_upper_exp(self) -> FmtUpperExp<Self>
where Self: UpperExp,

Causes self to use its UpperExp implementation when Debug-formatted.
§

fn fmt_upper_hex(self) -> FmtUpperHex<Self>
where Self: UpperHex,

Causes self to use its UpperHex implementation when Debug-formatted.
§

fn fmt_list(self) -> FmtList<Self>
where &'a Self: for<'a> IntoIterator,

Formats each item in a sequence. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

§

impl<T> Instrument for T

§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided [Span], returning an Instrumented wrapper. Read more
§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> IntoEither for T

source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
§

impl<T> Pipe for T
where T: ?Sized,

§

fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> R
where Self: Sized,

Pipes by value. This is generally the method you want to use. Read more
§

fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> R
where R: 'a,

Borrows self and passes that borrow into the pipe function. Read more
§

fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> R
where R: 'a,

Mutably borrows self and passes that borrow into the pipe function. Read more
§

fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
where Self: Borrow<B>, B: 'a + ?Sized, R: 'a,

Borrows self, then passes self.borrow() into the pipe function. Read more
§

fn pipe_borrow_mut<'a, B, R>( &'a mut self, func: impl FnOnce(&'a mut B) -> R ) -> R
where Self: BorrowMut<B>, B: 'a + ?Sized, R: 'a,

Mutably borrows self, then passes self.borrow_mut() into the pipe function. Read more
§

fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
where Self: AsRef<U>, U: 'a + ?Sized, R: 'a,

Borrows self, then passes self.as_ref() into the pipe function.
§

fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
where Self: AsMut<U>, U: 'a + ?Sized, R: 'a,

Mutably borrows self, then passes self.as_mut() into the pipe function.
§

fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
where Self: Deref<Target = T>, T: 'a + ?Sized, R: 'a,

Borrows self, then passes self.deref() into the pipe function.
§

fn pipe_deref_mut<'a, T, R>( &'a mut self, func: impl FnOnce(&'a mut T) -> R ) -> R
where Self: DerefMut<Target = T> + Deref, T: 'a + ?Sized, R: 'a,

Mutably borrows self, then passes self.deref_mut() into the pipe function.
§

impl<T> Pointable for T

§

const ALIGN: usize = _

The alignment of pointer.
§

type Init = T

The type for initializers.
§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
source§

impl<T> Same for T

§

type Output = T

Should always be Self
§

impl<T> Tap for T

§

fn tap(self, func: impl FnOnce(&Self)) -> Self

Immutable access to a value. Read more
§

fn tap_mut(self, func: impl FnOnce(&mut Self)) -> Self

Mutable access to a value. Read more
§

fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
where Self: Borrow<B>, B: ?Sized,

Immutable access to the Borrow<B> of a value. Read more
§

fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
where Self: BorrowMut<B>, B: ?Sized,

Mutable access to the BorrowMut<B> of a value. Read more
§

fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
where Self: AsRef<R>, R: ?Sized,

Immutable access to the AsRef<R> view of a value. Read more
§

fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
where Self: AsMut<R>, R: ?Sized,

Mutable access to the AsMut<R> view of a value. Read more
§

fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
where Self: Deref<Target = T>, T: ?Sized,

Immutable access to the Deref::Target of a value. Read more
§

fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
where Self: DerefMut<Target = T> + Deref, T: ?Sized,

Mutable access to the Deref::Target of a value. Read more
§

fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self

Calls .tap() only in debug builds, and is erased in release builds.
§

fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self

Calls .tap_mut() only in debug builds, and is erased in release builds.
§

fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
where Self: Borrow<B>, B: ?Sized,

Calls .tap_borrow() only in debug builds, and is erased in release builds.
§

fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
where Self: BorrowMut<B>, B: ?Sized,

Calls .tap_borrow_mut() only in debug builds, and is erased in release builds.
§

fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
where Self: AsRef<R>, R: ?Sized,

Calls .tap_ref() only in debug builds, and is erased in release builds.
§

fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
where Self: AsMut<R>, R: ?Sized,

Calls .tap_ref_mut() only in debug builds, and is erased in release builds.
§

fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
where Self: Deref<Target = T>, T: ?Sized,

Calls .tap_deref() only in debug builds, and is erased in release builds.
§

fn tap_deref_mut_dbg<T>(self, func: impl FnOnce(&mut T)) -> Self
where Self: DerefMut<Target = T> + Deref, T: ?Sized,

Calls .tap_deref_mut() only in debug builds, and is erased in release builds.
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
§

impl<T> TryConv for T

§

fn try_conv<T>(self) -> Result<T, Self::Error>
where Self: TryInto<T>,

Attempts to convert self into T using TryInto<T>. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V

§

impl<T> WithSubscriber for T

§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a [WithDispatch] wrapper. Read more
§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a [WithDispatch] wrapper. Read more
source§

impl<T> SyncDeps for T
where T: Send + Sync,