o1_utils/
chunked_polynomial.rs

1//! This module contains a type [ChunkedPolynomial],
2//! and a number of helper methods to deal with chunked polynomials.
3//! Polynomials that cut in several polynomials of the same length.
4
5use ark_ff::Field;
6use ark_poly::polynomial::{univariate::DensePolynomial, Polynomial};
7
8/// This struct contains multiple chunk polynomials with degree `size-1`.
9#[derive(Clone)]
10pub struct ChunkedPolynomial<F: Field> {
11    /// The chunk polynomials.
12    pub polys: Vec<DensePolynomial<F>>,
13
14    /// Each chunk polynomial has degree `size-1`.
15    pub size: usize,
16}
17
18impl<F: Field> ChunkedPolynomial<F> {
19    /// This function evaluates polynomial in chunks.
20    pub fn evaluate_chunks(&self, elm: F) -> Vec<F> {
21        let mut res: Vec<F> = vec![];
22        for poly in &self.polys {
23            let eval = poly.evaluate(&elm);
24            res.push(eval);
25        }
26        res
27    }
28
29    /// Multiplies the chunks of a polynomial with powers of zeta^n to make it of degree n-1.
30    /// For example, if a polynomial can be written `f = f0 + x^n f1 + x^2n f2`
31    /// (where f0, f1, f2 are of degree n-1), then this function returns the new semi-evaluated
32    /// `f'(x) = f0(x) + zeta^n f1(x) + zeta^2n f2(x)`.
33    pub fn linearize(&self, zeta_n: F) -> DensePolynomial<F> {
34        let mut scale = F::one();
35        let mut coeffs = vec![F::zero(); self.size];
36
37        for poly in &self.polys {
38            for (coeff, poly_coeff) in coeffs.iter_mut().zip(&poly.coeffs) {
39                *coeff += scale * poly_coeff;
40            }
41
42            scale *= zeta_n;
43        }
44
45        while coeffs.last().map_or(false, |c| c.is_zero()) {
46            coeffs.pop();
47        }
48
49        DensePolynomial { coeffs }
50    }
51}
o1_utils/chunked_polynomial.rs

o1_utils/
chunked_polynomial.rs
