feanor_math/rings/poly/
mod.rs

1use std::collections::HashMap;
2
3use crate::divisibility::*;
4use crate::ring::*;
5use crate::homomorphism::*;
6use crate::wrapper::RingElementWrapper;
7
8///
9/// Contains [`dense_poly::DensePolyRing`], an implementation of univariate polynomials
10/// based on dense coefficient storage.
11/// 
12pub mod dense_poly;
13///
14/// Contains [`sparse_poly::SparsePolyRing`], an implementation of univariate polynomials
15/// based on sparse coefficient storage.
16/// 
17pub mod sparse_poly;
18
19///
20/// Trait for all rings that represent the polynomial ring `R[X]` with
21/// any base ring R.
22/// 
23/// Currently, the two implementations of this type of ring are [`dense_poly::DensePolyRing`]
24/// and [`sparse_poly::SparsePolyRing`].
25/// 
26pub trait PolyRing: RingExtension {
27
28    /// 
29    /// Type of the iterator over all non-zero terms of a polynomial in this ring,
30    /// as returned by [`PolyRing::terms()`].
31    /// 
32    type TermsIterator<'a>: Iterator<Item = (&'a El<Self::BaseRing>, usize)>
33        where Self: 'a;
34
35    ///
36    /// Returns the indeterminate `X` generating this polynomial ring.
37    /// 
38    fn indeterminate(&self) -> Self::Element;
39
40    ///
41    /// Returns all the nonzero terms of the given polynomial.
42    /// 
43    /// If the base ring is only approximate, it is valid to return "zero" terms,
44    /// whatever that actually means.
45    /// 
46    fn terms<'a>(&'a self, f: &'a Self::Element) -> Self::TermsIterator<'a>;
47    
48    ///
49    /// Adds the given terms to the given polynomial.
50    /// 
51    fn add_assign_from_terms<I>(&self, lhs: &mut Self::Element, rhs: I)
52        where I: IntoIterator<Item = (El<Self::BaseRing>, usize)>
53    {
54        let self_ring = RingRef::new(self);
55        self.add_assign(lhs, self_ring.sum(
56            rhs.into_iter().map(|(c, i)| self.mul(self.from(c), self_ring.pow(self.indeterminate(), i)))
57        ));
58    }
59
60    ///
61    /// Multiplies the given polynomial with `X^rhs_power`.
62    /// 
63    fn mul_assign_monomial(&self, lhs: &mut Self::Element, rhs_power: usize) {
64        self.mul_assign(lhs, RingRef::new(self).pow(self.indeterminate(), rhs_power));
65    }
66
67    ///
68    /// Returns the coefficient of `f` that corresponds to the monomial `X^i`.
69    /// 
70    fn coefficient_at<'a>(&'a self, f: &'a Self::Element, i: usize) -> &'a El<Self::BaseRing>;
71
72    ///
73    /// Returns the degree of the polynomial `f`, i.e. the value `d` such that `f` can be written as
74    /// `f(X) = a0 + a1 * X + a2 * X^2 + ... + ad * X^d`. Returns `None` if `f` is zero.
75    /// 
76    fn degree(&self, f: &Self::Element) -> Option<usize>;
77
78    ///
79    /// Compute the euclidean division by a monic polynomial `rhs`.
80    /// 
81    /// Concretely, if `rhs` is a monic polynomial (polynomial with highest coefficient equal to 1), then
82    /// there exist unique `q, r` such that `lhs = rhs * q + r` and `deg(r) < deg(rhs)`. These are returned.
83    /// This function panics if `rhs` is not monic.
84    /// 
85    fn div_rem_monic(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element);
86
87    ///
88    /// Truncates the monomials of the given polynomial from the given position on, i.e.
89    /// computes the remainder of the polynomial division of `lhs` by `X^truncated_at_inclusive`.
90    /// 
91    fn truncate_monomials(&self, lhs: &mut Self::Element, truncated_at_inclusive: usize) {
92        *lhs = RingRef::new(self).from_terms(self.terms(lhs).filter(|(_, i)| *i < truncated_at_inclusive).map(|(c, i)| (self.base_ring().clone_el(c), i)))
93    }
94    
95    ///
96    /// Computes the polynomial whose coefficients are the images of the coefficients of `el`
97    /// under the given homomorphism.
98    /// 
99    /// This is used to implement [`PolyRingStore::lifted_hom()`].
100    /// 
101    fn map_terms<P, H>(&self, from: &P, el: &P::Element, hom: H) -> Self::Element
102        where P: ?Sized + PolyRing,
103            H: Homomorphism<<P::BaseRing as RingStore>::Type, <Self::BaseRing as RingStore>::Type>
104    {
105        assert!(self.base_ring().get_ring() == hom.codomain().get_ring());
106        assert!(from.base_ring().get_ring() == hom.domain().get_ring());
107        RingRef::new(self).from_terms(from.terms(el).map(|(c, i)| (hom.map_ref(c), i)))
108    }
109    
110    ///
111    /// Possibly divides all coefficients of the polynomial by a common factor,
112    /// in order to make them "smaller". 
113    /// 
114    /// In cases where we mainly care about polynomials up to scaling by non-zero 
115    /// divisors of the base ring, balancing intermediate polynomials can improve performance.
116    /// 
117    /// For more details on balancing, see [`DivisibilityRing::balance_factor()`].
118    /// 
119    #[stability::unstable(feature = "enable")]
120    fn balance_poly(&self, f: &mut Self::Element) -> Option<El<Self::BaseRing>>
121        where <Self::BaseRing as RingStore>::Type: DivisibilityRing
122    {
123        let balance_factor = self.base_ring().get_ring().balance_factor(self.terms(f).map(|(c, _)| c));
124        if let Some(balance_factor) = &balance_factor {
125            *f = RingRef::new(self).from_terms(self.terms(f).map(|(c, i)| (self.base_ring().checked_div(c, &balance_factor).unwrap(), i)));
126        }
127        return balance_factor;
128    }
129
130    ///
131    /// Evaluates the given polynomial at the given values.
132    /// 
133    /// # Example
134    /// ```rust
135    /// # use feanor_math::ring::*;
136    /// # use feanor_math::rings::poly::*;
137    /// # use feanor_math::primitive_int::*; 
138    /// let ring = dense_poly::DensePolyRing::new(StaticRing::<i32>::RING, "X");
139    /// let x = ring.indeterminate();
140    /// let poly = ring.add(ring.clone_el(&x), ring.pow(x, 2));
141    /// assert_eq!(12, ring.evaluate(&poly, &3, &StaticRing::<i32>::RING.identity()));
142    /// ```
143    /// 
144    fn evaluate<R, H>(&self, f: &Self::Element, value: &R::Element, hom: H) -> R::Element
145        where R: ?Sized + RingBase,
146            H: Homomorphism<<Self::BaseRing as RingStore>::Type, R>
147    {
148        hom.codomain().sum(self.terms(f).map(|(c, i)| {
149            let result = hom.codomain().pow(hom.codomain().clone_el(value), i);
150            hom.mul_ref_snd_map(result, c)
151        }))
152    }
153}
154
155///
156/// [`RingStore`] corresponding to [`PolyRing`].
157/// 
158pub trait PolyRingStore: RingStore
159    where Self::Type: PolyRing
160{
161    delegate!{ PolyRing, fn indeterminate(&self) -> El<Self> }
162    delegate!{ PolyRing, fn degree(&self, f: &El<Self>) -> Option<usize> }
163    delegate!{ PolyRing, fn mul_assign_monomial(&self, lhs: &mut El<Self>, rhs_power: usize) -> () }
164    delegate!{ PolyRing, fn div_rem_monic(&self, lhs: El<Self>, rhs: &El<Self>) -> (El<Self>, El<Self>) }
165    delegate!{ PolyRing, fn truncate_monomials(&self, lhs: &mut El<Self>, truncated_at_degree: usize) -> () }
166
167    ///
168    /// See [`PolyRing::coefficient_at()`].
169    /// 
170    fn coefficient_at<'a>(&'a self, f: &'a El<Self>, i: usize) -> &'a El<<Self::Type as RingExtension>::BaseRing> {
171        self.get_ring().coefficient_at(f, i)
172    }
173
174    ///
175    /// See [`PolyRing::terms()`].
176    /// 
177    fn terms<'a>(&'a self, f: &'a El<Self>) -> <Self::Type as PolyRing>::TermsIterator<'a> {
178        self.get_ring().terms(f)
179    }
180
181    ///
182    /// Computes the polynomial from the given terms.
183    /// 
184    /// If the iterator gives a term for the same monomial `X^i` multiple times,
185    /// the corresponding coefficients will be summed up.
186    /// 
187    fn from_terms<I>(&self, iter: I) -> El<Self>
188        where I: IntoIterator<Item = (El<<Self::Type as RingExtension>::BaseRing>, usize)>,
189    {
190        let mut result = self.zero();
191        self.get_ring().add_assign_from_terms(&mut result, iter);
192        return result;
193    }
194
195    ///
196    /// Computes the polynomial from the given terms.
197    /// 
198    /// As opposed to [`PolyRingStore::from_terms()`], the iterator may return errors,
199    /// in which case the computation is aborted and the first error is returned.
200    /// 
201    fn try_from_terms<E, I>(&self, iter: I) -> Result<El<Self>, E>
202        where I: IntoIterator<Item = Result<(El<<Self::Type as RingExtension>::BaseRing>, usize), E>>,
203    {
204        let mut result = self.zero();
205        let mut error = None;
206        self.get_ring().add_assign_from_terms(&mut result, iter.into_iter().map(|t| match t {
207            Ok(t) => Some(t),
208            Err(e) => { error = Some(e); None }
209        }).take_while(|t| t.is_some()).map(|t| t.unwrap()));
210        if let Some(e) = error {
211            return Err(e);
212        } else {
213            return Ok(result);
214        }
215    }
216
217    ///
218    /// Returns a reference to the leading coefficient of the given polynomial, or `None` if the
219    /// polynomial is zero.
220    /// 
221    fn lc<'a>(&'a self, f: &'a El<Self>) -> Option<&'a El<<Self::Type as RingExtension>::BaseRing>> {
222        Some(self.coefficient_at(f, self.degree(f)?))
223    }
224    
225    ///
226    /// Divides each coefficient of this polynomial by its leading coefficient, thus making it monic.
227    /// 
228    /// Panics if the leading coefficient is not a unit.
229    /// 
230    /// # Example
231    /// ```rust
232    /// # use feanor_math::ring::*;
233    /// # use feanor_math::rings::poly::*;
234    /// # use feanor_math::assert_el_eq;
235    /// # use feanor_math::rings::poly::dense_poly::*;
236    /// # use feanor_math::primitive_int::*;
237    /// let P = DensePolyRing::new(StaticRing::<i64>::RING, "X");
238    /// let f = P.from_terms([(6, 0), (3, 1)].into_iter());
239    /// assert_el_eq!(P, P.from_terms([(2, 0), (1, 1)].into_iter()), P.normalize(f));
240    /// ```
241    /// 
242    fn normalize(&self, mut f: El<Self>) -> El<Self>
243        where <<Self::Type as RingExtension>::BaseRing as RingStore>::Type: DivisibilityRing + Domain
244    {
245        if self.is_zero(&f) {
246            return f;
247        } else if let Some(inv_lc) = self.base_ring().invert(self.lc(&f).unwrap()) {
248            self.inclusion().mul_assign_ref_map(&mut f, &inv_lc);
249            return f;
250        } else {
251            let lc = self.lc(&f).unwrap();
252            return self.from_terms(self.terms(&f).map(|(c, i)| (self.base_ring().checked_div(c, &lc).unwrap(), i)));
253        }
254    }
255
256    ///
257    /// See [`PolyRing::evaluate()`].
258    /// 
259    fn evaluate<R, H>(&self, f: &El<Self>, value: &R::Element, hom: H) -> R::Element
260        where R: ?Sized + RingBase,
261            H: Homomorphism<<<Self::Type as RingExtension>::BaseRing as RingStore>::Type, R>
262    {
263        self.get_ring().evaluate(f, value, hom)
264    }
265
266    ///
267    /// Lifts the given homomorphism of base rings `S -> R` to the corresponding
268    /// homomorphism of polynomial rings `S[X] -> R[X]`.
269    /// 
270    /// As opposed to [`PolyRingStore::lifted_hom()`], this transfers the ownership
271    /// of `self` into the homomorphism object.
272    /// 
273    fn into_lifted_hom<P, H>(self, from: P, hom: H) -> CoefficientHom<P, Self, H>
274        where P: RingStore,
275            P::Type: PolyRing,
276            H: Homomorphism<<<P::Type as RingExtension>::BaseRing as RingStore>::Type, <<Self::Type as RingExtension>::BaseRing as RingStore>::Type>
277    {
278        CoefficientHom {
279            from: from,
280            to: self,
281            hom: hom
282        }
283    }
284
285    ///
286    /// Lifts the given homomorphism of base rings `S -> R` to the corresponding
287    /// homomorphism of polynomial rings `S[X] -> R[X]`.
288    /// 
289    fn lifted_hom<'a, P, H>(&'a self, from: P, hom: H) -> CoefficientHom<P, &'a Self, H>
290        where P: RingStore,
291            P::Type: PolyRing,
292            H: Homomorphism<<<P::Type as RingExtension>::BaseRing as RingStore>::Type, <<Self::Type as RingExtension>::BaseRing as RingStore>::Type>
293    {
294        self.into_lifted_hom(from, hom)
295    }
296    
297    ///
298    /// Invokes the function with a wrapped version of the indeterminate of this poly ring.
299    /// Use for convenient creation of polynomials.
300    /// 
301    /// Note however that [`PolyRingStore::from_terms()`] might be more performant.
302    /// 
303    /// If the number of polynomials to be created is known at compile time, it is more convenient
304    /// to instead use [`PolyRingStore::with_wrapped_indeterminate()`].
305    /// 
306    /// # Example
307    /// ```rust
308    /// use feanor_math::assert_el_eq;
309    /// use feanor_math::ring::*;
310    /// use feanor_math::rings::poly::*;
311    /// use feanor_math::homomorphism::*;
312    /// use feanor_math::rings::zn::zn_64::*;
313    /// use feanor_math::rings::poly::dense_poly::*;
314    /// let base_ring = Zn::new(7);
315    /// let poly_ring = DensePolyRing::new(base_ring, "X");
316    /// let f_version1 = poly_ring.from_terms([(base_ring.int_hom().map(3), 0), (base_ring.int_hom().map(2), 1), (base_ring.one(), 3)].into_iter());
317    /// let f_version2 = poly_ring.with_wrapped_indeterminate_dyn(|x| [3 + 2 * x + x.pow_ref(3)]).into_iter().next().unwrap();
318    /// assert_el_eq!(poly_ring, f_version1, f_version2);
319    /// ```
320    /// 
321    #[stability::unstable(feature = "enable")]
322    fn with_wrapped_indeterminate_dyn<'a, F, T>(&'a self, f: F) -> Vec<El<Self>>
323        where F: FnOnce(&RingElementWrapper<&'a Self>) -> T,
324            T: IntoIterator<Item = RingElementWrapper<&'a Self>>
325    {
326        let wrapped_indet = RingElementWrapper::new(self, self.indeterminate());
327        f(&wrapped_indet).into_iter().map(|f| f.unwrap()).collect()
328    }
329
330    ///
331    /// Invokes the function with a wrapped version of the indeterminate of this poly ring.
332    /// Use for convenient creation of polynomials.
333    /// 
334    /// Note however that [`PolyRingStore::from_terms()`] might be more performant.
335    /// 
336    /// If the number of polynomials to be created is not known at compile time, instead
337    /// use [`PolyRingStore::with_wrapped_indeterminate_dyn()`].
338    /// 
339    /// # Example
340    /// ```rust
341    /// use feanor_math::assert_el_eq;
342    /// use feanor_math::ring::*;
343    /// use feanor_math::rings::poly::*;
344    /// use feanor_math::homomorphism::*;
345    /// use feanor_math::rings::zn::zn_64::*;
346    /// use feanor_math::rings::poly::dense_poly::*;
347    /// let base_ring = Zn::new(7);
348    /// let poly_ring = DensePolyRing::new(base_ring, "X");
349    /// let f_version1 = poly_ring.from_terms([(base_ring.int_hom().map(3), 0), (base_ring.int_hom().map(2), 1), (base_ring.one(), 3)].into_iter());
350    /// let [f_version2] = poly_ring.with_wrapped_indeterminate(|x| [3 + 2 * x + x.pow_ref(3)]);
351    /// assert_el_eq!(poly_ring, f_version1, f_version2);
352    /// ```
353    /// 
354    fn with_wrapped_indeterminate<'a, F, const M: usize>(&'a self, f: F) -> [El<Self>; M]
355        where F: FnOnce(&RingElementWrapper<&'a Self>) -> [RingElementWrapper<&'a Self>; M]
356    {
357        let wrapped_indet = RingElementWrapper::new(self, self.indeterminate());
358        let mut result_it = f(&wrapped_indet).into_iter();
359        return std::array::from_fn(|_| result_it.next().unwrap().unwrap());
360    }
361    
362    ///
363    /// See [`PolyRing::balance_poly()`].
364    /// 
365    #[stability::unstable(feature = "enable")]
366    fn balance_poly(&self, f: &mut El<Self>) -> Option<El<<Self::Type as RingExtension>::BaseRing>>
367        where <<Self::Type as RingExtension>::BaseRing as RingStore>::Type: DivisibilityRing
368    {
369        self.get_ring().balance_poly(f)
370    }
371}
372
373///
374/// Homomorphism between two polynomial rings, induced by a homomorphism between their coefficient rings.
375/// 
376/// This is the type returned by [`PolyRingStore::lifted_hom()`] and [`PolyRingStore::into_lifted_hom()`],
377/// which should be used to create an instance of this type.
378/// 
379pub struct CoefficientHom<PFrom, PTo, H>
380    where PFrom: RingStore,
381        PTo: RingStore,
382        PFrom::Type: PolyRing,
383        PTo::Type: PolyRing,
384        H: Homomorphism<<<PFrom::Type as RingExtension>::BaseRing as RingStore>::Type, <<PTo::Type as RingExtension>::BaseRing as RingStore>::Type>
385{
386    from: PFrom,
387    to: PTo,
388    hom: H
389}
390
391impl<PFrom, PTo, H> Homomorphism<PFrom::Type, PTo::Type> for CoefficientHom<PFrom, PTo, H>
392    where PFrom: RingStore,
393        PTo: RingStore,
394        PFrom::Type: PolyRing,
395        PTo::Type: PolyRing,
396        H: Homomorphism<<<PFrom::Type as RingExtension>::BaseRing as RingStore>::Type, <<PTo::Type as RingExtension>::BaseRing as RingStore>::Type>
397{
398    type DomainStore = PFrom;
399    type CodomainStore = PTo;
400
401    fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
402        &self.to
403    }
404
405    fn domain<'a>(&'a self) -> &'a Self::DomainStore {
406        &self.from
407    }
408
409    fn map(&self, x: <PFrom::Type as RingBase>::Element) -> <PTo::Type as RingBase>::Element {
410        self.map_ref(&x)
411    }
412
413    fn map_ref(&self, x: &<PFrom::Type as RingBase>::Element) -> <PTo::Type as RingBase>::Element {
414        self.to.get_ring().map_terms(self.from.get_ring(), x, &self.hom)
415    }
416}
417
418impl<R: RingStore> PolyRingStore for R
419    where R::Type: PolyRing
420{}
421
422///
423/// Computes the formal derivative of a polynomial.
424/// 
425/// The formal derivative is the linear map defined by
426/// ```text
427///   X^k  ->  k * X^(k - 1)
428/// ```
429/// 
430pub fn derive_poly<P>(poly_ring: P, poly: &El<P>) -> El<P>
431    where P: PolyRingStore,
432        P::Type: PolyRing
433{
434    poly_ring.from_terms(poly_ring.terms(poly)
435        .filter(|(_, i)| *i > 0)
436        .map(|(c, i)| (poly_ring.base_ring().int_hom().mul_ref_fst_map(c, i.try_into().unwrap()), i - 1))
437    )
438}
439
440pub mod generic_impls {
441    use crate::ring::*;
442    use super::PolyRing;
443    use crate::homomorphism::*;
444
445    #[allow(type_alias_bounds)]
446    #[stability::unstable(feature = "enable")]
447    pub type Homomorphism<P1: PolyRing, P2: PolyRing> = <<P2::BaseRing as RingStore>::Type as CanHomFrom<<P1::BaseRing as RingStore>::Type>>::Homomorphism;
448
449    #[stability::unstable(feature = "enable")]
450    pub fn has_canonical_hom<P1: PolyRing, P2: PolyRing>(from: &P1, to: &P2) -> Option<Homomorphism<P1, P2>> 
451        where <P2::BaseRing as RingStore>::Type: CanHomFrom<<P1::BaseRing as RingStore>::Type>
452    {
453        to.base_ring().get_ring().has_canonical_hom(from.base_ring().get_ring())
454    }
455
456    #[stability::unstable(feature = "enable")]
457    pub fn map_in<P1: PolyRing, P2: PolyRing>(from: &P1, to: &P2, el: P1::Element, hom: &Homomorphism<P1, P2>) -> P2::Element
458        where <P2::BaseRing as RingStore>::Type: CanHomFrom<<P1::BaseRing as RingStore>::Type>
459    {
460        let mut result = to.zero();
461        to.add_assign_from_terms(&mut result, from.terms(&el).map(|(c, i)| (to.base_ring().get_ring().map_in(from.base_ring().get_ring(), from.base_ring().clone_el(c), hom), i)));
462        return result;
463    }
464
465    #[allow(type_alias_bounds)]
466    #[stability::unstable(feature = "enable")]
467    pub type Isomorphism<P1: PolyRing, P2: PolyRing> = <<P2::BaseRing as RingStore>::Type as CanIsoFromTo<<P1::BaseRing as RingStore>::Type>>::Isomorphism;
468
469    #[stability::unstable(feature = "enable")]
470    pub fn map_out<P1: PolyRing, P2: PolyRing>(from: &P1, to: &P2, el: P2::Element, iso: &Isomorphism<P1, P2>) -> P1::Element
471        where <P2::BaseRing as RingStore>::Type: CanIsoFromTo<<P1::BaseRing as RingStore>::Type>
472    {
473        let mut result = from.zero();
474        from.add_assign_from_terms(&mut result, to.terms(&el).map(|(c, i)| (to.base_ring().get_ring().map_out(from.base_ring().get_ring(), to.base_ring().clone_el(c), iso), i)));
475        return result;
476    }
477
478    #[stability::unstable(feature = "enable")]
479    pub fn dbg_poly<P: PolyRing>(ring: &P, el: &P::Element, out: &mut std::fmt::Formatter, unknown_name: &str, env: EnvBindingStrength) -> std::fmt::Result {
480        let mut terms = ring.terms(el).fuse();
481        let first_term = terms.next();
482        if first_term.is_none() {
483            return ring.base_ring().get_ring().dbg_within(&ring.base_ring().zero(), out, env);
484        }
485        let second_term = terms.next();
486        let use_parenthesis = (env > EnvBindingStrength::Sum && second_term.is_some()) || 
487            (env > EnvBindingStrength::Product && !(ring.base_ring().is_one(&first_term.as_ref().unwrap().0) && first_term.as_ref().unwrap().1 == 1)) ||
488            env == EnvBindingStrength::Strongest;
489        let mut terms = first_term.into_iter().chain(second_term.into_iter()).chain(terms);
490        if use_parenthesis {
491            write!(out, "(")?;
492        }
493        let print_unknown = |i: usize, out: &mut std::fmt::Formatter| {
494            if i == 0 {
495                // print nothing
496                Ok(())
497            } else if i == 1 {
498                write!(out, "{}", unknown_name)
499            } else {
500                write!(out, "{}^{}", unknown_name, i)
501            }
502        };
503        if let Some((c, i)) = terms.next() {
504            if ring.base_ring().get_ring().is_approximate() || !ring.base_ring().is_one(c) || i == 0 {
505                ring.base_ring().get_ring().dbg_within(c, out, if i == 0 { EnvBindingStrength::Sum } else { EnvBindingStrength:: Product })?;
506            }
507            print_unknown(i, out)?;
508        } else {
509            write!(out, "0")?;
510        }
511        while let Some((c, i)) = terms.next() {
512            write!(out, " + ")?;
513            if ring.base_ring().get_ring().is_approximate() || !ring.base_ring().is_one(c) || i == 0 {
514                ring.base_ring().get_ring().dbg_within(c, out, if i == 0 { EnvBindingStrength::Sum } else { EnvBindingStrength:: Product })?;
515            }
516            print_unknown(i, out)?;
517        }
518        if use_parenthesis {
519            write!(out, ")")?;
520        }
521        return Ok(());
522    }
523}
524
525///
526/// Constructs the homomorphism `R[X][Y] -> S[X][Y], X -> Y, Y -> X` that swaps the
527/// the two indeterminates of a polynomial ring in two indeterminates.
528/// 
529/// Coefficients are mapped from `R` to `S` using the given homomorphism.
530/// 
531pub fn transpose_indeterminates<P1, P2, H>(from: P1, to: P2, base_hom: H) -> impl Homomorphism<P1::Type, P2::Type>
532    where P1: RingStore, P1::Type: PolyRing,
533        P2: RingStore, P2::Type: PolyRing,
534        <<P1::Type as RingExtension>::BaseRing as RingStore>::Type: PolyRing,
535        <<P2::Type as RingExtension>::BaseRing as RingStore>::Type: PolyRing,
536        H: Homomorphism<<<<<P1::Type as RingExtension>::BaseRing as RingStore>::Type as RingExtension>::BaseRing as RingStore>::Type,
537            <<<<P2::Type as RingExtension>::BaseRing as RingStore>::Type as RingExtension>::BaseRing as RingStore>::Type>
538{
539    LambdaHom::new(from, to, move |from, to, x| {
540        let mut result_terms: HashMap<usize, Vec<(_, usize)>> = HashMap::new();
541        for (f, i) in from.terms(x) {
542            for (c, j) in from.base_ring().terms(f) {
543                match result_terms.entry(j) {
544                    std::collections::hash_map::Entry::Occupied(mut e) => { e.get_mut().push((base_hom.map_ref(c), i)); },
545                    std::collections::hash_map::Entry::Vacant(e) => { _ = e.insert(vec![(base_hom.map_ref(c), i)]); }
546                }
547            }
548        }
549        return to.from_terms(result_terms.into_iter().map(|(j, f)| (to.base_ring().from_terms(f.into_iter()), j)));
550    })
551}
552
553#[cfg(any(test, feature = "generic_tests"))]
554pub mod generic_tests {
555    use super::*;
556
557    pub fn test_poly_ring_axioms<R: PolyRingStore, I: Iterator<Item = El<<R::Type as RingExtension>::BaseRing>>>(ring: R, interesting_base_ring_elements: I)
558        where R::Type: PolyRing
559    {    
560        let x = ring.indeterminate();
561        let elements = interesting_base_ring_elements.collect::<Vec<_>>();
562        
563        // test linear independence of X
564        for a in &elements {
565            for b in &elements {
566                for c in &elements {
567                    for d in &elements {
568                        let a_bx = ring.add(ring.inclusion().map_ref(a), ring.mul_ref_snd(ring.inclusion().map_ref(b), &x));
569                        let c_dx = ring.add(ring.inclusion().map_ref(c), ring.mul_ref_snd(ring.inclusion().map_ref(d), &x));
570                        assert!(ring.eq_el(&a_bx, &c_dx) == (ring.base_ring().eq_el(a, c) && ring.base_ring().eq_el(b, d)));
571                    }
572                }
573            }
574        }
575        
576        // elementwise addition follows trivially from the ring axioms
577
578        // technically, convoluted multiplication follows from the ring axioms too, but test it anyway
579        for a in &elements {
580            for b in &elements {
581                for c in &elements {
582                    for d in &elements {
583                        let a_bx = ring.add(ring.inclusion().map_ref(a), ring.mul_ref_snd(ring.inclusion().map_ref(b), &x));
584                        let c_dx = ring.add(ring.inclusion().map_ref(c), ring.mul_ref_snd(ring.inclusion().map_ref(d), &x));
585                        let result = <_ as RingStore>::sum(&ring, [
586                            ring.mul(ring.inclusion().map_ref(a), ring.inclusion().map_ref(c)),
587                            ring.mul(ring.inclusion().map_ref(a), ring.mul_ref_snd(ring.inclusion().map_ref(d), &x)),
588                            ring.mul(ring.inclusion().map_ref(b), ring.mul_ref_snd(ring.inclusion().map_ref(c), &x)),
589                            ring.mul(ring.inclusion().map_ref(b), ring.mul(ring.inclusion().map_ref(d), ring.pow(ring.clone_el(&x), 2)))
590                        ].into_iter());
591                        assert_el_eq!(ring, result, ring.mul(a_bx, c_dx));
592                    }
593                }
594            }
595        }
596
597        // test terms(), from_terms()
598        for a in &elements {
599            for b in &elements {
600                for c in &elements {
601                    let f = <_ as RingStore>::sum(&ring, [
602                        ring.inclusion().map_ref(a),
603                        ring.mul_ref_snd(ring.inclusion().map_ref(b), &x),
604                        ring.mul(ring.inclusion().map_ref(c), ring.pow(ring.clone_el(&x), 3))
605                    ].into_iter());
606                    let actual = ring.from_terms([(ring.base_ring().clone_el(a), 0), (ring.base_ring().clone_el(c), 3), (ring.base_ring().clone_el(b), 1)].into_iter());
607                    assert_el_eq!(ring, f, actual);
608                    assert_el_eq!(ring, f, ring.from_terms(ring.terms(&f).map(|(c, i)| (ring.base_ring().clone_el(c), i))));
609                }
610            }
611        }
612
613        // test div_rem_monic()
614        for a in &elements {
615            for b in &elements {
616                for c in &elements {
617                    let f = ring.from_terms([(ring.base_ring().clone_el(a), 0), (ring.base_ring().clone_el(b), 3)].into_iter());
618                    let g = ring.from_terms([(ring.base_ring().negate(ring.base_ring().clone_el(c)), 0), (ring.base_ring().one(), 1)].into_iter());
619
620                    let (quo, rem) = ring.div_rem_monic(ring.clone_el(&f), &g);
621                    assert_el_eq!(
622                        &ring,
623                        &ring.from_terms([(ring.base_ring().add_ref_fst(a, ring.base_ring().mul_ref_fst(b, ring.base_ring().pow(ring.base_ring().clone_el(c), 3))), 0)].into_iter()),
624                        &rem
625                    );
626                    assert_el_eq!(
627                        &ring,
628                        &f,
629                        &ring.add(rem, ring.mul(quo, g))
630                    );
631                }
632            }
633        }
634
635        // test truncate_monomials()
636        for a in &elements {
637            for b in &elements {
638                for i in 2..5 {
639                    let a = ring.from_terms([(ring.base_ring().clone_el(a), 0), (ring.base_ring().one(), 3), (ring.base_ring().clone_el(b), 4), (ring.base_ring().one(), 5)]);
640                    let mut a_trunc = ring.clone_el(&a);
641                    ring.truncate_monomials(&mut a_trunc, i);
642                    assert_el_eq!(
643                        &ring,
644                        ring.div_rem_monic(ring.clone_el(&a), &ring.from_terms([(ring.base_ring().one(), i)])).1,
645                        a_trunc
646                    );
647                }
648            }
649        }
650
651        // test evaluate()
652        let hom = ring.base_ring().int_hom();
653        let base_ring = hom.codomain();
654        let f = ring.from_terms([(hom.map(1), 0), (hom.map(3), 1), (hom.map(7), 3)].into_iter());
655        for a in &elements {
656            assert_el_eq!(
657                &base_ring,
658                &base_ring.add(base_ring.one(), base_ring.add(base_ring.mul_ref_snd(hom.map(3), a), base_ring.mul(hom.map(7), base_ring.pow(base_ring.clone_el(a), 3)))),
659                &ring.evaluate(&f, a, &base_ring.identity())
660            )
661        }
662    }
663}
664
665#[cfg(test)]
666use std::fmt::{Display, Formatter};
667#[cfg(test)]
668use dense_poly::DensePolyRing;
669#[cfg(test)]
670use crate::primitive_int::StaticRing;
671
672#[test]
673fn test_dbg_poly() {
674    let ring = DensePolyRing::new(StaticRing::<i64>::RING, "X");
675    let [f1, f2, f3, f4] = ring.with_wrapped_indeterminate(|X| [X.clone(), X + 1, 2 * X + 1, 2 * X]);
676
677    fn to_str(ring: &DensePolyRing<StaticRing<i64>>, f: &El<DensePolyRing<StaticRing<i64>>>, env: EnvBindingStrength) -> String {
678        struct DisplayEl<'a> {
679            ring: &'a DensePolyRing<StaticRing<i64>>,
680            f:  &'a El<DensePolyRing<StaticRing<i64>>>,
681            env: EnvBindingStrength
682        }
683        impl<'a> Display for DisplayEl<'a> {
684            fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
685                generic_impls::dbg_poly(self.ring.get_ring(), self.f, f, "X", self.env)
686            }
687        }
688        return format!("{}", DisplayEl { ring, f, env });
689    }
690
691    assert_eq!("X", to_str(&ring, &f1, EnvBindingStrength::Sum));
692    assert_eq!("X", to_str(&ring, &f1, EnvBindingStrength::Product));
693    assert_eq!("X", to_str(&ring, &f1, EnvBindingStrength::Power));
694    assert_eq!("X + 1", to_str(&ring, &f2, EnvBindingStrength::Sum));
695    assert_eq!("(X + 1)", to_str(&ring, &f2, EnvBindingStrength::Product));
696    assert_eq!("(X + 1)", to_str(&ring, &f2, EnvBindingStrength::Power));
697    assert_eq!("2X + 1", to_str(&ring, &f3, EnvBindingStrength::Sum));
698    assert_eq!("(2X + 1)", to_str(&ring, &f3, EnvBindingStrength::Product));
699    assert_eq!("(2X + 1)", to_str(&ring, &f3, EnvBindingStrength::Power));
700    assert_eq!("2X", to_str(&ring, &f4, EnvBindingStrength::Sum));
701    assert_eq!("2X", to_str(&ring, &f4, EnvBindingStrength::Product));
702    assert_eq!("(2X)", to_str(&ring, &f4, EnvBindingStrength::Power));
703}
feanor_math/rings/poly/mod.rs

feanor_math/rings/poly/
mod.rs
