feanor_math/rings/multivariate/

mod.rs

use crate::homomorphism::Homomorphism;
use crate::ring::*;
use crate::seq::VectorFn;
use crate::wrapper::RingElementWrapper;

/// Contains an implementation [`multivariate_impl::MultivariatePolyRingImpl`] of a multivariate
/// polynomial ring.
pub mod multivariate_impl;

use std::any::Any;
use std::cmp::{Ordering, max};

/// Type of coefficients of multivariate polynomials of the given ring.
pub type PolyCoeff<P> = El<<<P as RingStore>::Type as RingExtension>::BaseRing>;

/// Type of monomials of multivariate polynomials of the given ring.
pub type PolyMonomial<P> = <<P as RingStore>::Type as MultivariatePolyRing>::Monomial;

/// Trait for multivariate polynomial rings.
pub trait MultivariatePolyRing: RingExtension {
    type Monomial;
    type TermIter<'a>: Iterator<Item = (&'a El<Self::BaseRing>, &'a Self::Monomial)>
    where
        Self: 'a;

    /// Returns the number of variables of this polynomial ring, i.e. the transcendence degree
    /// of the base ring.
    fn indeterminate_count(&self) -> usize;

    /// Returns the monomial `Xi`, where `Xi` is the `i`-th generator of this ring.
    fn indeterminate(&self, i: usize) -> Self::Monomial {
        assert!(i < self.indeterminate_count());
        self.create_monomial((0..self.indeterminate_count()).map(|j| if i == j { 1 } else { 0 }))
    }

    /// Creates a monomial with the given exponents.
    ///
    /// Note that when building a polynomial, the most convenient method is usually
    /// to use [`MultivariatePolyRingStore::with_wrapped_indeterminates()`].
    ///
    /// # Example
    /// ```rust
    /// # use feanor_math::ring::*;
    /// # use feanor_math::primitive_int::*;
    /// # use feanor_math::rings::multivariate::*;
    /// # use feanor_math::rings::multivariate::multivariate_impl::*;
    /// let poly_ring = MultivariatePolyRingImpl::new(StaticRing::<i64>::RING, 3);
    /// let x_as_monomial = poly_ring.create_monomial([1, 0, 0]);
    /// let x_as_poly = poly_ring.create_term(1, x_as_monomial);
    /// assert_eq!("X0", format!("{}", poly_ring.format(&x_as_poly)));
    /// ```
    fn create_monomial<I>(&self, exponents: I) -> Self::Monomial
    where
        I: IntoIterator<Item = usize>,
        I::IntoIter: ExactSizeIterator;

    /// Multiplies the given polynomial with the given monomial.
    fn mul_assign_monomial(&self, f: &mut Self::Element, monomial: Self::Monomial);

    /// Returns the coefficient corresponding to the given monomial in the given polynomial.
    /// If the polynomial does not contain a term with that monomial, zero is returned.
    fn coefficient_at<'a>(&'a self, f: &'a Self::Element, m: &Self::Monomial) -> &'a El<Self::BaseRing>;

    /// Returns the power of the `var_index`-th variable in the given monomial.
    /// In other words, this maps `X1^i1 ... Xm^im` to `i(var_index)`.
    fn exponent_at(&self, m: &Self::Monomial, var_index: usize) -> usize;

    /// Writes the powers of each variable in the given monomial into the given
    /// output slice.
    ///
    /// This is equivalent to performing `out[i] = self.exponent_at(m, i)` for
    /// every `i` in `0..self.indeterminate_count()`.
    fn expand_monomial_to(&self, m: &Self::Monomial, out: &mut [usize]) {
        assert_eq!(out.len(), self.indeterminate_count());
        for (i, out) in out.iter_mut().enumerate() {
            *out = self.exponent_at(m, i);
        }
    }

    /// Returns an iterator over all nonzero terms of the given polynomial.
    fn terms<'a>(&'a self, f: &'a Self::Element) -> Self::TermIter<'a>;

    /// Creates a new single-term polynomial.
    fn create_term(&self, coeff: El<Self::BaseRing>, monomial: Self::Monomial) -> Self::Element {
        let mut result = self.from(coeff);
        self.mul_assign_monomial(&mut result, monomial);
        return result;
    }

    /// Returns the **L**eading **T**erm of `f`, i.e. the term whose monomial is largest w.r.t. the
    /// given order.
    fn LT<'a, O: MonomialOrder>(
        &'a self,
        f: &'a Self::Element,
        order: O,
    ) -> Option<(&'a El<Self::BaseRing>, &'a Self::Monomial)> {
        self.terms(f).max_by(|l, r| order.compare(RingRef::new(self), l.1, r.1))
    }

    /// Returns the term of `f` whose monomial is largest (w.r.t. the given order) among all
    /// monomials smaller than `lt_than`.
    fn largest_term_lt<'a, O: MonomialOrder>(
        &'a self,
        f: &'a Self::Element,
        order: O,
        lt_than: &Self::Monomial,
    ) -> Option<(&'a El<Self::BaseRing>, &'a Self::Monomial)> {
        self.terms(f)
            .filter(|(_, m)| order.compare(RingRef::new(self), m, lt_than) == Ordering::Less)
            .max_by(|l, r| order.compare(RingRef::new(self), l.1, r.1))
    }

    fn add_assign_from_terms<I>(&self, lhs: &mut Self::Element, rhs: I)
    where
        I: IntoIterator<Item = (El<Self::BaseRing>, Self::Monomial)>,
    {
        let self_ring = RingRef::new(self);
        self.add_assign(lhs, self_ring.sum(rhs.into_iter().map(|(c, m)| self.create_term(c, m))));
    }

    /// Applies the given homomorphism `R -> S` to each coefficient of the given polynomial
    /// in `R[X1, ..., Xm]` to produce a monomial in `S[X1, ..., Xm]`.
    fn map_terms<P, H>(&self, from: &P, el: &P::Element, hom: H) -> Self::Element
    where
        P: ?Sized + MultivariatePolyRing,
        H: Homomorphism<<P::BaseRing as RingStore>::Type, <Self::BaseRing as RingStore>::Type>,
    {
        assert!(self.base_ring().get_ring() == hom.codomain().get_ring());
        assert!(from.base_ring().get_ring() == hom.domain().get_ring());
        assert_eq!(self.indeterminate_count(), from.indeterminate_count());
        let mut exponents_storage = (0..self.indeterminate_count()).map(|_| 0).collect::<Vec<_>>();
        return RingRef::new(self).from_terms(from.terms(el).map(|(c, m)| {
            from.expand_monomial_to(m, &mut exponents_storage);
            (hom.map_ref(c), self.create_monomial(exponents_storage.iter().copied()))
        }));
    }

    fn clone_monomial(&self, mon: &Self::Monomial) -> Self::Monomial {
        self.create_monomial((0..self.indeterminate_count()).map(|i| self.exponent_at(mon, i)))
    }

    /// Returns a list of all variables appearing in the given polynomial.
    /// Associated with each variable is the highest degree in which it
    /// appears in some term.
    ///
    /// # Example
    /// ```rust
    /// # use feanor_math::primitive_int::*;
    /// # use feanor_math::ring::*;
    /// # use feanor_math::rings::multivariate::*;
    /// # use feanor_math::rings::multivariate::multivariate_impl::*;
    /// let poly_ring = MultivariatePolyRingImpl::new(StaticRing::<i64>::RING, 2);
    /// let [f, g] =
    ///     poly_ring.with_wrapped_indeterminates(|[X, Y]| [1 + X + X.pow_ref(2) * Y, X.pow_ref(3)]);
    /// assert_eq!(vec![(0, 2), (1, 1)], poly_ring.appearing_indeterminates(&f));
    /// assert_eq!(vec![(0, 3)], poly_ring.appearing_indeterminates(&g));
    /// ```
    fn appearing_indeterminates(&self, f: &Self::Element) -> Vec<(usize, usize)> {
        let mut result = (0..self.indeterminate_count()).map(|_| 0).collect::<Vec<_>>();
        for (_, m) in self.terms(f) {
            for (i, result) in result.iter_mut().enumerate() {
                *result = max(*result, self.exponent_at(m, i));
            }
        }
        return result.into_iter().enumerate().filter(|(_, e)| *e > 0).collect();
    }

    /// Multiplies two monomials.
    fn monomial_mul(&self, lhs: Self::Monomial, rhs: &Self::Monomial) -> Self::Monomial {
        self.create_monomial(
            (0..self.indeterminate_count()).map(|i| self.exponent_at(&lhs, i) + self.exponent_at(rhs, i)),
        )
    }

    /// Returns the degree of a monomial, i.e. the sum of the exponents of all variables.
    fn monomial_deg(&self, mon: &Self::Monomial) -> usize {
        (0..self.indeterminate_count()).map(|i| self.exponent_at(mon, i)).sum()
    }

    /// Returns the least common multiple of two monomials.
    fn monomial_lcm(&self, lhs: Self::Monomial, rhs: &Self::Monomial) -> Self::Monomial {
        self.create_monomial(
            (0..self.indeterminate_count()).map(|i| max(self.exponent_at(&lhs, i), self.exponent_at(rhs, i))),
        )
    }

    /// Computes the quotient of two monomials.
    ///
    /// If `lhs` does not divide `rhs`, this returns `Result::Err` with the monomial
    /// `lhs / gcd(rhs, lhs)`.
    fn monomial_div(&self, lhs: Self::Monomial, rhs: &Self::Monomial) -> Result<Self::Monomial, Self::Monomial> {
        let mut failed = false;
        let result = self.create_monomial((0..self.indeterminate_count()).map(|i| {
            if let Some(res) = self.exponent_at(&lhs, i).checked_sub(self.exponent_at(rhs, i)) {
                res
            } else {
                failed = true;
                0
            }
        }));
        if failed { Err(result) } else { Ok(result) }
    }

    /// Evaluates the given polynomial at the given values.
    ///
    /// # Example
    /// ```rust
    /// # use feanor_math::ring::*;
    /// # use feanor_math::rings::multivariate::*;
    /// # use feanor_math::rings::multivariate::multivariate_impl::*;
    /// # use feanor_math::primitive_int::*;
    /// # use feanor_math::seq::*;
    /// let poly_ring = MultivariatePolyRingImpl::new(StaticRing::<i64>::RING, 2);
    /// let [f] = poly_ring.with_wrapped_indeterminates(|[X, Y]| [1 + X + X.pow_ref(2) * Y]);
    /// assert_eq!(
    ///     1 + 5 + 5 * 5 * 8,
    ///     poly_ring.evaluate(
    ///         &f,
    ///         [5, 8].clone_ring_els(StaticRing::<i64>::RING),
    ///         &poly_ring.base_ring().identity()
    ///     )
    /// );
    /// ```
    fn evaluate<R, V, H>(&self, f: &Self::Element, value: V, hom: H) -> R::Element
    where
        R: ?Sized + RingBase,
        H: Homomorphism<<Self::BaseRing as RingStore>::Type, R>,
        V: VectorFn<R::Element>,
    {
        assert_eq!(self.indeterminate_count(), value.len());
        assert!(hom.domain().get_ring() == self.base_ring().get_ring());
        hom.codomain().sum(self.terms(f).map(|(c, m)| {
            hom.mul_map(
                hom.codomain().prod(
                    (0..self.indeterminate_count()).map(|i| hom.codomain().pow(value.at(i), self.exponent_at(m, i))),
                ),
                hom.domain().clone_el(c),
            )
        }))
    }

    /// Replaces the given indeterminate in the given polynomial by the value `val`.
    ///
    /// Conceptually, this is similar to [`MultivariatePolyRing::evaluate()`], but less general,
    /// which can allow a faster implementation sometimes. In particular, this only replaces a
    /// single indeterminate, and does not change the ring.
    fn specialize(&self, f: &Self::Element, var: usize, val: &Self::Element) -> Self::Element {
        assert!(var < self.indeterminate_count());
        let mut parts = Vec::new();
        for (c, m) in self.terms(f) {
            while self.exponent_at(m, var) >= parts.len() {
                parts.push(Vec::new());
            }
            let new_m = self.create_monomial(
                (0..self.indeterminate_count()).map(|i| if i == var { 0 } else { self.exponent_at(m, i) }),
            );
            parts[self.exponent_at(m, var)].push((self.base_ring().clone_el(c), new_m));
        }
        if let Some(first) = parts.pop() {
            let mut current = self.zero();
            self.add_assign_from_terms(&mut current, first);
            while let Some(new) = parts.pop() {
                let mut next = self.zero();
                self.add_assign_from_terms(&mut next, new);
                self.mul_assign_ref(&mut current, val);
                self.add_assign(&mut current, next);
            }
            return current;
        } else {
            return self.zero();
        }
    }
}

/// [`RingStore`] for [`MultivariatePolyRing`]
pub trait MultivariatePolyRingStore: RingStore
where
    Self::Type: MultivariatePolyRing,
{
    delegate! { MultivariatePolyRing, fn indeterminate_count(&self) -> usize }
    delegate! { MultivariatePolyRing, fn indeterminate(&self, i: usize) -> <Self::Type as MultivariatePolyRing>::Monomial }
    delegate! { MultivariatePolyRing, fn create_term(&self, coeff: PolyCoeff<Self>, monomial: PolyMonomial<Self>) -> El<Self> }
    delegate! { MultivariatePolyRing, fn exponent_at(&self, m: &PolyMonomial<Self>, var_index: usize) -> usize }
    delegate! { MultivariatePolyRing, fn expand_monomial_to(&self, m: &PolyMonomial<Self>, out: &mut [usize]) -> () }
    delegate! { MultivariatePolyRing, fn monomial_mul(&self, lhs: PolyMonomial<Self>, rhs: &PolyMonomial<Self>) -> PolyMonomial<Self> }
    delegate! { MultivariatePolyRing, fn monomial_lcm(&self, lhs: PolyMonomial<Self>, rhs: &PolyMonomial<Self>) -> PolyMonomial<Self> }
    delegate! { MultivariatePolyRing, fn monomial_div(&self, lhs: PolyMonomial<Self>, rhs: &PolyMonomial<Self>) -> Result<PolyMonomial<Self>, PolyMonomial<Self>> }
    delegate! { MultivariatePolyRing, fn monomial_deg(&self, val: &PolyMonomial<Self>) -> usize }
    delegate! { MultivariatePolyRing, fn mul_assign_monomial(&self, f: &mut El<Self>, monomial: PolyMonomial<Self>) -> () }
    delegate! { MultivariatePolyRing, fn appearing_indeterminates(&self, f: &El<Self>) -> Vec<(usize, usize)> }
    delegate! { MultivariatePolyRing, fn specialize(&self, f: &El<Self>, var: usize, val: &El<Self>) -> El<Self> }

    fn expand_monomial(&self, m: &PolyMonomial<Self>) -> Vec<usize> {
        let mut result = (0..self.indeterminate_count()).map(|_| 0).collect::<Vec<_>>();
        self.expand_monomial_to(m, &mut result);
        return result;
    }

    /// Returns the term of `f` whose monomial is largest (w.r.t. the given order) among all
    /// monomials smaller than `lt_than`.
    fn largest_term_lt<'a, O: MonomialOrder>(
        &'a self,
        f: &'a El<Self>,
        order: O,
        lt_than: &PolyMonomial<Self>,
    ) -> Option<(&'a PolyCoeff<Self>, &'a PolyMonomial<Self>)> {
        self.get_ring().largest_term_lt(f, order, lt_than)
    }

    /// Returns the **L**eading **T**erm of `f`, i.e. the term whose monomial is largest w.r.t. the
    /// given order.
    fn LT<'a, O: MonomialOrder>(
        &'a self,
        f: &'a El<Self>,
        order: O,
    ) -> Option<(&'a PolyCoeff<Self>, &'a PolyMonomial<Self>)> {
        self.get_ring().LT(f, order)
    }

    /// Creates a new monomial with given exponents.
    ///
    /// For details, see [`MultivariatePolyRing::create_monomial()`].
    fn create_monomial<I>(&self, exponents: I) -> PolyMonomial<Self>
    where
        I: IntoIterator<Item = usize>,
        I::IntoIter: ExactSizeIterator,
    {
        self.get_ring().create_monomial(exponents)
    }

    fn clone_monomial(&self, mon: &PolyMonomial<Self>) -> PolyMonomial<Self> { self.get_ring().clone_monomial(mon) }

    /// Returns the coefficient of a polynomial corresponding to a monomial.
    ///
    /// For details, see [`MultivariatePolyRing::coefficient_at()`].
    fn coefficient_at<'a>(&'a self, f: &'a El<Self>, m: &PolyMonomial<Self>) -> &'a PolyCoeff<Self> {
        self.get_ring().coefficient_at(f, m)
    }

    /// Returns an iterator over all nonzero terms of the polynomial.
    ///
    /// For details, see [`MultivariatePolyRing::terms()`].
    fn terms<'a>(&'a self, f: &'a El<Self>) -> <Self::Type as MultivariatePolyRing>::TermIter<'a> {
        self.get_ring().terms(f)
    }

    /// Creates a new polynomial by summing up all the given terms.
    fn from_terms<I>(&self, terms: I) -> El<Self>
    where
        I: IntoIterator<Item = (PolyCoeff<Self>, PolyMonomial<Self>)>,
    {
        let mut result = self.zero();
        self.get_ring().add_assign_from_terms(&mut result, terms);
        return result;
    }

    /// Evaluates the polynomial at the given values.
    ///
    /// For details, see [`MultivariatePolyRing::evaluate()`].
    fn evaluate<R, V, H>(&self, f: &El<Self>, value: V, hom: H) -> R::Element
    where
        R: ?Sized + RingBase,
        H: Homomorphism<<<Self::Type as RingExtension>::BaseRing as RingStore>::Type, R>,
        V: VectorFn<R::Element>,
    {
        self.get_ring().evaluate(f, value, hom)
    }

    /// Returns the homomorphism `R[X1, ..., Xm] -> S[X1, ..., Xm]` that is induced by
    /// applying the given homomorphism `R -> S` coefficient-wise.
    fn into_lifted_hom<P, H>(self, from: P, hom: H) -> CoefficientHom<P, Self, H>
    where
        P: RingStore,
        P::Type: MultivariatePolyRing,
        H: Homomorphism<
                <<P::Type as RingExtension>::BaseRing as RingStore>::Type,
                <<Self::Type as RingExtension>::BaseRing as RingStore>::Type,
            >,
    {
        CoefficientHom { from, to: self, hom }
    }

    /// Returns the homomorphism `R[X1, ..., Xm] -> S[X1, ..., Xm]` that is induced by
    /// applying the given homomorphism `R -> S` coefficient-wise.
    ///
    /// If the ownership of this ring should be transferred to the homomorphism, consider
    /// using [`MultivariatePolyRingStore::into_lifted_hom()`].
    fn lifted_hom<P, H>(&self, from: P, hom: H) -> CoefficientHom<P, &Self, H>
    where
        P: RingStore,
        P::Type: MultivariatePolyRing,
        H: Homomorphism<
                <<P::Type as RingExtension>::BaseRing as RingStore>::Type,
                <<Self::Type as RingExtension>::BaseRing as RingStore>::Type,
            >,
    {
        self.into_lifted_hom(from, hom)
    }

    /// Invokes the function with a wrapped version of the indeterminates of this poly ring.
    /// Use for convenient creation of polynomials.
    ///
    /// Note however that [`MultivariatePolyRingStore::from_terms()`] might be more performant.
    ///
    /// # Example
    /// ```rust
    /// use feanor_math::assert_el_eq;
    /// use feanor_math::homomorphism::*;
    /// use feanor_math::ring::*;
    /// use feanor_math::rings::multivariate::multivariate_impl::*;
    /// use feanor_math::rings::multivariate::*;
    /// use feanor_math::rings::zn::zn_64::*;
    /// let base_ring = Zn::new(7);
    /// let poly_ring = MultivariatePolyRingImpl::new(base_ring, 3);
    /// let f_version1 = poly_ring.from_terms(
    ///     [
    ///         (
    ///             base_ring.int_hom().map(3),
    ///             poly_ring.create_monomial([0, 0, 0]),
    ///         ),
    ///         (
    ///             base_ring.int_hom().map(2),
    ///             poly_ring.create_monomial([0, 1, 1]),
    ///         ),
    ///         (base_ring.one(), poly_ring.create_monomial([2, 0, 0])),
    ///     ]
    ///     .into_iter(),
    /// );
    /// let f_version2 = poly_ring
    ///     .with_wrapped_indeterminates_dyn(|[x, y, z]| [3 + 2 * y * z + x.pow_ref(2)])
    ///     .into_iter()
    ///     .next()
    ///     .unwrap();
    /// let [f_version3] =
    ///     poly_ring.with_wrapped_indeterminates(|[x, y, z]| [3 + 2 * y * z + x.pow_ref(2)]);
    /// assert_el_eq!(poly_ring, f_version1, f_version2);
    /// ```
    #[stability::unstable(feature = "enable")]
    fn with_wrapped_indeterminates_dyn<'a, F, T, const N: usize>(&'a self, f: F) -> Vec<El<Self>>
    where
        F: FnOnce([&RingElementWrapper<&'a Self>; N]) -> T,
        T: IntoIterator<Item = RingElementWrapper<&'a Self>>,
    {
        assert_eq!(self.indeterminate_count(), N);
        let wrapped_indets: [_; N] = std::array::from_fn(|i| {
            RingElementWrapper::new(self, self.create_term(self.base_ring().one(), self.indeterminate(i)))
        });
        f(std::array::from_fn(|i| &wrapped_indets[i]))
            .into_iter()
            .map(|f| f.unwrap())
            .collect()
    }

    /// Same as [`MultivariatePolyRingStore::with_wrapped_indeterminates_dyn()`], but returns result
    /// as an array to allow pattern matching.
    ///
    /// # Example
    /// ```rust
    /// use feanor_math::assert_el_eq;
    /// use feanor_math::homomorphism::*;
    /// use feanor_math::ring::*;
    /// use feanor_math::rings::multivariate::multivariate_impl::*;
    /// use feanor_math::rings::multivariate::*;
    /// use feanor_math::rings::zn::zn_64::*;
    /// let base_ring = Zn::new(7);
    /// let poly_ring = MultivariatePolyRingImpl::new(base_ring, 3);
    /// let f_version1 = poly_ring.from_terms(
    ///     [
    ///         (
    ///             base_ring.int_hom().map(3),
    ///             poly_ring.create_monomial([0, 0, 0]),
    ///         ),
    ///         (
    ///             base_ring.int_hom().map(2),
    ///             poly_ring.create_monomial([0, 1, 1]),
    ///         ),
    ///         (base_ring.one(), poly_ring.create_monomial([2, 0, 0])),
    ///     ]
    ///     .into_iter(),
    /// );
    /// let f_version2 = poly_ring
    ///     .with_wrapped_indeterminates_dyn(|[x, y, z]| [3 + 2 * y * z + x.pow_ref(2)])
    ///     .into_iter()
    ///     .next()
    ///     .unwrap();
    /// let [f_version3] =
    ///     poly_ring.with_wrapped_indeterminates(|[x, y, z]| [3 + 2 * y * z + x.pow_ref(2)]);
    /// assert_el_eq!(poly_ring, f_version1, f_version2);
    /// ```
    #[stability::unstable(feature = "enable")]
    fn with_wrapped_indeterminates<'a, F, const N: usize, const M: usize>(&'a self, f: F) -> [El<Self>; M]
    where
        F: FnOnce([&RingElementWrapper<&'a Self>; N]) -> [RingElementWrapper<&'a Self>; M],
    {
        assert_eq!(self.indeterminate_count(), N);
        let wrapped_indets: [_; N] = std::array::from_fn(|i| {
            RingElementWrapper::new(self, self.create_term(self.base_ring().one(), self.indeterminate(i)))
        });
        let mut result_it = f(std::array::from_fn(|i| &wrapped_indets[i]))
            .into_iter()
            .map(|f| f.unwrap());
        let result = std::array::from_fn(|_| result_it.next().unwrap());
        debug_assert!(result_it.next().is_none());
        return result;
    }
}

impl<P> MultivariatePolyRingStore for P
where
    P: RingStore,
    P::Type: MultivariatePolyRing,
{
}

/// Trait for monomial orders, i.e. orderings on the monomials `X1^i1 ... Xm^im` of a multivariate
/// polynomial ring that are compatible with multiplication. These are also sometimes called term
/// orders.
///
/// To be precise, a total order on monomials is a monomial order, if for all `u, v, w` with `u <=
/// v` also `uw <= vw`.
pub trait MonomialOrder: Clone {
    fn compare<P>(&self, ring: P, lhs: &PolyMonomial<P>, rhs: &PolyMonomial<P>) -> Ordering
    where
        P: RingStore,
        P::Type: MultivariatePolyRing;

    /// Checks whether two monomials are equal.
    ///
    /// This may be faster than [`MonomialOrder::compare()`], but clearly must have
    /// a compatible behavior.
    fn eq_mon<P>(&self, ring: P, lhs: &PolyMonomial<P>, rhs: &PolyMonomial<P>) -> bool
    where
        P: RingStore,
        P::Type: MultivariatePolyRing,
    {
        self.compare(ring, lhs, rhs) == Ordering::Equal
    }

    /// Whether this order is the same as the given other order, i.e. [`MonomialOrder::compare()`]
    /// gives the same output on all inputs.
    ///
    /// Many monomial orders are likely to be implemented as zero-sized types with only a single
    /// instance. In this case, the default implementation is sufficient.
    fn is_same<O>(&self, rhs: &O) -> bool
    where
        O: MonomialOrder,
    {
        assert!(self.as_any().is_some());
        assert!(std::mem::size_of::<Self>() == 0);
        if let Some(rhs_as_any) = rhs.as_any() {
            self.as_any().unwrap().type_id() == rhs_as_any.type_id()
        } else {
            false
        }
    }

    /// Upcasts this reference to `&dyn Any`, which is sometimes required to compare monomial order
    /// objects of different types.
    fn as_any(&self) -> Option<&dyn Any>;
}

/// Trait for [`MonomialOrder`]s that are graded, i.e. for `v, w` with `deg(v) < deg(w)`
/// they always satisfy `v < w`.
pub trait GradedMonomialOrder: MonomialOrder {}

/// The graded reverse lexicographic order. This is the most important monomial order, since
/// computing a Groebner basis w.r.t. this order is usually more efficient than for other orders.
/// Also sometimes referred to as "grevlex".
///
/// Concretely, this is the ordering of monomials we get by first comparing monomial degrees, and
/// in case of a tie reverse the outcome of a lexicographic comparison, using a reversed order
/// of variables.
///
/// # Example
/// ```rust
/// # use feanor_math::ring::*;
/// # use feanor_math::rings::multivariate::*;
/// # use feanor_math::rings::multivariate::multivariate_impl::*;
/// # use feanor_math::primitive_int::*;
/// # use std::cmp::Ordering;
/// let poly_ring = MultivariatePolyRingImpl::new(StaticRing::<i64>::RING, 3);
/// let monomials_descending = [
///     [2, 0, 0], // x1^2
///     [1, 1, 0], // x1 x2
///     [0, 2, 0], // x2^2
///     [1, 0, 1], // x1 x3
///     [0, 1, 1], // x2 x3
///     [0, 0, 2], // x3^2
/// ]
/// .into_iter()
/// .map(|m| poly_ring.create_monomial(m))
/// .collect::<Vec<_>>();
/// for i in 1..6 {
///     assert!(
///         DegRevLex.compare(
///             &poly_ring,
///             &monomials_descending[i - 1],
///             &monomials_descending[i]
///         ) == Ordering::Greater
///     );
/// }
/// ```
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct DegRevLex;

impl MonomialOrder for DegRevLex {
    fn as_any(&self) -> Option<&dyn Any> { Some(self as &dyn Any) }

    fn compare<P>(&self, ring: P, lhs: &PolyMonomial<P>, rhs: &PolyMonomial<P>) -> Ordering
    where
        P: RingStore,
        P::Type: MultivariatePolyRing,
    {
        let lhs_deg = ring.monomial_deg(lhs);
        let rhs_deg = ring.monomial_deg(rhs);
        if lhs_deg < rhs_deg {
            return Ordering::Less;
        } else if lhs_deg > rhs_deg {
            return Ordering::Greater;
        } else {
            for i in (0..ring.indeterminate_count()).rev() {
                if ring.exponent_at(lhs, i) > ring.exponent_at(rhs, i) {
                    return Ordering::Less;
                } else if ring.exponent_at(lhs, i) < ring.exponent_at(rhs, i) {
                    return Ordering::Greater;
                }
            }
            return Ordering::Equal;
        }
    }
}

impl GradedMonomialOrder for DegRevLex {}

/// Lexicographic ordering of monomials.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Lex;

impl MonomialOrder for Lex {
    fn as_any(&self) -> Option<&dyn Any> { Some(self as &dyn Any) }

    fn compare<P>(&self, ring: P, lhs: &PolyMonomial<P>, rhs: &PolyMonomial<P>) -> Ordering
    where
        P: RingStore,
        P::Type: MultivariatePolyRing,
    {
        for i in 0..ring.indeterminate_count() {
            match ring.exponent_at(lhs, i).cmp(&ring.exponent_at(rhs, i)) {
                Ordering::Less => {
                    return Ordering::Less;
                }
                Ordering::Greater => {
                    return Ordering::Greater;
                }
                Ordering::Equal => {}
            }
        }
        return Ordering::Equal;
    }
}

pub struct CoefficientHom<PFrom, PTo, H>
where
    PFrom: RingStore,
    PTo: RingStore,
    PFrom::Type: MultivariatePolyRing,
    PTo::Type: MultivariatePolyRing,
    H: Homomorphism<
            <<PFrom::Type as RingExtension>::BaseRing as RingStore>::Type,
            <<PTo::Type as RingExtension>::BaseRing as RingStore>::Type,
        >,
{
    from: PFrom,
    to: PTo,
    hom: H,
}

impl<PFrom, PTo, H> Homomorphism<PFrom::Type, PTo::Type> for CoefficientHom<PFrom, PTo, H>
where
    PFrom: RingStore,
    PTo: RingStore,
    PFrom::Type: MultivariatePolyRing,
    PTo::Type: MultivariatePolyRing,
    H: Homomorphism<
            <<PFrom::Type as RingExtension>::BaseRing as RingStore>::Type,
            <<PTo::Type as RingExtension>::BaseRing as RingStore>::Type,
        >,
{
    type DomainStore = PFrom;
    type CodomainStore = PTo;

    fn codomain(&self) -> &Self::CodomainStore { &self.to }

    fn domain(&self) -> &Self::DomainStore { &self.from }

    fn map(&self, x: <PFrom::Type as RingBase>::Element) -> <PTo::Type as RingBase>::Element { self.map_ref(&x) }

    fn map_ref(&self, x: &<PFrom::Type as RingBase>::Element) -> <PTo::Type as RingBase>::Element {
        self.to.get_ring().map_terms(self.from.get_ring(), x, &self.hom)
    }
}

pub mod generic_impls {
    use std::fmt::{Formatter, Result};

    use super::*;

    #[stability::unstable(feature = "enable")]
    pub fn print<P>(ring: P, poly: &El<P>, out: &mut Formatter, env: EnvBindingStrength) -> Result
    where
        P: RingStore,
        P::Type: MultivariatePolyRing,
    {
        if ring.is_zero(poly) {
            ring.base_ring()
                .get_ring()
                .dbg_within(&ring.base_ring().zero(), out, env)?;
        } else {
            if env >= EnvBindingStrength::Product {
                write!(out, "(")?;
            }

            let mut print_term = |c: &PolyCoeff<P>, m: &PolyMonomial<P>, with_plus: bool| {
                if with_plus {
                    write!(out, " + ")?;
                }
                let is_constant_term = ring.monomial_deg(m) == 0;
                if !ring.base_ring().is_one(c) || is_constant_term {
                    ring.base_ring().get_ring().dbg_within(
                        c,
                        out,
                        if is_constant_term {
                            EnvBindingStrength::Sum
                        } else {
                            EnvBindingStrength::Product
                        },
                    )?;
                    if !is_constant_term {
                        write!(out, " * ")?;
                    }
                }
                let mut needs_space = false;
                for i in 0..ring.indeterminate_count() {
                    if ring.exponent_at(m, i) > 0 {
                        if needs_space {
                            write!(out, " * ")?;
                        }
                        write!(out, "X{}", i)?;
                        needs_space = true;
                    }
                    if ring.exponent_at(m, i) > 1 {
                        write!(out, "^{}", ring.exponent_at(m, i))?;
                    }
                }
                return Ok::<(), std::fmt::Error>(());
            };

            for (i, (c, m)) in ring.terms(poly).enumerate() {
                print_term(c, m, i != 0)?;
            }
            if env >= EnvBindingStrength::Product {
                write!(out, ")")?;
            }
        }

        return Ok(());
    }
}

#[cfg(any(test, feature = "generic_tests"))]
pub mod generic_tests {
    use super::*;
    use crate::seq::*;

    #[stability::unstable(feature = "enable")]
    pub fn test_poly_ring_axioms<P: RingStore, I: Iterator<Item = PolyCoeff<P>>>(
        ring: P,
        interesting_base_ring_elements: I,
    ) where
        P::Type: MultivariatePolyRing,
    {
        let elements = interesting_base_ring_elements.collect::<Vec<_>>();
        let n = ring.indeterminate_count();
        let base_ring = ring.base_ring();

        // test multiplication of variables
        for i in 0..n {
            for j in 0..n {
                let xi = ring.create_term(base_ring.one(), ring.indeterminate(i));
                let xj = ring.create_term(base_ring.one(), ring.indeterminate(j));
                let xixj = ring.create_term(
                    base_ring.one(),
                    ring.create_monomial((0..n).map(|k| {
                        if k == i && k == j {
                            2
                        } else if k == j || k == i {
                            1
                        } else {
                            0
                        }
                    })),
                );
                assert_el_eq!(ring, xixj, ring.mul(xi, xj));
            }
        }

        // test monomial operations
        for i in 0..n {
            for j in 0..n {
                let xi = ring.indeterminate(i);
                let xj = ring.indeterminate(j);
                let xixj_lcm = ring.create_monomial((0..n).map(|k| if k == j || k == i { 1 } else { 0 }));
                assert_el_eq!(
                    ring,
                    ring.create_term(base_ring.one(), xixj_lcm),
                    ring.create_term(base_ring.one(), ring.monomial_lcm(xi, &xj))
                );
            }
        }

        // all monomials should be different
        for i in 0..n {
            for j in 0..n {
                let xi = ring.create_term(
                    base_ring.one(),
                    ring.create_monomial((0..n).map(|k| if k == i { 1 } else { 0 })),
                );
                let xj = ring.create_term(
                    base_ring.one(),
                    ring.create_monomial((0..n).map(|k| if k == j { 1 } else { 0 })),
                );
                assert!((i == j) == ring.eq_el(&xi, &xj));
            }
        }

        // monomials shouldn't be zero divisors
        for i in 0..n {
            for a in &elements {
                let xi = ring.create_term(base_ring.one(), ring.indeterminate(i));
                assert!(base_ring.is_zero(a) == ring.is_zero(&ring.inclusion().mul_ref_map(&xi, a)));
            }
        }

        // test add_assign_from_terms
        for i in 0..n {
            let xi = ring.indeterminate(i);
            let mut a = ring.create_term(base_ring.int_hom().map(3), ring.create_monomial((0..n).map(|_| 0)));
            let terms_with_multiples = [
                (base_ring.one(), ring.clone_monomial(&xi)),
                (base_ring.one(), ring.clone_monomial(&xi)),
                (base_ring.one(), ring.create_monomial((0..n).map(|_| 0))),
                (base_ring.one(), ring.create_monomial((0..n).map(|_| 0))),
                (base_ring.one(), ring.clone_monomial(&xi)),
                (base_ring.one(), ring.create_monomial((0..n).map(|_| 0))),
                (base_ring.one(), ring.clone_monomial(&xi)),
                (base_ring.one(), ring.create_monomial((0..n).map(|_| 0))),
            ];
            ring.get_ring().add_assign_from_terms(&mut a, terms_with_multiples);
            assert_el_eq!(
                &ring,
                ring.from_terms([
                    (base_ring.int_hom().map(7), ring.create_monomial((0..n).map(|_| 0))),
                    (base_ring.int_hom().map(4), xi),
                ]),
                a
            );
        }

        if n >= 2 {
            let one = ring.create_monomial((0..n).map(|_| 0));
            let x0 = ring.indeterminate(0);
            let x1 = ring.indeterminate(1);
            let x0_v = ring.create_term(base_ring.one(), ring.clone_monomial(&x0));
            let x1_v = ring.create_term(base_ring.one(), ring.clone_monomial(&x1));
            let x0_2 = ring.create_monomial((0..n).map(|k| if k == 0 { 2 } else { 0 }));
            let x0_3 = ring.create_monomial((0..n).map(|k| if k == 0 { 3 } else { 0 }));
            let x0_4 = ring.create_monomial((0..n).map(|k| if k == 0 { 4 } else { 0 }));
            let x0x1 = ring.create_monomial((0..n).map(|k| if k == 0 || k == 1 { 1 } else { 0 }));
            let x0_3x1 = ring.create_monomial((0..n).map(|k| {
                if k == 0 {
                    3
                } else if k == 1 {
                    1
                } else {
                    0
                }
            }));
            let x1_2 = ring.create_monomial((0..n).map(|k| if k == 1 { 2 } else { 0 }));

            // test product
            for a in &elements {
                for b in &elements {
                    for c in &elements {
                        let f = ring.add(
                            ring.inclusion().mul_ref_map(&x0_v, a),
                            ring.inclusion().mul_ref_map(&x1_v, b),
                        );
                        let g = ring.add(ring.inclusion().mul_ref_map(&x0_v, c), ring.clone_el(&x1_v));
                        let h = ring.from_terms(
                            [
                                (base_ring.mul_ref(a, c), ring.clone_monomial(&x0_2)),
                                (
                                    base_ring.add_ref_snd(base_ring.mul_ref(b, c), a),
                                    ring.clone_monomial(&x0x1),
                                ),
                                (base_ring.clone_el(b), ring.clone_monomial(&x1_2)),
                            ]
                            .into_iter(),
                        );
                        assert_el_eq!(ring, h, ring.mul(f, g));
                    }
                }
            }

            // test sum
            for a in &elements {
                for b in &elements {
                    for c in &elements {
                        let f = ring.from_terms([
                            (base_ring.clone_el(a), ring.clone_monomial(&one)),
                            (base_ring.clone_el(c), ring.clone_monomial(&x0_2)),
                            (base_ring.one(), ring.clone_monomial(&x0x1)),
                        ]);
                        let g = ring.from_terms([
                            (base_ring.clone_el(b), ring.clone_monomial(&x0)),
                            (base_ring.one(), ring.clone_monomial(&x0_2)),
                        ]);
                        let h = ring.from_terms([
                            (base_ring.clone_el(a), ring.clone_monomial(&one)),
                            (base_ring.clone_el(b), ring.clone_monomial(&x0)),
                            (base_ring.add_ref_fst(c, base_ring.one()), ring.clone_monomial(&x0_2)),
                            (base_ring.one(), ring.clone_monomial(&x0x1)),
                        ]);
                        assert_el_eq!(ring, h, ring.add(f, g));
                    }
                }
            }

            // test mul_assign_monomial
            for a in &elements {
                for b in &elements {
                    for c in &elements {
                        let mut f = ring.from_terms([
                            (base_ring.clone_el(a), ring.clone_monomial(&one)),
                            (base_ring.clone_el(b), ring.clone_monomial(&x0)),
                            (base_ring.clone_el(c), ring.clone_monomial(&x0_2)),
                            (base_ring.one(), ring.clone_monomial(&x0x1)),
                        ]);
                        let h = ring.from_terms([
                            (base_ring.clone_el(a), ring.clone_monomial(&x0_2)),
                            (base_ring.clone_el(b), ring.clone_monomial(&x0_3)),
                            (base_ring.clone_el(c), ring.clone_monomial(&x0_4)),
                            (base_ring.one(), ring.clone_monomial(&x0_3x1)),
                        ]);
                        let m = ring.clone_monomial(&x0_2);
                        ring.mul_assign_monomial(&mut f, m);
                        assert_el_eq!(ring, h, f);
                    }
                }
            }

            // test evaluate
            for a in &elements {
                for b in &elements {
                    let f = ring.from_terms([
                        (base_ring.int_hom().map(3), ring.clone_monomial(&one)),
                        (base_ring.int_hom().map(10), ring.clone_monomial(&x0)),
                        (base_ring.neg_one(), ring.clone_monomial(&x0_2)),
                        (base_ring.one(), ring.clone_monomial(&x0x1)),
                    ]);
                    let expected = <_ as RingStore>::sum(
                        base_ring,
                        [
                            base_ring.int_hom().map(3),
                            base_ring.int_hom().mul_ref_map(a, &10),
                            base_ring.negate(base_ring.pow(base_ring.clone_el(a), 2)),
                            base_ring.mul_ref(a, b),
                        ],
                    );
                    let values = [base_ring.clone_el(a), base_ring.clone_el(b)]
                        .into_iter()
                        .chain((0..(ring.indeterminate_count() - 2)).map(|_| base_ring.zero()))
                        .collect::<Vec<_>>();
                    assert_el_eq!(
                        &base_ring,
                        &expected,
                        &ring.evaluate(&f, values.into_clone_ring_els(base_ring), &base_ring.identity())
                    );
                }
            }
        }
    }
}