ark_poly/polynomial/multivariate/
sparse.rs

1//! A sparse multivariate polynomial represented in coefficient form.
2use crate::{
3    multivariate::{SparseTerm, Term},
4    DenseMVPolynomial, Polynomial,
5};
6use ark_ff::{Field, Zero};
7use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
8use ark_std::{
9    cmp::Ordering,
10    fmt,
11    ops::{Add, AddAssign, Neg, Sub, SubAssign},
12    rand::Rng,
13    vec::*,
14};
15
16#[cfg(feature = "parallel")]
17use rayon::prelude::*;
18
19/// Stores a sparse multivariate polynomial in coefficient form.
20#[derive(Educe, CanonicalSerialize, CanonicalDeserialize)]
21#[educe(Clone, PartialEq, Eq, Hash, Default)]
22pub struct SparsePolynomial<F: Field, T: Term> {
23    /// The number of variables the polynomial supports
24    #[educe(PartialEq(ignore))]
25    pub num_vars: usize,
26    /// List of each term along with its coefficient
27    pub terms: Vec<(F, T)>,
28}
29
30impl<F: Field, T: Term> SparsePolynomial<F, T> {
31    fn remove_zeros(&mut self) {
32        self.terms.retain(|(c, _)| !c.is_zero());
33    }
34}
35
36impl<F: Field> Polynomial<F> for SparsePolynomial<F, SparseTerm> {
37    type Point = Vec<F>;
38
39    /// Returns the total degree of the polynomial
40    ///
41    /// # Examples
42    /// ```
43    /// use ark_poly::{
44    ///     polynomial::multivariate::{SparsePolynomial, SparseTerm},
45    ///     DenseMVPolynomial, Polynomial,
46    /// };
47    /// use ark_std::test_rng;
48    /// use ark_test_curves::bls12_381::Fq;
49    ///
50    /// let rng = &mut test_rng();
51    /// // Create a multivariate polynomial of degree 7
52    /// let poly: SparsePolynomial<Fq, SparseTerm> = SparsePolynomial::rand(7, 2, rng);
53    /// assert_eq!(poly.degree(), 7);
54    /// ```
55    fn degree(&self) -> usize {
56        self.terms
57            .iter()
58            .map(|(_, term)| term.degree())
59            .max()
60            .unwrap_or(0)
61    }
62
63    /// Evaluates `self` at the given `point` in `Self::Point`.
64    ///
65    /// # Examples
66    /// ```
67    /// use ark_ff::UniformRand;
68    /// use ark_poly::{
69    ///     polynomial::multivariate::{SparsePolynomial, SparseTerm, Term},
70    ///     DenseMVPolynomial, Polynomial,
71    /// };
72    /// use ark_std::test_rng;
73    /// use ark_test_curves::bls12_381::Fq;
74    ///
75    /// let rng = &mut test_rng();
76    /// let poly = SparsePolynomial::rand(4, 3, rng);
77    /// let random_point = vec![Fq::rand(rng); 3];
78    /// // The result will be a single element in the field.
79    /// let result: Fq = poly.evaluate(&random_point);
80    /// ```
81    fn evaluate(&self, point: &Vec<F>) -> F {
82        assert!(point.len() >= self.num_vars, "Invalid evaluation domain");
83        if self.is_zero() {
84            return F::zero();
85        }
86        cfg_into_iter!(&self.terms)
87            .map(|(coeff, term)| *coeff * term.evaluate(point))
88            .sum()
89    }
90}
91
92impl<F: Field> DenseMVPolynomial<F> for SparsePolynomial<F, SparseTerm> {
93    /// Returns the number of variables in `self`
94    fn num_vars(&self) -> usize {
95        self.num_vars
96    }
97
98    /// Outputs an `l`-variate polynomial which is the sum of `l` `d`-degree
99    /// univariate polynomials where each coefficient is sampled uniformly at random.
100    fn rand<R: Rng>(d: usize, l: usize, rng: &mut R) -> Self {
101        let mut random_terms = vec![(F::rand(rng), SparseTerm::new(vec![]))];
102        for var in 0..l {
103            for deg in 1..=d {
104                random_terms.push((F::rand(rng), SparseTerm::new(vec![(var, deg)])));
105            }
106        }
107        Self::from_coefficients_vec(l, random_terms)
108    }
109
110    type Term = SparseTerm;
111
112    /// Constructs a new polynomial from a list of tuples of the form `(coeff, Self::Term)`
113    ///
114    /// # Examples
115    /// ```
116    /// use ark_poly::{
117    ///     polynomial::multivariate::{SparsePolynomial, SparseTerm, Term},
118    ///     DenseMVPolynomial, Polynomial,
119    /// };
120    /// use ark_test_curves::bls12_381::Fq;
121    ///
122    /// // Create a multivariate polynomial in 3 variables, with 4 terms:
123    /// // 2*x_0^3 + x_0*x_2 + x_1*x_2 + 5
124    /// let poly = SparsePolynomial::from_coefficients_vec(
125    ///     3,
126    ///     vec![
127    ///         (Fq::from(2), SparseTerm::new(vec![(0, 3)])),
128    ///         (Fq::from(1), SparseTerm::new(vec![(0, 1), (2, 1)])),
129    ///         (Fq::from(1), SparseTerm::new(vec![(1, 1), (2, 1)])),
130    ///         (Fq::from(5), SparseTerm::new(vec![])),
131    ///     ],
132    /// );
133    /// ```
134    fn from_coefficients_vec(num_vars: usize, mut terms: Vec<(F, SparseTerm)>) -> Self {
135        // Ensure that terms are in ascending order.
136        terms.sort_by(|(_, t1), (_, t2)| t1.cmp(t2));
137        // If any terms are duplicated, add them together
138        let mut terms_dedup: Vec<(F, SparseTerm)> = Vec::new();
139        for term in terms {
140            if let Some(prev) = terms_dedup.last_mut() {
141                if prev.1 == term.1 {
142                    *prev = (prev.0 + term.0, prev.1.clone());
143                    continue;
144                }
145            };
146            // Assert correct number of indeterminates
147            assert!(
148                term.1.iter().all(|(var, _)| *var < num_vars),
149                "Invalid number of indeterminates"
150            );
151            terms_dedup.push(term);
152        }
153        let mut result = Self {
154            num_vars,
155            terms: terms_dedup,
156        };
157        // Remove any terms with zero coefficients
158        result.remove_zeros();
159        result
160    }
161
162    /// Returns the terms of a `self` as a list of tuples of the form `(coeff, Self::Term)`
163    fn terms(&self) -> &[(F, Self::Term)] {
164        self.terms.as_slice()
165    }
166}
167
168impl<F: Field, T: Term> Add for SparsePolynomial<F, T> {
169    type Output = SparsePolynomial<F, T>;
170
171    fn add(self, other: SparsePolynomial<F, T>) -> Self {
172        &self + &other
173    }
174}
175
176impl<'a, 'b, F: Field, T: Term> Add<&'a SparsePolynomial<F, T>> for &'b SparsePolynomial<F, T> {
177    type Output = SparsePolynomial<F, T>;
178
179    fn add(self, other: &'a SparsePolynomial<F, T>) -> SparsePolynomial<F, T> {
180        let mut result = Vec::new();
181        let mut cur_iter = self.terms.iter().peekable();
182        let mut other_iter = other.terms.iter().peekable();
183        // Since both polynomials are sorted, iterate over them in ascending order,
184        // combining any common terms
185        loop {
186            // Peek at iterators to decide which to take from
187            let which = match (cur_iter.peek(), other_iter.peek()) {
188                (Some(cur), Some(other)) => Some((cur.1).cmp(&other.1)),
189                (Some(_), None) => Some(Ordering::Less),
190                (None, Some(_)) => Some(Ordering::Greater),
191                (None, None) => None,
192            };
193            // Push the smallest element to the `result` coefficient vec
194            let smallest = match which {
195                Some(Ordering::Less) => cur_iter.next().unwrap().clone(),
196                Some(Ordering::Equal) => {
197                    let other = other_iter.next().unwrap();
198                    let cur = cur_iter.next().unwrap();
199                    (cur.0 + other.0, cur.1.clone())
200                },
201                Some(Ordering::Greater) => other_iter.next().unwrap().clone(),
202                None => break,
203            };
204            result.push(smallest);
205        }
206        // Remove any zero terms
207        result.retain(|(c, _)| !c.is_zero());
208        SparsePolynomial {
209            num_vars: core::cmp::max(self.num_vars, other.num_vars),
210            terms: result,
211        }
212    }
213}
214
215impl<'a, F: Field, T: Term> AddAssign<&'a SparsePolynomial<F, T>> for SparsePolynomial<F, T> {
216    fn add_assign(&mut self, other: &'a SparsePolynomial<F, T>) {
217        *self = &*self + other;
218    }
219}
220
221impl<'a, F: Field, T: Term> AddAssign<(F, &'a SparsePolynomial<F, T>)> for SparsePolynomial<F, T> {
222    fn add_assign(&mut self, (f, other): (F, &'a SparsePolynomial<F, T>)) {
223        let other = Self {
224            num_vars: other.num_vars,
225            terms: other
226                .terms
227                .iter()
228                .map(|(coeff, term)| (*coeff * f, term.clone()))
229                .collect(),
230        };
231        // Note the call to `Add` will remove also any duplicates
232        *self = &*self + &other;
233    }
234}
235
236impl<F: Field, T: Term> Neg for SparsePolynomial<F, T> {
237    type Output = SparsePolynomial<F, T>;
238
239    #[inline]
240    fn neg(mut self) -> SparsePolynomial<F, T> {
241        for coeff in &mut self.terms {
242            (coeff).0 = -coeff.0;
243        }
244        self
245    }
246}
247
248impl<'a, 'b, F: Field, T: Term> Sub<&'a SparsePolynomial<F, T>> for &'b SparsePolynomial<F, T> {
249    type Output = SparsePolynomial<F, T>;
250
251    #[inline]
252    fn sub(self, other: &'a SparsePolynomial<F, T>) -> SparsePolynomial<F, T> {
253        let neg_other = other.clone().neg();
254        self + &neg_other
255    }
256}
257
258impl<'a, F: Field, T: Term> SubAssign<&'a SparsePolynomial<F, T>> for SparsePolynomial<F, T> {
259    #[inline]
260    fn sub_assign(&mut self, other: &'a SparsePolynomial<F, T>) {
261        *self = &*self - other;
262    }
263}
264
265impl<F: Field, T: Term> fmt::Debug for SparsePolynomial<F, T> {
266    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
267        for (coeff, term) in self.terms.iter().filter(|(c, _)| !c.is_zero()) {
268            if term.is_constant() {
269                write!(f, "\n{:?}", coeff)?;
270            } else {
271                write!(f, "\n{:?} {:?}", coeff, term)?;
272            }
273        }
274        Ok(())
275    }
276}
277
278impl<F: Field, T: Term> Zero for SparsePolynomial<F, T> {
279    /// Returns the zero polynomial.
280    fn zero() -> Self {
281        Self {
282            num_vars: 0,
283            terms: Vec::new(),
284        }
285    }
286
287    /// Checks if the given polynomial is zero.
288    fn is_zero(&self) -> bool {
289        self.terms.is_empty() || self.terms.iter().all(|(c, _)| c.is_zero())
290    }
291}
292
293#[cfg(test)]
294mod tests {
295    use super::*;
296    use ark_ff::UniformRand;
297    use ark_std::test_rng;
298    use ark_test_curves::bls12_381::Fr;
299
300    // TODO: Make tests generic over term type
301
302    /// Generate random `l`-variate polynomial of maximum individual degree `d`
303    fn rand_poly<R: Rng>(l: usize, d: usize, rng: &mut R) -> SparsePolynomial<Fr, SparseTerm> {
304        let mut random_terms = Vec::new();
305        let num_terms = rng.gen_range(1..1000);
306        // For each term, randomly select up to `l` variables with degree
307        // in [1,d] and random coefficient
308        random_terms.push((Fr::rand(rng), SparseTerm::new(vec![])));
309        for _ in 1..num_terms {
310            let term = (0..l)
311                .map(|i| {
312                    if rng.gen_bool(0.5) {
313                        Some((i, rng.gen_range(1..(d + 1))))
314                    } else {
315                        None
316                    }
317                })
318                .flatten()
319                .collect();
320            let coeff = Fr::rand(rng);
321            random_terms.push((coeff, SparseTerm::new(term)));
322        }
323        SparsePolynomial::from_coefficients_slice(l, &random_terms)
324    }
325
326    /// Perform a naive n^2 multiplication of `self` by `other`.
327    fn naive_mul(
328        cur: &SparsePolynomial<Fr, SparseTerm>,
329        other: &SparsePolynomial<Fr, SparseTerm>,
330    ) -> SparsePolynomial<Fr, SparseTerm> {
331        if cur.is_zero() || other.is_zero() {
332            SparsePolynomial::zero()
333        } else {
334            let mut result_terms = Vec::new();
335            for (cur_coeff, cur_term) in cur.terms.iter() {
336                for (other_coeff, other_term) in other.terms.iter() {
337                    let mut term = cur_term.0.clone();
338                    term.extend(other_term.0.clone());
339                    result_terms.push((*cur_coeff * *other_coeff, SparseTerm::new(term)));
340                }
341            }
342            SparsePolynomial::from_coefficients_slice(cur.num_vars, result_terms.as_slice())
343        }
344    }
345
346    #[test]
347    fn add_polynomials() {
348        let rng = &mut test_rng();
349        let max_degree = 10;
350        for a_var_count in 1..20 {
351            for b_var_count in 1..20 {
352                let p1 = rand_poly(a_var_count, max_degree, rng);
353                let p2 = rand_poly(b_var_count, max_degree, rng);
354                let res1 = &p1 + &p2;
355                let res2 = &p2 + &p1;
356                assert_eq!(res1, res2);
357            }
358        }
359    }
360
361    #[test]
362    fn sub_polynomials() {
363        let rng = &mut test_rng();
364        let max_degree = 10;
365        for a_var_count in 1..20 {
366            for b_var_count in 1..20 {
367                let p1 = rand_poly(a_var_count, max_degree, rng);
368                let p2 = rand_poly(b_var_count, max_degree, rng);
369                let res1 = &p1 - &p2;
370                let res2 = &p2 - &p1;
371                assert_eq!(&res1 + &p2, p1);
372                assert_eq!(res1, -res2);
373            }
374        }
375    }
376
377    #[test]
378    fn evaluate_polynomials() {
379        let rng = &mut test_rng();
380        let max_degree = 10;
381        for var_count in 1..20 {
382            let p = rand_poly(var_count, max_degree, rng);
383            let mut point = Vec::with_capacity(var_count);
384            for _ in 0..var_count {
385                point.push(Fr::rand(rng));
386            }
387            let mut total = Fr::zero();
388            for (coeff, term) in p.terms.iter() {
389                let mut summand = *coeff;
390                for var in term.iter() {
391                    let eval = point.get(var.0).unwrap();
392                    summand *= eval.pow(&[var.1 as u64]);
393                }
394                total += summand;
395            }
396            assert_eq!(p.evaluate(&point), total);
397        }
398    }
399
400    #[test]
401    fn add_and_evaluate_polynomials() {
402        let rng = &mut test_rng();
403        let max_degree = 10;
404        for a_var_count in 1..20 {
405            for b_var_count in 1..20 {
406                let p1 = rand_poly(a_var_count, max_degree, rng);
407                let p2 = rand_poly(b_var_count, max_degree, rng);
408                let mut point = Vec::new();
409                for _ in 0..core::cmp::max(a_var_count, b_var_count) {
410                    point.push(Fr::rand(rng));
411                }
412                // Evaluate both polynomials at a given point
413                let eval1 = p1.evaluate(&point);
414                let eval2 = p2.evaluate(&point);
415                // Add polynomials
416                let sum = &p1 + &p2;
417                // Evaluate result at same point
418                let eval3 = sum.evaluate(&point);
419                assert_eq!(eval1 + eval2, eval3);
420            }
421        }
422    }
423
424    #[test]
425    /// This is just to make sure naive_mul works as expected
426    fn mul_polynomials_fixed() {
427        let a = SparsePolynomial::from_coefficients_slice(
428            4,
429            &[
430                ("2".parse().unwrap(), SparseTerm(vec![])),
431                ("4".parse().unwrap(), SparseTerm(vec![(0, 1), (1, 2)])),
432                ("8".parse().unwrap(), SparseTerm(vec![(0, 1), (0, 1)])),
433                ("1".parse().unwrap(), SparseTerm(vec![(3, 0)])),
434            ],
435        );
436        let b = SparsePolynomial::from_coefficients_slice(
437            4,
438            &[
439                ("1".parse().unwrap(), SparseTerm(vec![(0, 1), (1, 2)])),
440                ("2".parse().unwrap(), SparseTerm(vec![(2, 1)])),
441                ("1".parse().unwrap(), SparseTerm(vec![(3, 1)])),
442            ],
443        );
444        let result = naive_mul(&a, &b);
445        let expected = SparsePolynomial::from_coefficients_slice(
446            4,
447            &[
448                ("3".parse().unwrap(), SparseTerm(vec![(0, 1), (1, 2)])),
449                ("6".parse().unwrap(), SparseTerm(vec![(2, 1)])),
450                ("3".parse().unwrap(), SparseTerm(vec![(3, 1)])),
451                ("4".parse().unwrap(), SparseTerm(vec![(0, 2), (1, 4)])),
452                (
453                    "8".parse().unwrap(),
454                    SparseTerm(vec![(0, 1), (1, 2), (2, 1)]),
455                ),
456                (
457                    "4".parse().unwrap(),
458                    SparseTerm(vec![(0, 1), (1, 2), (3, 1)]),
459                ),
460                ("8".parse().unwrap(), SparseTerm(vec![(0, 3), (1, 2)])),
461                ("16".parse().unwrap(), SparseTerm(vec![(0, 2), (2, 1)])),
462                ("8".parse().unwrap(), SparseTerm(vec![(0, 2), (3, 1)])),
463            ],
464        );
465        assert_eq!(expected, result);
466    }
467}
ark_poly/polynomial/multivariate/sparse.rs

ark_poly/polynomial/multivariate/
sparse.rs
