Function evaluate_piecewise_multilinear

pub fn evaluate_piecewise_multilinear<F: Field>(
    point: &[F],
    n_pieces_by_vars: &[usize],
    piece_evals: &mut [F],
) -> Result<F, Error>

Evaluate a piecewise multilinear polynomial at a point, given the evaluations of the pieces.

A piecewise multilinear is defined by a sequence of multilinear polynomials, ordered from most number of variables to least. We define it over a boolean hypercube by identifying the smallest hypercube larger than the total number of hypercube evaluations of all the pieces, then concatenating the evaluations, flattened into vectors in little-endian order. The evaluation vector is right-padded with zeros up to the hypercube size of the containing cube. Equivalently, we can view the piecewise multilinear as defined by an inductive linear interpolation of pairs of polynomials.

This function takes a description of a piecewise multilinear polynomial and the evaluations of the pieces at prefixes of the given point, then evaluates the concatenated multilinear at the point.

Arguments

• point - the evaluation point. The length specifies the number of variables in the concatenated multilinear.
• n_pieces_by_vars - the number of multilinear pieces, indexed by the number of variables. Entry at index i is the number of multilinears with i variables. The sum of n_pieces_by_vars[i] * 2^i for all indices i must be at most 2^n, where n is the length of point..
• piece_evals - the evaluations of the multilinear pieces at the corresponding prefixes of point. The length must be equal to the sum of the values in n_pieces_by_vars. This must be in the same order as the corresponding multilinears are implicitly concatenated.

Example

Suppose we have three multilinear functions $f_0$, $f_1$, and $f_2$, which have $2$, $2$, and $1$ variables respectively. There exists a unique $4$-variate multilinear function $\tilde{f}$, which is defined by concatenating the evaluations of $f_0$, $f_1$, and $f_2$ along their respective defining Boolean hypercubes and then zero-padding. (I.e., we simply decree that the resulting list of length 16 is the ordered list of evaluations of a multilinear $\tilde{f}$ on $\mathcal B_4$.) We wish to evaluate $\tilde{f}$ at the point $(r_0, r_1, r_2, r_3)$, and we are given the evaluations of $v_0:=f_0(r_0,r_1)$, $v_1:=f_1(r_0,r_1)$, and $v_2:=f_2(r_0)$. In this situation, we have the following: n_pieces_by_vars is [0, 1, 2], and piece_evals is [v_0, v_1, v_2].