Struct LagrangeBasisEvaluations 

pub struct LagrangeBasisEvaluations<F> {
    evals: Vec<Vec<F>>,
}

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.

Fields

evals: Vec<Vec<F>>

If no chunking:

• evals is a vector of length 1 containing a vector of size n corresponding to the evaluations of the Lagrange polynomials, which are the polynomials that equal 1 at ω_i and 0 elsewhere in the domain.

If chunking (a vector of size c · n)

• the first index refers to the chunks
• the second index refers j-th coefficient of the i-th chunk of the polynomial that equals the powers of the point and 0 elsewhere (and the length of each such vector is n).

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.

fn new_with_segment_size_1(domain: D<F>, x: F) -> LagrangeBasisEvaluations<F>

Compute all evaluations of the normalized lagrange basis polynomials of the given domain at the given point. Runs in time O(domain size).

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

Compute all evaluations of the normalized Lagrange basis polynomials of the given domain at the given point x. Runs in time O(n log(n)) where n is the domain size.

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