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

o1_utils/
chunked_polynomial.rs
