Struct kimchi::lagrange_basis_evaluations::LagrangeBasisEvaluations

pub struct LagrangeBasisEvaluations<F> { /* private fields */ }

Evaluations of all normalized lagrange basis polynomials at a given point. Can be used to evaluate an Evaluations form polynomial at that point.

The Lagrange basis for polynomials of degree <= d over a domain {ω_0,...,ω_{d-1}} is the set of d polynomials {l_0,...,l_{d-1}} of degree d-1 that equal 1 at ω_i and 0 in the rest of the domain terms. They can be used to evaluate polynomials in evaluation form efficiently in O(d) time.

When chunking is in place, the domain size n is larger than the maximum polynomial degree allowed m. Thus, on input n = c·m evaluations for c chunks, we cannot obtain a polynomial f with degree c·m-1 with the equation:

f(X) = x_0 · l_0(X) + ... + x_{c·m-1} · l_{c·m-1}(X)

Instead, this struct will contain the c·m coefficients of the polynomial that is equal to the powers of the point x in the positions corresponding to the chunk, and 0 elsewhere in the domain. This is useful to evaluate the chunks of polynomials of degree c·m-1 given in evaluation form at the point.

Implementations

impl<F: FftField> LagrangeBasisEvaluations<F>

pub fn domain_size(&self) -> usize

Return the domain size of the individual evaluations.

Note that there is an invariant that all individual evaluation chunks have the same size. It is enforced by each constructor.

pub fn evaluate<D: EvaluationDomain<F>>(&self, p: &Evaluations<F, D>) -> Vec<F>

Given the evaluations form of a polynomial, directly evaluate that polynomial at a point.

The Lagrange basis evaluations can be used to evaluate a polynomial given in evaluation form efficiently in O(n) time, where n is the domain size, without the need of interpolating.

Recall that a polynomial can be represented as the sum of the scaled Lagrange polynomials using its evaluations on the domain: f(x) = x_0 · l_0(x) + ... + x_n · l_n(x)

But when chunking is in place, we want to evaluate a polynomial f of degree c · m - 1 at point z, expressed as

f(z) = a_0·z^0 + ... + a_{c*m}·z^{c·m}
     = z^0 · f_0(z) + z^m · f_1(z) + ... + z^{(c-1)m} · f_{c-1}(z)

where f_i(X) is the i-th chunked polynomial of degree m-1 of f: f_i(x) = a_{i·m} · x^0 + ... + a_{(i+1)m-1} · x^{m-1}

Returns the evaluation of each chunk of the polynomial at the point (when there is no chunking, the result is a vector of length 1). They correspond to the f_i(z) in the equation above.

pub fn evaluate_boolean<D: EvaluationDomain<F>>( &self, p: &Evaluations<F, D> ) -> Vec<F>

Given the evaluations form of a polynomial, directly evaluate that polynomial at a point, assuming that the given evaluations are either 0 or 1 at every point of the domain.

This method can particularly be useful when the polynomials represent (boolean) selectors in a circuit.

pub fn new( max_poly_size: usize, domain: D<F>, x: F ) -> LagrangeBasisEvaluations<F>