algebraeon_rings/polynomial/
multipoly_structure.rs

1use super::Polynomial;
2use super::polynomial_structure::*;
3use crate::polynomial::HomogeneousOfDegreeResult;
4use crate::polynomial::Monomial;
5use crate::polynomial::MultiPolynomial;
6use crate::polynomial::Term;
7use crate::polynomial::Variable;
8use crate::polynomial::VariablePower;
9use crate::structure::*;
10use algebraeon_nzq::*;
11use algebraeon_sets::structure::*;
12use std::borrow::Borrow;
13use std::collections::HashMap;
14use std::collections::HashSet;
15use std::fmt::Display;
16use std::marker::PhantomData;
17use std::rc::Rc;
18
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub struct MultiPolynomialStructure<RS: RingEqSignature, RSB: BorrowedStructure<RS>> {
21    _coeff_ring: PhantomData<RS>,
22    coeff_ring: RSB,
23}
24
25impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> MultiPolynomialStructure<RS, RSB> {
26    fn new(coeff_ring: RSB) -> Self {
27        Self {
28            _coeff_ring: PhantomData,
29            coeff_ring,
30        }
31    }
32
33    pub fn coeff_ring(&self) -> &RS {
34        self.coeff_ring.borrow()
35    }
36}
37
38pub trait RingToMultiPolynomialRingSignature: RingEqSignature {
39    fn multivariable_polynomial_ring(&self) -> MultiPolynomialStructure<Self, &Self> {
40        MultiPolynomialStructure::new(self)
41    }
42
43    fn into_multivariable_polynomial_ring(self) -> MultiPolynomialStructure<Self, Self> {
44        MultiPolynomialStructure::new(self)
45    }
46}
47impl<RS: RingEqSignature> RingToMultiPolynomialRingSignature for RS {}
48
49impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> Signature
50    for MultiPolynomialStructure<RS, RSB>
51{
52}
53
54impl<RS: RingEqSignature + ToStringSignature, RSB: BorrowedStructure<RS>> ToStringSignature
55    for MultiPolynomialStructure<RS, RSB>
56{
57    fn to_string(&self, p: &Self::Set) -> String {
58        if p.terms.is_empty() {
59            "0".into()
60        } else {
61            let mut s = String::new();
62            for (idx, term) in p.terms.iter().enumerate() {
63                if idx != 0 {
64                    s += "+";
65                }
66                if !self
67                    .coeff_ring()
68                    .equal(&term.coeff, &self.coeff_ring().one())
69                {
70                    s += "(";
71                    s += &self.coeff_ring().to_string(&term.coeff);
72                    s += ")";
73                }
74                s += &term.monomial.to_string();
75            }
76            s
77        }
78    }
79}
80
81impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> SetSignature
82    for MultiPolynomialStructure<RS, RSB>
83{
84    type Set = MultiPolynomial<RS::Set>;
85
86    fn is_element(&self, _x: &Self::Set) -> Result<(), String> {
87        Ok(())
88    }
89}
90
91impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> EqSignature
92    for MultiPolynomialStructure<RS, RSB>
93{
94    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
95        let a = self.reduce(a.clone());
96        let b = self.reduce(b.clone());
97
98        let n = a.terms.len();
99        if n == b.terms.len() {
100            (0..n).all(|i| {
101                self.coeff_ring()
102                    .equal(&a.terms[i].coeff, &b.terms[i].coeff)
103                    && a.terms[i].monomial == b.terms[i].monomial
104            })
105        } else {
106            false
107        }
108    }
109}
110
111impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> RinglikeSpecializationSignature
112    for MultiPolynomialStructure<RS, RSB>
113{
114}
115
116impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> ZeroSignature
117    for MultiPolynomialStructure<RS, RSB>
118{
119    fn zero(&self) -> Self::Set {
120        MultiPolynomial { terms: vec![] }
121    }
122}
123
124impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> AdditionSignature
125    for MultiPolynomialStructure<RS, RSB>
126{
127    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
128        let mut a = a.clone();
129        let mut existing_monomials: HashMap<Monomial, usize> = HashMap::new(); //the index of each monomial
130        for (
131            idx,
132            Term {
133                coeff: _coeff,
134                monomial,
135            },
136        ) in a.terms.clone().into_iter().enumerate()
137        {
138            existing_monomials.insert(monomial, idx);
139        }
140        for Term { coeff, monomial } in &b.terms {
141            if existing_monomials.contains_key(monomial) {
142                self.coeff_ring().add_mut(
143                    &mut a.terms[*existing_monomials.get(monomial).unwrap()].coeff,
144                    coeff,
145                );
146            } else {
147                a.terms.push(Term {
148                    coeff: coeff.clone(),
149                    monomial: monomial.clone(),
150                });
151            }
152        }
153        self.reduce(a) //sort the coeffs
154    }
155}
156
157impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> CancellativeAdditionSignature
158    for MultiPolynomialStructure<RS, RSB>
159{
160    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
161        Some(self.sub(a, b))
162    }
163}
164
165impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> TryNegateSignature
166    for MultiPolynomialStructure<RS, RSB>
167{
168    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
169        Some(self.neg(a))
170    }
171}
172
173impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> AdditiveMonoidSignature
174    for MultiPolynomialStructure<RS, RSB>
175{
176}
177
178impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> AdditiveGroupSignature
179    for MultiPolynomialStructure<RS, RSB>
180{
181    fn neg(&self, a: &Self::Set) -> Self::Set {
182        MultiPolynomial {
183            terms: a
184                .terms
185                .iter()
186                .map(
187                    |Term {
188                         coeff: c,
189                         monomial: m,
190                     }| Term {
191                        coeff: self.coeff_ring().neg(c),
192                        monomial: m.clone(),
193                    },
194                )
195                .collect(),
196        }
197    }
198}
199
200impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> OneSignature
201    for MultiPolynomialStructure<RS, RSB>
202{
203    fn one(&self) -> Self::Set {
204        MultiPolynomial {
205            terms: vec![Term {
206                coeff: self.coeff_ring().one(),
207                monomial: Monomial::one(),
208            }],
209        }
210    }
211}
212
213impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> MultiplicationSignature
214    for MultiPolynomialStructure<RS, RSB>
215{
216    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
217        let mut terms: HashMap<Monomial, RS::Set> = HashMap::new();
218        for Term {
219            coeff: a_coeff,
220            monomial: a_monomial,
221        } in &a.terms
222        {
223            for Term {
224                coeff: b_coeff,
225                monomial: b_monomial,
226            } in &b.terms
227            {
228                let mon = Monomial::mul(a_monomial, b_monomial);
229                let coeff = self.coeff_ring().mul(a_coeff, b_coeff);
230                self.coeff_ring()
231                    .add_mut(terms.entry(mon).or_insert(self.coeff_ring().zero()), &coeff);
232            }
233        }
234        self.reduce(MultiPolynomial::new(
235            terms
236                .into_iter()
237                .map(|(monomial, coeff)| Term { coeff, monomial })
238                .collect(),
239        ))
240    }
241}
242
243impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> CommutativeMultiplicationSignature
244    for MultiPolynomialStructure<RS, RSB>
245{
246}
247
248impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> MultiplicativeMonoidSignature
249    for MultiPolynomialStructure<RS, RSB>
250{
251}
252
253impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> MultiplicativeAbsorptionMonoidSignature
254    for MultiPolynomialStructure<RS, RSB>
255{
256}
257
258impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> LeftDistributiveMultiplicationOverAddition
259    for MultiPolynomialStructure<RS, RSB>
260{
261}
262
263impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> RightDistributiveMultiplicationOverAddition
264    for MultiPolynomialStructure<RS, RSB>
265{
266}
267
268impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> SemiRingSignature
269    for MultiPolynomialStructure<RS, RSB>
270{
271}
272
273impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> RingSignature
274    for MultiPolynomialStructure<RS, RSB>
275{
276}
277
278impl<RS: CharacteristicSignature + RingEqSignature, RSB: BorrowedStructure<RS>>
279    CharacteristicSignature for MultiPolynomialStructure<RS, RSB>
280{
281    fn characteristic(&self) -> Natural {
282        self.coeff_ring().characteristic()
283    }
284}
285
286impl<RS: IntegralDomainSignature, RSB: BorrowedStructure<RS>> TryReciprocalSignature
287    for MultiPolynomialStructure<RS, RSB>
288{
289    fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
290        self.try_divide(&self.one(), a)
291    }
292}
293
294impl<RS: IntegralDomainSignature, RSB: BorrowedStructure<RS>> CancellativeMultiplicationSignature
295    for MultiPolynomialStructure<RS, RSB>
296{
297    fn try_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
298        let mut vars = HashSet::new();
299        vars.extend(a.free_vars());
300        vars.extend(b.free_vars());
301        if vars.is_empty() {
302            //a and b are constants
303            debug_assert!(a.terms.len() <= 1);
304            debug_assert!(b.terms.len() <= 1);
305            if b.terms.is_empty() {
306                None
307            } else if a.terms.is_empty() {
308                Some(self.zero())
309            } else {
310                debug_assert!(a.terms.len() == 1);
311                debug_assert!(b.terms.len() == 1);
312                debug_assert!(!self.coeff_ring().is_zero(&b.terms[0].coeff));
313                Some(MultiPolynomial::constant(
314                    self.coeff_ring()
315                        .try_divide(&a.terms[0].coeff, &b.terms[0].coeff)?,
316                ))
317            }
318        } else {
319            let var = vars.iter().next().unwrap();
320            let a_poly = self.expand(a, var);
321            let b_poly = self.expand(b, var);
322            let poly_ring = self.polynomials();
323            Some(poly_ring.evaluate(
324                &poly_ring.try_divide(&a_poly, &b_poly)?,
325                &self.var(var.clone()),
326            ))
327        }
328    }
329}
330
331impl<RS: IntegralDomainSignature, RSB: BorrowedStructure<RS>> MultiplicativeIntegralMonoidSignature
332    for MultiPolynomialStructure<RS, RSB>
333{
334}
335
336impl<RS: IntegralDomainSignature, RSB: BorrowedStructure<RS>> IntegralDomainSignature
337    for MultiPolynomialStructure<RS, RSB>
338{
339}
340
341impl<RS: FavoriteAssociateSignature + IntegralDomainSignature, RSB: BorrowedStructure<RS>>
342    FavoriteAssociateSignature for MultiPolynomialStructure<RS, RSB>
343{
344    fn factor_fav_assoc(&self, mpoly: &Self::Set) -> (Self::Set, Self::Set) {
345        match mpoly.terms.first() {
346            None => {
347                debug_assert!(self.is_zero(mpoly));
348                (self.one(), self.zero())
349            }
350            Some(first_term) => {
351                debug_assert!(!self.is_zero(mpoly));
352                let (unit, _) = self.coeff_ring().factor_fav_assoc(&first_term.coeff);
353                let unit_inv =
354                    MultiPolynomial::constant(self.coeff_ring().try_reciprocal(&unit).unwrap());
355                let unit = MultiPolynomial::constant(unit);
356                (unit, self.mul(&unit_inv, mpoly))
357            }
358        }
359    }
360}
361
362impl<RS: CharZeroRingSignature + EqSignature, RSB: BorrowedStructure<RS>> CharZeroRingSignature
363    for MultiPolynomialStructure<RS, RSB>
364{
365    fn try_to_int(&self, x: &Self::Set) -> Option<Integer> {
366        self.coeff_ring().try_to_int(&self.as_constant(x)?)
367    }
368}
369
370impl<
371    RS: EqSignature + IntegralDomainSignature + FiniteUnitsSignature,
372    RSB: BorrowedStructure<RS>,
373    B: BorrowedStructure<MultiPolynomialStructure<RS, RSB>>,
374> CountableSetSignature
375    for MultiplicativeMonoidUnitsStructure<MultiPolynomialStructure<RS, RSB>, B>
376{
377    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
378        self.list_all_elements().into_iter()
379    }
380}
381
382impl<
383    RS: EqSignature + IntegralDomainSignature + FiniteUnitsSignature,
384    RSB: BorrowedStructure<RS>,
385    B: BorrowedStructure<MultiPolynomialStructure<RS, RSB>>,
386> FiniteSetSignature for MultiplicativeMonoidUnitsStructure<MultiPolynomialStructure<RS, RSB>, B>
387{
388    fn list_all_elements(&self) -> Vec<Self::Set> {
389        self.monoid()
390            .coeff_ring()
391            .all_units()
392            .into_iter()
393            .map(MultiPolynomial::constant)
394            .collect()
395    }
396}
397
398impl<
399    RS: GreatestCommonDivisorSignature,
400    RSB: BorrowedStructure<RS>,
401    MPB: BorrowedStructure<MultiPolynomialStructure<RS, RSB>>,
402> GreatestCommonDivisorSignature for PolynomialStructure<MultiPolynomialStructure<RS, RSB>, MPB>
403{
404    fn gcd(&self, x: &Self::Set, y: &Self::Set) -> Self::Set {
405        self.gcd_by_primitive_subresultant(x.clone(), y.clone())
406    }
407}
408
409impl<RS: GreatestCommonDivisorSignature, RSB: BorrowedStructure<RS>> GreatestCommonDivisorSignature
410    for MultiPolynomialStructure<RS, RSB>
411where
412    for<'a> PolynomialStructure<MultiPolynomialStructure<RS, RSB>, &'a Self>:
413        SetSignature<Set = Polynomial<MultiPolynomial<RS::Set>>>,
414{
415    fn gcd(&self, x: &Self::Set, y: &Self::Set) -> Self::Set {
416        if let Some(free_var) = x.free_vars().into_iter().chain(y.free_vars()).next() {
417            let poly_over_self = self.polynomials();
418            let x_poly = self.expand(x, &free_var);
419            let y_poly = self.expand(y, &free_var);
420            let g_poly = poly_over_self.gcd(&x_poly, &y_poly);
421            poly_over_self.evaluate(&g_poly, &self.var(free_var))
422        } else {
423            let x = self.as_constant(x).unwrap();
424            let y = self.as_constant(y).unwrap();
425            let g = self.coeff_ring().gcd(&x, &y);
426            MultiPolynomial::constant(g)
427        }
428    }
429}
430
431impl<RS: UniqueFactorizationMonoidSignature + IntegralDomainSignature, RSB: BorrowedStructure<RS>>
432    UniqueFactorizationMonoidSignature for MultiPolynomialStructure<RS, RSB>
433{
434    type FactoredExponent = NaturalCanonicalStructure;
435
436    fn factorization_exponents(&self) -> &Self::FactoredExponent {
437        Natural::structure_ref()
438    }
439
440    fn into_factorization_exponents(self) -> Self::FactoredExponent {
441        Natural::structure()
442    }
443
444    fn try_is_irreducible(&self, _a: &Self::Set) -> Option<bool> {
445        None
446    }
447
448    fn factorization_pow(&self, a: &Self::Set, k: &Natural) -> Self::Set {
449        self.nat_pow(a, k)
450    }
451}
452
453impl<
454    RS: UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>
455        + GreatestCommonDivisorSignature
456        + CharZeroRingSignature
457        + FiniteUnitsSignature
458        + 'static,
459    RSB: BorrowedStructure<RS> + 'static,
460    MPB: BorrowedStructure<MultiPolynomialStructure<RS, RSB>>,
461> PolynomialStructure<MultiPolynomialStructure<RS, RSB>, MPB>
462where
463    PolynomialStructure<MultiPolynomialStructure<RS, RSB>, MPB>: SetSignature<Set = Polynomial<MultiPolynomial<RS::Set>>>
464        + UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>,
465    PolynomialStructure<RS, RSB>: SetSignature<Set = Polynomial<RS::Set>>
466        + UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>,
467    MultiPolynomialStructure<RS, RSB>: SetSignature<Set = MultiPolynomial<RS::Set>>
468        + UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>
469        + GreatestCommonDivisorSignature,
470{
471    pub fn factor_by_yuns_and_kroneckers_inductively(
472        &self,
473        factor_poly: impl Fn(&Polynomial<RS::Set>) -> Factored<Polynomial<RS::Set>, Natural>,
474        factor_multipoly_coeff: impl Fn(
475            &MultiPolynomial<RS::Set>,
476        ) -> Factored<MultiPolynomial<RS::Set>, Natural>,
477        mpoly: &<Self as SetSignature>::Set,
478    ) -> Factored<Polynomial<MultiPolynomial<RS::Set>>, Natural> {
479        match |mpoly: &<Self as SetSignature>::Set| -> Option<Polynomial<RS::Set>> {
480            let mut const_coeffs = vec![];
481            for coeff in self.into_coeffs(mpoly.clone()) {
482                const_coeffs.push(self.coeff_ring().as_constant(&coeff)?);
483            }
484            Some(Polynomial::from_coeffs(const_coeffs))
485        }(mpoly)
486        {
487            // It is a polynomial with multipolynomial coefficients where all coefficients are constant
488            // So we can defer to a univariate factoring algorithm
489            Some(poly) => {
490                let (unit, factors) = factor_poly(&poly).into_unit_and_powers().unwrap();
491                self.factorizations().new_unit_and_powers_unchecked(
492                    unit.apply_map_into(MultiPolynomial::constant),
493                    factors
494                        .into_iter()
495                        .map(|(factor, power)| {
496                            (factor.apply_map_into(MultiPolynomial::constant), power)
497                        })
498                        .collect(),
499                )
500            }
501            None => {
502                self.factorize_by_yuns_and_kroneckers_method(mpoly, |c| factor_multipoly_coeff(c))
503            }
504        }
505    }
506}
507
508impl<
509    RS: UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>
510        + GreatestCommonDivisorSignature
511        + CharZeroRingSignature
512        + FiniteUnitsSignature
513        + 'static,
514    RSB: BorrowedStructure<RS> + 'static,
515> MultiPolynomialStructure<RS, RSB>
516where
517    MultiPolynomialStructure<RS, RSB>: SetSignature<Set = MultiPolynomial<RS::Set>>
518        + UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>,
519    PolynomialStructure<RS, RSB>: SetSignature<Set = Polynomial<RS::Set>>
520        + UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>,
521    for<'a> PolynomialStructure<Self, &'a Self>: SetSignature<Set = Polynomial<MultiPolynomial<RS::Set>>>
522        + UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>,
523{
524    pub fn factor_by_yuns_and_kroneckers_inductively(
525        &self,
526        factor_coeff: Rc<dyn Fn(&RS::Set) -> Factored<RS::Set, Natural>>,
527        factor_poly: Rc<dyn Fn(&Polynomial<RS::Set>) -> Factored<Polynomial<RS::Set>, Natural>>,
528        mpoly: &<Self as SetSignature>::Set,
529    ) -> Factored<MultiPolynomial<RS::Set>, Natural> {
530        if self.is_zero(mpoly) {
531            Factored::Zero
532        } else {
533            #[allow(clippy::single_match_else)]
534            match mpoly.free_vars().into_iter().next() {
535                Some(free_var) => {
536                    match mpoly.homogeneous_of_degree() {
537                        HomogeneousOfDegreeResult::Homogeneous(_) => {
538                            // If mpoly is homogeneous we can eliminate a variable right away
539                            let dehom_mpoly = self.partial_evaluate(
540                                mpoly,
541                                HashMap::from([(free_var.clone(), self.coeff_ring().one())]),
542                            );
543                            let (unit, factors) = self
544                                .factor_by_yuns_and_kroneckers_inductively(
545                                    factor_coeff.clone(),
546                                    factor_poly.clone(),
547                                    &dehom_mpoly,
548                                )
549                                .into_unit_and_powers()
550                                .unwrap();
551
552                            self.factorizations().new_unit_and_powers_unchecked(
553                                self.homogenize(&unit, &free_var),
554                                factors
555                                    .into_iter()
556                                    .map(|(factor, power)| {
557                                        (self.homogenize(&factor, &free_var), power)
558                                    })
559                                    .collect(),
560                            )
561                        }
562                        HomogeneousOfDegreeResult::No => {
563                            // Not homogeneous but
564                            // There exists a free variable
565                            // So turn ourself into a polynomial with respect to that free variable
566                            let poly_over_self = self.polynomials();
567                            let expanded_poly = self.expand(mpoly, &free_var);
568                            let free_var = self.var(free_var);
569                            let (unit, factors) = poly_over_self
570                                .factor_by_yuns_and_kroneckers_inductively(
571                                    factor_poly.as_ref(),
572                                    |c| {
573                                        self.factor_by_yuns_and_kroneckers_inductively(
574                                            factor_coeff.clone(),
575                                            factor_poly.clone(),
576                                            c,
577                                        )
578                                    },
579                                    &expanded_poly,
580                                )
581                                .into_unit_and_powers()
582                                .unwrap();
583
584                            self.factorizations().new_unit_and_powers_unchecked(
585                                poly_over_self.evaluate(&unit, &free_var),
586                                factors
587                                    .into_iter()
588                                    .map(|(factor, power)| {
589                                        (poly_over_self.evaluate(&factor, &free_var), power)
590                                    })
591                                    .collect(),
592                            )
593                        }
594                        HomogeneousOfDegreeResult::Zero => unreachable!(),
595                    }
596                }
597                None => {
598                    // Just an element of the coefficient ring
599                    let value = self.as_constant(mpoly).unwrap();
600                    if let Some((unit, factors)) = factor_coeff(&value).into_unit_and_powers() {
601                        self.factorizations().new_unit_and_powers_unchecked(
602                            MultiPolynomial::constant(unit),
603                            factors
604                                .into_iter()
605                                .map(|(factor, power)| (MultiPolynomial::constant(factor), power))
606                                .collect(),
607                        )
608                    } else {
609                        Factored::Zero
610                    }
611                }
612            }
613        }
614    }
615}
616
617impl<RS: RingEqSignature, RSB: BorrowedStructure<RS>> MultiPolynomialStructure<RS, RSB> {
618    pub fn reduce(&self, p: MultiPolynomial<RS::Set>) -> MultiPolynomial<RS::Set> {
619        MultiPolynomial::new(
620            p.terms
621                .into_iter()
622                .filter(|Term { coeff, .. }| !self.coeff_ring().is_zero(coeff))
623                .collect(),
624        )
625    }
626
627    pub fn var_pow(&self, v: Variable, k: usize) -> MultiPolynomial<RS::Set> {
628        MultiPolynomial {
629            terms: vec![Term {
630                coeff: self.coeff_ring().one(),
631                monomial: Monomial::new(vec![VariablePower { var: v, pow: k }]),
632            }],
633        }
634    }
635
636    pub fn var(&self, v: Variable) -> MultiPolynomial<RS::Set> {
637        self.var_pow(v, 1)
638    }
639
640    pub fn as_constant(&self, p: &MultiPolynomial<RS::Set>) -> Option<RS::Set> {
641        if p.terms.is_empty() {
642            Some(self.coeff_ring().zero())
643        } else if p.terms.len() == 1 {
644            let Term { coeff, monomial } = &p.terms[0];
645            if monomial == &Monomial::one() {
646                Some(coeff.clone())
647            } else {
648                None
649            }
650        } else {
651            None
652        }
653    }
654
655    pub fn degree(&self, p: &MultiPolynomial<RS::Set>) -> Option<usize> {
656        p.terms.iter().map(Term::degree).max()
657    }
658
659    pub fn split_by_degree(
660        &self,
661        p: MultiPolynomial<RS::Set>,
662    ) -> HashMap<usize, MultiPolynomial<RS::Set>> {
663        let mut p_by_deg = HashMap::new();
664        for term in p.terms {
665            // let term = MultiPolynomial::new(vec![term]);
666            let deg = term.degree();
667            p_by_deg.entry(deg).or_insert_with(Vec::new);
668            p_by_deg.get_mut(&deg).unwrap().push(term);
669        }
670        p_by_deg
671            .into_iter()
672            .map(|(d, t)| (d, MultiPolynomial { terms: t }))
673            .collect()
674    }
675
676    pub fn homogenize(
677        &self,
678        p: &MultiPolynomial<RS::Set>,
679        v: &Variable,
680    ) -> MultiPolynomial<RS::Set> {
681        if self.is_zero(p) {
682            self.zero()
683        } else {
684            let d = self.degree(p).unwrap();
685            let h = MultiPolynomial::new(
686                p.terms
687                    .iter()
688                    .map(|Term { coeff, monomial }| Term {
689                        coeff: coeff.clone(),
690                        monomial: monomial.homogenize(d, v),
691                    })
692                    .collect(),
693            );
694            debug_assert!(h.check_invariants().is_ok());
695            h
696        }
697    }
698
699    pub fn expand(
700        &self,
701        p: &MultiPolynomial<RS::Set>,
702        v: &Variable,
703    ) -> Polynomial<MultiPolynomial<RS::Set>> {
704        let mut coeffs = vec![];
705        for Term { coeff, monomial } in &p.terms {
706            let k = monomial.get_var_pow(v);
707            while coeffs.len() <= k {
708                coeffs.push(self.zero());
709            }
710            self.add_mut(
711                &mut coeffs[k],
712                &MultiPolynomial {
713                    terms: vec![Term {
714                        coeff: coeff.clone(),
715                        monomial: Monomial::new(
716                            monomial
717                                .clone()
718                                .prod
719                                .into_iter()
720                                .filter(|VariablePower { var, pow: _pow }| var != v)
721                                .collect(),
722                        ),
723                    }],
724                },
725            );
726        }
727        Polynomial::from_coeffs(coeffs)
728    }
729
730    pub fn partial_evaluate(
731        &self,
732        poly: &MultiPolynomial<RS::Set>,
733        values: HashMap<Variable, impl Borrow<RS::Set>>,
734    ) -> MultiPolynomial<RS::Set> {
735        let mut values = values
736            .into_iter()
737            .map(|(v, a)| (v, MultiPolynomial::constant(a.borrow().clone())))
738            .collect::<HashMap<_, _>>();
739
740        let free_vars = poly.free_vars();
741        for free_var in free_vars {
742            if !values.contains_key(&free_var) {
743                values.insert(free_var.clone(), self.var(free_var));
744            }
745        }
746        MultiPolynomialStructure::new(self.clone()).evaluate(
747            &poly.apply_map(|x| MultiPolynomial::constant(x.clone())),
748            values,
749        )
750    }
751
752    pub fn evaluate(
753        &self,
754        poly: &MultiPolynomial<RS::Set>,
755        values: HashMap<Variable, impl Borrow<RS::Set>>,
756    ) -> RS::Set {
757        self.coeff_ring().sum(
758            poly.terms
759                .iter()
760                .map(|Term { coeff, monomial }| {
761                    self.coeff_ring()
762                        .mul(coeff, &monomial.evaluate(self.coeff_ring(), &values))
763                })
764                .collect(),
765        )
766    }
767}
768
769impl<R: MetaType> MetaType for MultiPolynomial<R>
770where
771    R::Signature: RingEqSignature,
772{
773    type Signature = MultiPolynomialStructure<R::Signature, R::Signature>;
774
775    fn structure() -> Self::Signature {
776        MultiPolynomialStructure::new(R::structure())
777    }
778}
779
780impl<R: MetaType> Display for MultiPolynomial<R>
781where
782    R::Signature: RingEqSignature + ToStringSignature,
783{
784    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
785        write!(f, "{}", Self::structure().to_string(self))
786    }
787}
788
789impl<R: MetaType> PartialEq for MultiPolynomial<R>
790where
791    R::Signature: RingEqSignature,
792{
793    fn eq(&self, other: &Self) -> bool {
794        Self::structure().equal(self, other)
795    }
796}
797
798impl<R: MetaType> Eq for MultiPolynomial<R> where R::Signature: RingEqSignature {}
799
800impl<R: MetaType> MultiPolynomial<R>
801where
802    R::Signature: RingEqSignature,
803{
804    pub fn reduce(self) -> Self {
805        Self::structure().reduce(self)
806    }
807
808    pub fn var(v: Variable) -> Self {
809        Self::structure().var(v)
810    }
811
812    pub fn as_constant(&self) -> Option<R> {
813        Self::structure().as_constant(self)
814    }
815
816    pub fn degree(&self) -> Option<usize> {
817        Self::structure().degree(self)
818    }
819
820    pub fn homogenize(&self, v: &Variable) -> Self {
821        Self::structure().homogenize(self, v)
822    }
823
824    pub fn expand(&self, v: &Variable) -> Polynomial<Self> {
825        Self::structure().expand(self, v)
826    }
827
828    pub fn evaluate(&self, values: HashMap<Variable, impl Borrow<R>>) -> R {
829        Self::structure().evaluate(self, values)
830    }
831}
832
833#[cfg(test)]
834mod tests {
835    use crate::structure::IntoErgonomic;
836
837    use algebraeon_nzq::*;
838
839    use super::*;
840
841    #[test]
842    fn test_monomial_ordering() {
843        let xv = Variable::new(String::from("x"));
844        let yv = Variable::new(String::from("y"));
845
846        let xx = Monomial::new(vec![VariablePower {
847            var: xv.clone(),
848            pow: 2,
849        }]);
850        let yy = Monomial::new(vec![VariablePower {
851            var: yv.clone(),
852            pow: 2,
853        }]);
854        let xy = Monomial::new(vec![
855            VariablePower {
856                var: xv.clone(),
857                pow: 1,
858            },
859            VariablePower {
860                var: yv.clone(),
861                pow: 1,
862            },
863        ]);
864        let x = Monomial::new(vec![VariablePower {
865            var: xv.clone(),
866            pow: 1,
867        }]);
868        let y = Monomial::new(vec![VariablePower {
869            var: yv.clone(),
870            pow: 1,
871        }]);
872        let one = Monomial::one();
873
874        {
875            let terms = vec![
876                xx.clone(),
877                xy.clone(),
878                x.clone(),
879                yy.clone(),
880                y.clone(),
881                one.clone(),
882            ];
883            let mut sorted_terms = terms.clone();
884            sorted_terms.sort_by(Monomial::lexicographic_order);
885
886            assert_eq!(terms, sorted_terms);
887        }
888
889        {
890            let terms = vec![
891                xx.clone(),
892                xy.clone(),
893                yy.clone(),
894                x.clone(),
895                y.clone(),
896                one.clone(),
897            ];
898            let mut sorted_terms = terms.clone();
899            sorted_terms.sort_by(Monomial::graded_lexicographic_order);
900
901            assert_eq!(terms, sorted_terms);
902        }
903    }
904
905    #[test]
906    fn test_reduction() {
907        let x = MultiPolynomial::<Integer>::var(Variable::new(String::from("x")));
908        let f = MultiPolynomial::sum(vec![&x, &MultiPolynomial::neg(&x)]);
909        assert_eq!(f.terms.len(), 0);
910
911        let x = MultiPolynomial::<Integer>::var(Variable::new(String::from("x")));
912        let y = MultiPolynomial::<Integer>::var(Variable::new(String::from("y")));
913        let g = MultiPolynomial::sum(vec![&x, &y]);
914        let h = MultiPolynomial::sum(vec![&x, &MultiPolynomial::neg(&y)]);
915        let f = MultiPolynomial::product(vec![&g, &h]);
916        println!("g = {}", g);
917        println!("h = {}", h);
918        println!("f = {}", f);
919        assert_eq!(f.terms.len(), 2);
920    }
921
922    #[test]
923    fn test_divideision() {
924        let x = MultiPolynomial::<Integer>::var(Variable::new(String::from("x")));
925        let y = MultiPolynomial::<Integer>::var(Variable::new(String::from("y")));
926
927        let f = MultiPolynomial::sum(vec![
928            &MultiPolynomial::product(vec![&x, &x]),
929            &MultiPolynomial::neg(&MultiPolynomial::product(vec![&y, &y])),
930        ]);
931        let g = MultiPolynomial::sum(vec![&x, &MultiPolynomial::neg(&y)]);
932        match MultiPolynomial::try_divide(&f, &g) {
933            Some(h) => {
934                assert_eq!(f, MultiPolynomial::mul(&g, &h));
935            }
936            None => panic!(),
937        }
938
939        let f = MultiPolynomial::sum(vec![
940            &MultiPolynomial::product(vec![&x, &x]),
941            &MultiPolynomial::neg(&MultiPolynomial::product(vec![&y, &y])),
942        ]);
943        let g = MultiPolynomial::zero();
944        assert!(MultiPolynomial::try_divide(&f, &g).is_none());
945
946        let f = MultiPolynomial::sum(vec![
947            &MultiPolynomial::product(vec![&x, &x]),
948            &MultiPolynomial::neg(&MultiPolynomial::product(vec![&y, &y])),
949        ]);
950        let g = MultiPolynomial::sum(vec![&x]);
951        assert!(MultiPolynomial::try_divide(&f, &g).is_none());
952    }
953
954    #[test]
955    fn test_elems() {
956        let x = &MultiPolynomial::<Integer>::var(Variable::new("x")).into_ergonomic();
957        let y = &MultiPolynomial::<Integer>::var(Variable::new("y")).into_ergonomic();
958        let z = &MultiPolynomial::<Integer>::var(Variable::new("z")).into_ergonomic();
959
960        let f = x + y + z;
961        let g = x - y + z;
962
963        let h = (&f * &g) / &f;
964        h.into_verbose().check_invariants().unwrap();
965
966        println!("f = {}", f);
967        println!("g = {}", g);
968        println!("fg = {}", &f * &g);
969        println!("fg/f = {}", (&f * &g) / &f);
970
971        assert_eq!((&f * &g) / &f, g);
972    }
973
974    // #[test]
975    // fn test_gcd_and_factor() {
976    //     let x = &MultiPolynomial::<Integer>::var(Variable::new("x")).into_ergonomic();
977    //     let y = &MultiPolynomial::<Integer>::var(Variable::new("y")).into_ergonomic();
978
979    //     let a = y - x;
980    //     let b = y.pow(2) - x.pow(3);
981    //     let c = y.pow(3) * x + 5 + y;
982    //     let d = x.pow(5) * y.pow(4) - 1;
983    //     let e = y.pow(4) - x.pow(4);
984    //     let f = 24 * (y - x);
985
986    //     assert!(a.clone().into_verbose().is_irreducible());
987    //     assert!(b.clone().into_verbose().is_irreducible());
988    //     assert!(c.clone().into_verbose().is_irreducible());
989    //     assert!(d.clone().into_verbose().is_irreducible());
990    //     assert!(!e.clone().into_verbose().is_irreducible());
991    //     assert!(!f.clone().into_verbose().is_irreducible());
992
993    //     assert!(MultiPolynomial::are_associate(
994    //         &b.clone().into_verbose(),
995    //         &MultiPolynomial::gcd(&(&a * &b).into_verbose(), &(&b * &c).into_verbose())
996    //     ));
997
998    //     assert!(MultiPolynomial::are_associate(
999    //         &(&b * &c).into_verbose(),
1000    //         &MultiPolynomial::gcd(
1001    //             &(&a * &b * &c).into_verbose(),
1002    //             &(&b * &c * &d).into_verbose()
1003    //         )
1004    //     ));
1005    // }
1006}
algebraeon_rings/polynomial/multipoly_structure.rs

algebraeon_rings/polynomial/
multipoly_structure.rs
