ark_poly/polynomial/multivariate/
mod.rs

1//! Work with sparse multivariate polynomials.
2use ark_ff::Field;
3use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
4use ark_std::{
5    cmp::Ordering,
6    fmt::{Debug, Error, Formatter},
7    hash::Hash,
8    ops::Deref,
9    vec::*,
10};
11
12#[cfg(feature = "parallel")]
13use rayon::prelude::*;
14
15mod sparse;
16pub use sparse::SparsePolynomial;
17
18/// Describes the interface for a term (monomial) of a multivariate polynomial.
19pub trait Term:
20    Clone
21    + PartialOrd
22    + Ord
23    + PartialEq
24    + Eq
25    + Hash
26    + Default
27    + Debug
28    + Deref<Target = [(usize, usize)]>
29    + Send
30    + Sync
31    + CanonicalSerialize
32    + CanonicalDeserialize
33{
34    /// Create a new `Term` from a list of tuples of the form `(variable, power)`
35    fn new(term: Vec<(usize, usize)>) -> Self;
36
37    /// Returns the total degree of `self`. This is the sum of all variable
38    /// powers in `self`
39    fn degree(&self) -> usize;
40
41    /// Returns a list of variables in `self`
42    fn vars(&self) -> Vec<usize>;
43
44    /// Returns a list of the powers of each variable in `self`
45    fn powers(&self) -> Vec<usize>;
46
47    /// Returns whether `self` is a constant
48    fn is_constant(&self) -> bool;
49
50    /// Evaluates `self` at the point `p`.
51    fn evaluate<F: Field>(&self, p: &[F]) -> F;
52}
53
54/// Stores a term (monomial) in a multivariate polynomial.
55/// Each element is of the form `(variable, power)`.
56#[derive(Clone, PartialEq, Eq, Hash, Default, CanonicalSerialize, CanonicalDeserialize)]
57pub struct SparseTerm(Vec<(usize, usize)>);
58
59impl SparseTerm {
60    /// Sums the powers of any duplicated variables. Assumes `term` is sorted.
61    fn combine(term: &[(usize, usize)]) -> Vec<(usize, usize)> {
62        let mut term_dedup: Vec<(usize, usize)> = Vec::new();
63        for (var, pow) in term {
64            if let Some(prev) = term_dedup.last_mut() {
65                if prev.0 == *var {
66                    prev.1 += pow;
67                    continue;
68                }
69            }
70            term_dedup.push((*var, *pow));
71        }
72        term_dedup
73    }
74}
75
76impl Term for SparseTerm {
77    /// Create a new `Term` from a list of tuples of the form `(variable, power)`
78    fn new(mut term: Vec<(usize, usize)>) -> Self {
79        // Remove any terms with power 0
80        term.retain(|(_, pow)| *pow != 0);
81        // If there are more than one variables, make sure they are
82        // in order and combine any duplicates
83        if term.len() > 1 {
84            term.sort_by(|(v1, _), (v2, _)| v1.cmp(v2));
85            term = Self::combine(&term);
86        }
87        Self(term)
88    }
89
90    /// Returns the sum of all variable powers in `self`
91    fn degree(&self) -> usize {
92        self.iter().fold(0, |sum, acc| sum + acc.1)
93    }
94
95    /// Returns a list of variables in `self`
96    fn vars(&self) -> Vec<usize> {
97        self.iter().map(|(v, _)| *v).collect()
98    }
99
100    /// Returns a list of variable powers in `self`
101    fn powers(&self) -> Vec<usize> {
102        self.iter().map(|(_, p)| *p).collect()
103    }
104
105    /// Returns whether `self` is a constant
106    fn is_constant(&self) -> bool {
107        self.len() == 0 || self.degree() == 0
108    }
109
110    /// Evaluates `self` at the given `point` in the field.
111    fn evaluate<F: Field>(&self, point: &[F]) -> F {
112        cfg_into_iter!(self)
113            .map(|(var, power)| point[*var].pow([*power as u64]))
114            .product()
115    }
116}
117
118impl Debug for SparseTerm {
119    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
120        for variable in self.iter() {
121            if variable.1 == 1 {
122                write!(f, " * x_{}", variable.0)?;
123            } else {
124                write!(f, " * x_{}^{}", variable.0, variable.1)?;
125            }
126        }
127        Ok(())
128    }
129}
130
131impl Deref for SparseTerm {
132    type Target = [(usize, usize)];
133
134    fn deref(&self) -> &[(usize, usize)] {
135        &self.0
136    }
137}
138
139impl PartialOrd for SparseTerm {
140    /// Sort by total degree. If total degree is equal then ordering
141    /// is given by exponent weight in lower-numbered variables
142    /// ie. `x_1 > x_2`, `x_1^2 > x_1 * x_2`, etc.
143    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
144        if self.degree() != other.degree() {
145            Some(self.degree().cmp(&other.degree()))
146        } else {
147            // Iterate through all variables and return the corresponding ordering
148            // if they differ in variable numbering or power
149            for (cur, other) in self.iter().zip(other.iter()) {
150                if other.0 == cur.0 {
151                    if cur.1 != other.1 {
152                        return Some((cur.1).cmp(&other.1));
153                    }
154                } else {
155                    return Some((other.0).cmp(&cur.0));
156                }
157            }
158            Some(Ordering::Equal)
159        }
160    }
161}
162
163impl Ord for SparseTerm {
164    fn cmp(&self, other: &Self) -> Ordering {
165        self.partial_cmp(other).unwrap()
166    }
167}
ark_poly/polynomial/multivariate/mod.rs

ark_poly/polynomial/multivariate/
mod.rs
