algebraeon_rings/polynomial/
multipoly.rs

1use crate::structure::*;
2use algebraeon_nzq::*;
3use std::borrow::Borrow;
4use std::collections::HashMap;
5use std::collections::HashSet;
6use std::fmt::Display;
7use std::hash::Hash;
8use std::sync::atomic::AtomicUsize;
9
10#[derive(Debug, Clone)]
11pub struct Variable {
12    pub(crate) ident: usize,
13    pub(crate) name: String,
14}
15
16impl PartialEq for Variable {
17    fn eq(&self, other: &Self) -> bool {
18        self.ident == other.ident
19    }
20}
21
22impl Eq for Variable {}
23
24impl Hash for Variable {
25    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
26        self.ident.hash(state);
27    }
28}
29
30impl Variable {
31    pub fn new<S: Into<String>>(name: S) -> Self {
32        static COUNTER: AtomicUsize = AtomicUsize::new(0);
33        let name = name.into();
34        assert!(!name.is_empty());
35        Self {
36            ident: COUNTER.fetch_add(1, std::sync::atomic::Ordering::Relaxed),
37            name,
38        }
39    }
40}
41
42#[derive(Debug, Clone, PartialEq, Eq, Hash)]
43pub struct VariablePower {
44    pub(crate) var: Variable,
45    pub(crate) pow: usize,
46}
47
48#[derive(Debug, Clone)]
49pub struct Monomial {
50    pub(crate) prod: Vec<VariablePower>, //should be sorted by variable ident
51    pub(crate) ident_lookup: HashMap<usize, usize>, //point from variable ident to index of that variables power in self.prod
52}
53
54impl PartialEq for Monomial {
55    fn eq(&self, other: &Self) -> bool {
56        self.prod == other.prod
57    }
58}
59
60impl Eq for Monomial {}
61
62impl Hash for Monomial {
63    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
64        self.prod.hash(state);
65    }
66}
67
68impl Display for Monomial {
69    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
70        if self.prod.is_empty() {
71            write!(f, "1")
72        } else {
73            for VariablePower { var, pow } in &self.prod {
74                write!(f, "{}", &var.name)?;
75                if *pow != 1 {
76                    write!(f, "^")?;
77                    write!(f, "{}", pow)?;
78                }
79            }
80            Ok(())
81        }
82    }
83}
84
85impl Monomial {
86    pub fn check_invariants(&self) -> Result<(), &'static str> {
87        let mut vars = HashSet::new();
88        for VariablePower { var, pow } in &self.prod {
89            if pow == &0 {
90                return Err("shouldn't have a variable to the power of zero");
91            }
92            if vars.contains(var) {
93                return Err("each var should appear at most once");
94            }
95            vars.insert(var);
96        }
97        for (ident, idx) in &self.ident_lookup {
98            if &self.prod[*idx].var.ident != ident {
99                return Err("bad ident_lookup");
100            }
101        }
102        let mut ordered_prod = self.prod.clone();
103        ordered_prod.sort_by_key(|VariablePower { var, pow: _pow }| var.ident);
104        if self.prod != ordered_prod {
105            return Err("var powers are not sorted");
106        }
107        Ok(())
108    }
109
110    pub fn new(mut prod: Vec<VariablePower>) -> Self {
111        prod.retain(|VariablePower { var: _var, pow }| pow != &0);
112        prod.sort_by_key(|vpow| vpow.var.ident);
113        let mut ident_lookup = HashMap::new();
114        for (idx, VariablePower { var, pow: _pow }) in prod.iter().enumerate() {
115            ident_lookup.insert(var.ident, idx);
116        }
117        Self { prod, ident_lookup }
118    }
119
120    pub fn one() -> Self {
121        Monomial {
122            prod: vec![],
123            ident_lookup: HashMap::new(),
124        }
125    }
126
127    pub fn degree(&self) -> usize {
128        let mut d = 0;
129        for VariablePower { var: _var, pow } in &self.prod {
130            d += pow;
131        }
132        d
133    }
134
135    pub fn homogenize(&self, target_degree: usize, v: &Variable) -> Self {
136        let self_degree = self.degree();
137        if target_degree >= self_degree {
138            let mut prod = self.prod.clone();
139            prod.push(VariablePower {
140                var: v.clone(),
141                pow: target_degree - self_degree,
142            });
143            Self::new(prod)
144        } else {
145            panic!();
146        }
147    }
148
149    pub fn get_var_pow(&self, v: &Variable) -> usize {
150        if self.ident_lookup.contains_key(&v.ident) {
151            self.prod[*self.ident_lookup.get(&v.ident).unwrap()].pow
152        } else {
153            0
154        }
155    }
156
157    pub fn free_vars(&self) -> HashSet<Variable> {
158        self.prod
159            .iter()
160            .map(|VariablePower { var, pow: _pow }| var.clone())
161            .collect()
162    }
163
164    pub fn evaluate<RS: RingSignature>(
165        &self,
166        ring: &RS,
167        values: &HashMap<Variable, impl Borrow<RS::Set>>,
168    ) -> RS::Set {
169        ring.product(
170            self.prod
171                .iter()
172                .map(|VariablePower { var, pow }| {
173                    ring.nat_pow(values.get(var).unwrap().borrow(), &Natural::from(*pow))
174                })
175                .collect(),
176        )
177    }
178
179    pub fn mul(a: &Self, b: &Self) -> Self {
180        Self::new({
181            let mut prod = HashMap::new();
182            for VariablePower { var: v, pow: k } in &a.prod {
183                *prod.entry(v.clone()).or_insert(0) += k;
184            }
185            for VariablePower { var: v, pow: k } in &b.prod {
186                *prod.entry(v.clone()).or_insert(0) += k;
187            }
188            let prod: Vec<VariablePower> = prod
189                .into_iter()
190                .map(|(v, k)| VariablePower { var: v, pow: k })
191                .collect();
192            prod
193        })
194    }
195
196    pub fn lexicographic_order(a: &Self, b: &Self) -> std::cmp::Ordering {
197        let mut i = 0;
198        while i < std::cmp::min(a.prod.len(), b.prod.len()) {
199            #[allow(clippy::comparison_chain)]
200            if a.prod[i].var.ident < b.prod[i].var.ident {
201                return std::cmp::Ordering::Less;
202            } else if a.prod[i].var.ident > b.prod[i].var.ident {
203                return std::cmp::Ordering::Greater;
204            }
205            if a.prod[i].pow > b.prod[i].pow {
206                return std::cmp::Ordering::Less;
207            }
208            if a.prod[i].pow < b.prod[i].pow {
209                return std::cmp::Ordering::Greater;
210            }
211            i += 1;
212        }
213        #[allow(clippy::comparison_chain)]
214        return if a.prod.len() > b.prod.len() {
215            std::cmp::Ordering::Less
216        } else if a.prod.len() < b.prod.len() {
217            std::cmp::Ordering::Greater
218        } else {
219            std::cmp::Ordering::Equal
220        };
221    }
222
223    pub fn graded_lexicographic_order(a: &Self, b: &Self) -> std::cmp::Ordering {
224        #[allow(clippy::comparison_chain)]
225        if a.degree() < b.degree() {
226            std::cmp::Ordering::Greater
227        } else if a.degree() > b.degree() {
228            std::cmp::Ordering::Less
229        } else {
230            Self::lexicographic_order(a, b)
231        }
232    }
233}
234
235#[derive(Debug, Clone)]
236pub struct Term<ElemT: Clone> {
237    pub(crate) coeff: ElemT,
238    pub(crate) monomial: Monomial,
239}
240
241impl<ElemT: Clone> Term<ElemT> {
242    fn check_invariants(&self) -> Result<(), &'static str> {
243        self.monomial.check_invariants()
244    }
245
246    pub fn degree(&self) -> usize {
247        self.monomial.degree()
248    }
249}
250
251#[derive(Debug, Clone)]
252pub struct MultiPolynomial<R: Clone> {
253    pub(crate) terms: Vec<Term<R>>, //sorted by monomial ordering
254}
255
256impl<R: Clone> MultiPolynomial<R> {
257    pub fn check_invariants(&self) -> Result<(), &'static str> {
258        for term in &self.terms {
259            match term.check_invariants() {
260                Ok(()) => {}
261                Err(e) => {
262                    return Err(e);
263                }
264            }
265            // if self.coeff_ring.is_zero(&term.coeff) {
266            //     return Err("coeff should not be zero");
267            // }
268        }
269
270        if !(0..self.terms.len() - 1).all(|i| {
271            Monomial::lexicographic_order(&self.terms[i].monomial, &self.terms[i + 1].monomial)
272                .is_le()
273        }) {
274            return Err("terms are not sorted");
275        }
276
277        Ok(())
278    }
279
280    pub fn new(mut terms: Vec<Term<R>>) -> Self {
281        terms.sort_by(|t1, t2| Monomial::lexicographic_order(&t1.monomial, &t2.monomial));
282        Self { terms }
283    }
284
285    pub fn constant(c: R) -> MultiPolynomial<R> {
286        MultiPolynomial {
287            terms: vec![Term {
288                coeff: c,
289                monomial: Monomial::one(),
290            }],
291        }
292    }
293
294    pub fn term(t: Term<R>) -> MultiPolynomial<R> {
295        MultiPolynomial { terms: vec![t] }
296    }
297
298    pub fn free_vars(&self) -> HashSet<Variable> {
299        let mut vars = HashSet::new();
300        for term in &self.terms {
301            vars.extend(term.monomial.free_vars());
302        }
303        vars
304    }
305
306    pub fn apply_map<ImgSet: Clone>(&self, f: impl Fn(&R) -> ImgSet) -> MultiPolynomial<ImgSet> {
307        MultiPolynomial {
308            terms: self
309                .terms
310                .iter()
311                .map(|Term { coeff, monomial }| Term {
312                    coeff: f(coeff),
313                    monomial: monomial.clone(),
314                })
315                .collect(),
316        }
317    }
318
319    pub fn apply_map_vars(self, f: HashMap<Variable, Variable>) -> MultiPolynomial<R> {
320        MultiPolynomial {
321            terms: self
322                .terms
323                .into_iter()
324                .map(
325                    |Term {
326                         coeff,
327                         monomial: Monomial { prod, .. },
328                     }| Term {
329                        coeff,
330                        monomial: Monomial::new(
331                            prod.into_iter()
332                                .map(|VariablePower { var, pow }| VariablePower {
333                                    var: f.get(&var).unwrap().clone(),
334                                    pow,
335                                })
336                                .collect(),
337                        ),
338                    },
339                )
340                .collect(),
341        }
342    }
343
344    pub fn evaluate_var_zero(self, v: &Variable) -> MultiPolynomial<R> {
345        MultiPolynomial {
346            terms: self
347                .terms
348                .into_iter()
349                .filter(|Term { monomial, .. }| monomial.get_var_pow(v) == 0)
350                .collect(),
351        }
352    }
353
354    //return the terms where every var in vars is present
355    pub fn has_all_vars_parts(self, vars: Vec<&Variable>) -> MultiPolynomial<R> {
356        MultiPolynomial {
357            terms: self
358                .terms
359                .into_iter()
360                .filter(|Term { monomial, .. }| vars.iter().all(|v| monomial.get_var_pow(v) > 0))
361                .collect(),
362        }
363    }
364}
365
366#[derive(Debug, Clone, Copy, PartialEq, Eq)]
367pub enum HomogeneousOfDegreeResult {
368    No,
369    Zero,
370    Homogeneous(usize),
371}
372
373impl<R: Clone> MultiPolynomial<R> {
374    pub fn homogeneous_of_degree(&self) -> HomogeneousOfDegreeResult {
375        let mut terms = self.terms.iter().collect::<Vec<_>>();
376        match terms.pop() {
377            Some(first_term) => {
378                let d = first_term.degree();
379                for term in terms {
380                    if d != term.degree() {
381                        return HomogeneousOfDegreeResult::No;
382                    }
383                }
384                HomogeneousOfDegreeResult::Homogeneous(d)
385            }
386            None => {
387                // Zero polynomial is homogeneous of degree infinity
388                HomogeneousOfDegreeResult::Zero
389            }
390        }
391    }
392}
algebraeon_rings/polynomial/multipoly.rs

algebraeon_rings/polynomial/
multipoly.rs
