Coverage for sympy/polys/agca/modules.py : 32%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
""" Computations with modules over polynomial rings.
This module implements various classes that encapsulate groebner basis computations for modules. Most of them should not be instantiated by hand. Instead, use the constructing routines on objects you already have.
For example, to construct a free module over ``QQ[x, y]``, call ``QQ[x, y].free_module(rank)`` instead of the ``FreeModule`` constructor. In fact ``FreeModule`` is an abstract base class that should not be instantiated, the ``free_module`` method instead returns the implementing class ``FreeModulePolyRing``.
In general, the abstract base classes implement most functionality in terms of a few non-implemented methods. The concrete base classes supply only these non-implemented methods. They may also supply new implementations of the convenience methods, for example if there are faster algorithms available. """
# TODO # - module saturation # - module quotient/intersection for quotient rings # - free resoltutions / syzygies # - finding small/minimal generating sets # - ...
########################################################################## ## Abstract base classes ################################################# ##########################################################################
""" Abstract base class for modules.
Do not instantiate - use ring explicit constructors instead:
>>> from sympy import QQ >>> from sympy.abc import x >>> QQ.old_poly_ring(x).free_module(2) QQ[x]**2
Attributes:
- dtype - type of elements - ring - containing ring
Non-implemented methods:
- submodule - quotient_module - is_zero - is_submodule - multiply_ideal
The method convert likely needs to be changed in subclasses. """
self.ring = ring
""" Convert ``elem`` into internal representation of this module.
If ``M`` is not None, it should be a module containing it. """ if not isinstance(elem, self.dtype): raise CoercionFailed return elem
"""Generate a submodule.""" raise NotImplementedError
"""Generate a quotient module.""" raise NotImplementedError
if not isinstance(e, Module): e = self.submodule(*e) return self.quotient_module(e)
"""Return True if ``elem`` is an element of this module.""" try: self.convert(elem) return True except CoercionFailed: return False
return self.contains(elem)
""" Returns True if ``other`` is is a subset of ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> F.subset([(1, x), (x, 2)]) True >>> F.subset([(1/x, x), (x, 2)]) False """ return all(self.contains(x) for x in other)
return self.is_submodule(other) and other.is_submodule(self)
return not (self == other)
"""Returns True if ``self`` is a zero module.""" raise NotImplementedError
"""Returns True if ``other`` is a submodule of ``self``.""" raise NotImplementedError
""" Multiply ``self`` by the ideal ``other``. """ raise NotImplementedError
if not isinstance(e, Ideal): try: e = self.ring.ideal(e) except (CoercionFailed, NotImplementedError): return NotImplemented return self.multiply_ideal(e)
"""Return the identity homomorphism on ``self``.""" raise NotImplementedError
""" Base class for module element wrappers.
Use this class to wrap primitive data types as module elements. It stores a reference to the containing module, and implements all the arithmetic operators.
Attributes:
- module - containing module - data - internal data
Methods that likely need change in subclasses:
- add - mul - div - eq """
self.module = module self.data = data
"""Add data ``d1`` and ``d2``.""" return d1 + d2
"""Multiply module data ``m`` by coefficient d.""" return m * d
"""Divide module data ``m`` by coefficient d.""" return m / d
"""Return true if d1 and d2 represent the same element.""" return d1 == d2
if not isinstance(om, self.__class__) or om.module != self.module: try: om = self.module.convert(om) except CoercionFailed: return NotImplemented return self.__class__(self.module, self.add(self.data, om.data))
return self.__class__(self.module, self.mul(self.data, self.module.ring.convert(-1)))
if not isinstance(om, self.__class__) or om.module != self.module: try: om = self.module.convert(om) except CoercionFailed: return NotImplemented return self.__add__(-om)
return (-self).__add__(om)
if not isinstance(o, self.module.ring.dtype): try: o = self.module.ring.convert(o) except CoercionFailed: return NotImplemented return self.__class__(self.module, self.mul(self.data, o))
if not isinstance(o, self.module.ring.dtype): try: o = self.module.ring.convert(o) except CoercionFailed: return NotImplemented return self.__class__(self.module, self.div(self.data, o))
if not isinstance(om, self.__class__) or om.module != self.module: try: om = self.module.convert(om) except CoercionFailed: return False return self.eq(self.data, om.data)
return not self.__eq__(om)
########################################################################## ## Free Modules ########################################################## ##########################################################################
"""Element of a free module. Data stored as a tuple."""
return tuple(x + y for x, y in zip(d1, d2))
return tuple(x * p for x in d)
return tuple(x / p for x in d)
from sympy import sstr return '[' + ', '.join(sstr(x) for x in self.data) + ']'
return self.data.__iter__()
return self.data[idx]
""" Abstract base class for free modules.
Additional attributes:
- rank - rank of the free module
Non-implemented methods:
- submodule """
Module.__init__(self, ring) self.rank = rank
return repr(self.ring) + "**" + repr(self.rank)
""" Returns True if ``other`` is a submodule of ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> M = F.submodule([2, x]) >>> F.is_submodule(F) True >>> F.is_submodule(M) True >>> M.is_submodule(F) False """ if isinstance(other, SubModule): return other.container == self if isinstance(other, FreeModule): return other.ring == self.ring and other.rank == self.rank return False
""" Convert ``elem`` into the internal representation.
This method is called implicitly whenever computations involve elements not in the internal representation.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> F.convert([1, 0]) [1, 0] """ if isinstance(elem, FreeModuleElement): if elem.module is self: return elem if elem.module.rank != self.rank: raise CoercionFailed return FreeModuleElement(self, tuple(self.ring.convert(x, elem.module.ring) for x in elem.data)) elif iterable(elem): tpl = tuple(self.ring.convert(x) for x in elem) if len(tpl) != self.rank: raise CoercionFailed return FreeModuleElement(self, tpl) elif elem is 0: return FreeModuleElement(self, (self.ring.convert(0),)*self.rank) else: raise CoercionFailed
""" Returns True if ``self`` is a zero module.
(If, as this implementation assumes, the coefficient ring is not the zero ring, then this is equivalent to the rank being zero.)
>>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).free_module(0).is_zero() True >>> QQ.old_poly_ring(x).free_module(1).is_zero() False """ return self.rank == 0
""" Return a set of basis elements.
>>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).free_module(3).basis() ([1, 0, 0], [0, 1, 0], [0, 0, 1]) """ from sympy.matrices import eye M = eye(self.rank) return tuple(self.convert(M.row(i)) for i in range(self.rank))
""" Return a quotient module.
>>> from sympy.abc import x >>> from sympy import QQ >>> M = QQ.old_poly_ring(x).free_module(2) >>> M.quotient_module(M.submodule([1, x], [x, 2])) QQ[x]**2/<[1, x], [x, 2]>
Or more conicisely, using the overloaded division operator:
>>> QQ.old_poly_ring(x).free_module(2) / [[1, x], [x, 2]] QQ[x]**2/<[1, x], [x, 2]> """ return QuotientModule(self.ring, self, submodule)
""" Multiply ``self`` by the ideal ``other``.
>>> from sympy.abc import x >>> from sympy import QQ >>> I = QQ.old_poly_ring(x).ideal(x) >>> F = QQ.old_poly_ring(x).free_module(2) >>> F.multiply_ideal(I) <[x, 0], [0, x]> """ return self.submodule(*self.basis()).multiply_ideal(other)
""" Return the identity homomorphism on ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).free_module(2).identity_hom() Matrix([ [1, 0], : QQ[x]**2 -> QQ[x]**2 [0, 1]]) """ from sympy.polys.agca.homomorphisms import homomorphism return homomorphism(self, self, self.basis())
""" Free module over a generalized polynomial ring.
Do not instantiate this, use the constructor method of the ring instead:
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(3) >>> F QQ[x]**3 >>> F.contains([x, 1, 0]) True >>> F.contains([1/x, 0, 1]) False """
from sympy.polys.domains.old_polynomialring import PolynomialRingBase FreeModule.__init__(self, ring, rank) if not isinstance(ring, PolynomialRingBase): raise NotImplementedError('This implementation only works over ' + 'polynomial rings, got %s' % ring) if not isinstance(ring.dom, Field): raise NotImplementedError('Ground domain must be a field, ' + 'got %s' % ring.dom)
""" Generate a submodule.
>>> from sympy.abc import x, y >>> from sympy import QQ >>> M = QQ.old_poly_ring(x, y).free_module(2).submodule([x, x + y]) >>> M <[x, x + y]> >>> M.contains([2*x, 2*x + 2*y]) True >>> M.contains([x, y]) False """ return SubModulePolyRing(gens, self, **opts)
""" Free module over a quotient ring.
Do not instantiate this, use the constructor method of the ring instead:
>>> from sympy.abc import x >>> from sympy import QQ >>> F = (QQ.old_poly_ring(x)/[x**2 + 1]).free_module(3) >>> F (QQ[x]/<x**2 + 1>)**3
Attributes
- quot - the quotient module `R^n / IR^n`, where `R/I` is our ring """
from sympy.polys.domains.quotientring import QuotientRing FreeModule.__init__(self, ring, rank) if not isinstance(ring, QuotientRing): raise NotImplementedError('This implementation only works over ' + 'quotient rings, got %s' % ring) F = self.ring.ring.free_module(self.rank) self.quot = F / (self.ring.base_ideal*F)
return "(" + repr(self.ring) + ")" + "**" + repr(self.rank)
""" Generate a submodule.
>>> from sympy.abc import x, y >>> from sympy import QQ >>> M = (QQ.old_poly_ring(x, y)/[x**2 - y**2]).free_module(2).submodule([x, x + y]) >>> M <[x + <x**2 - y**2>, x + y + <x**2 - y**2>]> >>> M.contains([y**2, x**2 + x*y]) True >>> M.contains([x, y]) False """ return SubModuleQuotientRing(gens, self, **opts)
""" Lift the element ``elem`` of self to the module self.quot.
Note that self.quot is the same set as self, just as an R-module and not as an R/I-module, so this makes sense.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = (QQ.old_poly_ring(x)/[x**2 + 1]).free_module(2) >>> e = F.convert([1, 0]) >>> e [1 + <x**2 + 1>, 0 + <x**2 + 1>] >>> L = F.quot >>> l = F.lift(e) >>> l [1, 0] + <[x**2 + 1, 0], [0, x**2 + 1]> >>> L.contains(l) True """ return self.quot.convert([x.data for x in elem])
""" Push down an element of self.quot to self.
This undoes ``lift``.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = (QQ.old_poly_ring(x)/[x**2 + 1]).free_module(2) >>> e = F.convert([1, 0]) >>> l = F.lift(e) >>> e == l False >>> e == F.unlift(l) True """ return self.convert(elem.data)
########################################################################## ## Submodules and subquotients ########################################### ##########################################################################
""" Base class for submodules.
Attributes:
- container - containing module - gens - generators (subset of containing module) - rank - rank of containing module
Non-implemented methods:
- _contains - _syzygies - _in_terms_of_generators - _intersect - _module_quotient
Methods that likely need change in subclasses:
- reduce_element """
Module.__init__(self, container.ring) self.gens = tuple(container.convert(x) for x in gens) self.container = container self.rank = container.rank self.ring = container.ring self.dtype = container.dtype
return "<" + ", ".join(repr(x) for x in self.gens) + ">"
"""Implementation of containment. Other is guaranteed to be FreeModuleElement.""" raise NotImplementedError
"""Implementation of syzygy computation wrt self generators.""" raise NotImplementedError
"""Implementation of expression in terms of generators.""" raise NotImplementedError
""" Convert ``elem`` into the internal represantition.
Mostly called implicitly.
>>> from sympy.abc import x >>> from sympy import QQ >>> M = QQ.old_poly_ring(x).free_module(2).submodule([1, x]) >>> M.convert([2, 2*x]) [2, 2*x] """ if isinstance(elem, self.container.dtype) and elem.module is self: return elem r = copy(self.container.convert(elem, M)) r.module = self if not self._contains(r): raise CoercionFailed return r
"""Implementation of intersection. Other is guaranteed to be a submodule of same free module.""" raise NotImplementedError
"""Implementation of quotient. Other is guaranteed to be a submodule of same free module.""" raise NotImplementedError
""" Returns the intersection of ``self`` with submodule ``other``.
>>> from sympy.abc import x, y >>> from sympy import QQ >>> F = QQ.old_poly_ring(x, y).free_module(2) >>> F.submodule([x, x]).intersect(F.submodule([y, y])) <[x*y, x*y]>
Some implementation allow further options to be passed. Currently, to only one implemented is ``relations=True``, in which case the function will return a triple ``(res, rela, relb)``, where ``res`` is the intersection module, and ``rela`` and ``relb`` are lists of coefficient vectors, expressing the generators of ``res`` in terms of the generators of ``self`` (``rela``) and ``other`` (``relb``).
>>> F.submodule([x, x]).intersect(F.submodule([y, y]), relations=True) (<[x*y, x*y]>, [(y,)], [(x,)])
The above result says: the intersection module is generated by the single element `(-xy, -xy) = -y (x, x) = -x (y, y)`, where `(x, x)` and `(y, y)` respectively are the unique generators of the two modules being intersected. """ if not isinstance(other, SubModule): raise TypeError('%s is not a SubModule' % other) if other.container != self.container: raise ValueError( '%s is contained in a different free module' % other) return self._intersect(other, **options)
r""" Returns the module quotient of ``self`` by submodule ``other``.
That is, if ``self`` is the module `M` and ``other`` is `N`, then return the ideal `\{f \in R | fN \subset M\}`.
>>> from sympy import QQ >>> from sympy.abc import x, y >>> F = QQ.old_poly_ring(x, y).free_module(2) >>> S = F.submodule([x*y, x*y]) >>> T = F.submodule([x, x]) >>> S.module_quotient(T) <y>
Some implementations allow further options to be passed. Currently, the only one implemented is ``relations=True``, which may only be passed if ``other`` is prinicipal. In this case the function will return a pair ``(res, rel)`` where ``res`` is the ideal, and ``rel`` is a list of coefficient vectors, expressing the generators of the ideal, multiplied by the generator of ``other`` in terms of generators of ``self``.
>>> S.module_quotient(T, relations=True) (<y>, [[1]])
This means that the quotient ideal is generated by the single element `y`, and that `y (x, x) = 1 (xy, xy)`, `(x, x)` and `(xy, xy)` being the generators of `T` and `S`, respectively. """ if not isinstance(other, SubModule): raise TypeError('%s is not a SubModule' % other) if other.container != self.container: raise ValueError( '%s is contained in a different free module' % other) return self._module_quotient(other, **options)
""" Returns the module generated by the union of ``self`` and ``other``.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(1) >>> M = F.submodule([x**2 + x]) # <x(x+1)> >>> N = F.submodule([x**2 - 1]) # <(x-1)(x+1)> >>> M.union(N) == F.submodule([x+1]) True """ if not isinstance(other, SubModule): raise TypeError('%s is not a SubModule' % other) if other.container != self.container: raise ValueError( '%s is contained in a different free module' % other) return self.__class__(self.gens + other.gens, self.container)
""" Return True if ``self`` is a zero module.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> F.submodule([x, 1]).is_zero() False >>> F.submodule([0, 0]).is_zero() True """ return all(x == 0 for x in self.gens)
""" Generate a submodule.
>>> from sympy.abc import x >>> from sympy import QQ >>> M = QQ.old_poly_ring(x).free_module(2).submodule([x, 1]) >>> M.submodule([x**2, x]) <[x**2, x]> """ if not self.subset(gens): raise ValueError('%s not a subset of %s' % (gens, self)) return self.__class__(gens, self.container)
""" Return True if ``self`` is the entire free module.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> F.submodule([x, 1]).is_full_module() False >>> F.submodule([1, 1], [1, 2]).is_full_module() True """ return all(self.contains(x) for x in self.container.basis())
""" Returns True if ``other`` is a submodule of ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> M = F.submodule([2, x]) >>> N = M.submodule([2*x, x**2]) >>> M.is_submodule(M) True >>> M.is_submodule(N) True >>> N.is_submodule(M) False """ if isinstance(other, SubModule): return self.container == other.container and \ all(self.contains(x) for x in other.gens) if isinstance(other, (FreeModule, QuotientModule)): return self.container == other and self.is_full_module() return False
r""" Compute the syzygy module of the generators of ``self``.
Suppose `M` is generated by `f_1, \dots, f_n` over the ring `R`. Consider the homomorphism `\phi: R^n \to M`, given by sending `(r_1, \dots, r_n) \to r_1 f_1 + \dots + r_n f_n`. The syzygy module is defined to be the kernel of `\phi`.
The syzygy module is zero iff the generators generate freely a free submodule:
>>> from sympy.abc import x, y >>> from sympy import QQ >>> QQ.old_poly_ring(x).free_module(2).submodule([1, 0], [1, 1]).syzygy_module().is_zero() True
A slightly more interesting example:
>>> M = QQ.old_poly_ring(x, y).free_module(2).submodule([x, 2*x], [y, 2*y]) >>> S = QQ.old_poly_ring(x, y).free_module(2).submodule([y, -x]) >>> M.syzygy_module() == S True """ F = self.ring.free_module(len(self.gens)) # NOTE we filter out zero syzygies. This is for convenience of the # _syzygies function and not meant to replace any real "generating set # reduction" algorithm return F.submodule(*[x for x in self._syzygies() if F.convert(x) != 0], **opts)
""" Express element ``e`` of ``self`` in terms of the generators.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> M = F.submodule([1, 0], [1, 1]) >>> M.in_terms_of_generators([x, x**2]) [-x**2 + x, x**2] """ try: e = self.convert(e) except CoercionFailed: raise ValueError('%s is not an element of %s' % (e, self)) return self._in_terms_of_generators(e)
""" Reduce the element ``x`` of our ring modulo the ideal ``self``.
Here "reduce" has no specific meaning, it could return a unique normal form, simplify the expression a bit, or just do nothing. """ return x
""" Return a quotient module.
This is the same as taking a submodule of a quotient of the containing module.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> S1 = F.submodule([x, 1]) >>> S2 = F.submodule([x**2, x]) >>> S1.quotient_module(S2) <[x, 1] + <[x**2, x]>>
Or more coincisely, using the overloaded division operator:
>>> F.submodule([x, 1]) / [(x**2, x)] <[x, 1] + <[x**2, x]>> """ if not self.is_submodule(other): raise ValueError('%s not a submodule of %s' % (other, self)) return SubQuotientModule(self.gens, self.container.quotient_module(other), **opts)
return self.container.quotient_module(self).convert(oth)
""" Multiply ``self`` by the ideal ``I``.
>>> from sympy.abc import x >>> from sympy import QQ >>> I = QQ.old_poly_ring(x).ideal(x**2) >>> M = QQ.old_poly_ring(x).free_module(2).submodule([1, 1]) >>> I*M <[x**2, x**2]> """ return self.submodule(*[x*g for [x] in I._module.gens for g in self.gens])
""" Return a homomorphism representing the inclusion map of ``self``.
That is, the natural map from ``self`` to ``self.container``.
>>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).free_module(2).submodule([x, x]).inclusion_hom() Matrix([ [1, 0], : <[x, x]> -> QQ[x]**2 [0, 1]]) """ return self.container.identity_hom().restrict_domain(self)
""" Return the identity homomorphism on ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> QQ.old_poly_ring(x).free_module(2).submodule([x, x]).identity_hom() Matrix([ [1, 0], : <[x, x]> -> <[x, x]> [0, 1]]) """ return self.container.identity_hom().restrict_domain( self).restrict_codomain(self)
""" Submodule of a quotient module.
Equivalently, quotient module of a submodule.
Do not instantiate this, instead use the submodule or quotient_module constructing methods:
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> S = F.submodule([1, 0], [1, x]) >>> Q = F/[(1, 0)] >>> S/[(1, 0)] == Q.submodule([5, x]) True
Attributes:
- base - base module we are quotient of - killed_module - submodule used to form the quotient """ SubModule.__init__(self, gens, container) self.killed_module = self.container.killed_module # XXX it is important for some code below that the generators of base # are in this particular order! self.base = self.container.base.submodule( *[x.data for x in self.gens], **opts).union(self.killed_module)
return self.base.contains(elem.data)
# let N = self.killed_module be generated by e_1, ..., e_r # let F = self.base be generated by f_1, ..., f_s and e_1, ..., e_r # Then self = F/N. # Let phi: R**s --> self be the evident surjection. # Similarly psi: R**(s + r) --> F. # We need to find generators for ker(phi). Let chi: R**s --> F be the # evident lift of phi. For X in R**s, phi(X) = 0 iff chi(X) is # contained in N, iff there exists Y in R**r such that # psi(X, Y) = 0. # Hence if alpha: R**(s + r) --> R**s is the projection map, then # ker(phi) = alpha ker(psi). return [X[:len(self.gens)] for X in self.base._syzygies()]
return self.base._in_terms_of_generators(e.data)[:len(self.gens)]
""" Return True if ``self`` is the entire free module.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> F.submodule([x, 1]).is_full_module() False >>> F.submodule([1, 1], [1, 2]).is_full_module() True """ return self.base.is_full_module()
""" Return the quotient homomorphism to self.
That is, return the natural map from ``self.base`` to ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> M = (QQ.old_poly_ring(x).free_module(2) / [(1, x)]).submodule([1, 0]) >>> M.quotient_hom() Matrix([ [1, 0], : <[1, 0], [1, x]> -> <[1, 0] + <[1, x]>, [1, x] + <[1, x]>> [0, 1]]) """ return self.base.identity_hom().quotient_codomain(self.killed_module)
"""A product monomial order with a zeroth term as module index."""
if TOP: ProductOrder.__init__(self, (o2, _subs1), (o1, _subs0)) else: ProductOrder.__init__(self, (o1, _subs0), (o2, _subs1))
""" Submodule of a free module over a generalized polynomial ring.
Do not instantiate this, use the constructor method of FreeModule instead:
>>> from sympy.abc import x, y >>> from sympy import QQ >>> F = QQ.old_poly_ring(x, y).free_module(2) >>> F.submodule([x, y], [1, 0]) <[x, y], [1, 0]>
Attributes:
- order - monomial order used """
#self._gb - cached groebner basis #self._gbe - cached groebner basis relations
SubModule.__init__(self, gens, container) if not isinstance(container, FreeModulePolyRing): raise NotImplementedError('This implementation is for submodules of ' + 'FreeModulePolyRing, got %s' % container) self.order = ModuleOrder(monomial_key(order), self.ring.order, TOP) self._gb = None self._gbe = None
if isinstance(other, SubModulePolyRing) and self.order != other.order: return False return SubModule.__eq__(self, other)
"""Returns a standard basis in sdm form.""" from sympy.polys.distributedmodules import sdm_groebner, sdm_nf_mora if self._gbe is None and extended: gb, gbe = sdm_groebner( [self.ring._vector_to_sdm(x, self.order) for x in self.gens], sdm_nf_mora, self.order, self.ring.dom, extended=True) self._gb, self._gbe = tuple(gb), tuple(gbe) if self._gb is None: self._gb = tuple(sdm_groebner( [self.ring._vector_to_sdm(x, self.order) for x in self.gens], sdm_nf_mora, self.order, self.ring.dom)) if extended: return self._gb, self._gbe else: return self._gb
"""Returns a standard basis in element form.""" if not extended: return [self.convert(self.ring._sdm_to_vector(x, self.rank)) for x in self._groebner()] gb, gbe = self._groebner(extended=True) return ([self.convert(self.ring._sdm_to_vector(x, self.rank)) for x in gb], [self.ring._sdm_to_vector(x, len(self.gens)) for x in gbe])
from sympy.polys.distributedmodules import sdm_zero, sdm_nf_mora return sdm_nf_mora(self.ring._vector_to_sdm(x, self.order), self._groebner(), self.order, self.ring.dom) == \ sdm_zero()
"""Compute syzygies. See [SCA, algorithm 2.5.4].""" # NOTE if self.gens is a standard basis, this can be done more # efficiently using Schreyer's theorem from sympy.matrices import eye
# First bullet point k = len(self.gens) r = self.rank im = eye(k) Rkr = self.ring.free_module(r + k) newgens = [] for j, f in enumerate(self.gens): m = [0]*(r + k) for i, v in enumerate(f): m[i] = f[i] for i in range(k): m[r + i] = im[j, i] newgens.append(Rkr.convert(m)) # Note: we need *descending* order on module index, and TOP=False to # get an eliminetaion order F = Rkr.submodule(*newgens, order='ilex', TOP=False)
# Second bullet point: standard basis of F G = F._groebner_vec()
# Third bullet point: G0 = G intersect the new k components G0 = [x[r:] for x in G if all(y == self.ring.convert(0) for y in x[:r])]
# Fourth and fifth bullet points: we are done return G0
"""Expression in terms of generators. See [SCA, 2.8.1].""" # NOTE: if gens is a standard basis, this can be done more efficiently M = self.ring.free_module(self.rank).submodule(*((e,) + self.gens)) S = M.syzygy_module( order="ilex", TOP=False) # We want decreasing order! G = S._groebner_vec() # This list cannot not be empty since e is an element e = [x for x in G if self.ring.is_unit(x[0])][0] return [-x/e[0] for x in e[1:]]
""" Reduce the element ``x`` of our container modulo ``self``.
This applies the normal form ``NF`` to ``x``. If ``NF`` is passed as none, the default Mora normal form is used (which is not unique!). """ from sympy.polys.distributedmodules import sdm_nf_mora if NF is None: NF = sdm_nf_mora return self.container.convert(self.ring._sdm_to_vector(NF( self.ring._vector_to_sdm(x, self.order), self._groebner(), self.order, self.ring.dom), self.rank))
# See: [SCA, section 2.8.2] fi = self.gens hi = other.gens r = self.rank ci = [[0]*(2*r) for _ in range(r)] for k in range(r): ci[k][k] = 1 ci[k][r + k] = 1 di = [list(f) + [0]*r for f in fi] ei = [[0]*r + list(h) for h in hi] syz = self.ring.free_module(2*r).submodule(*(ci + di + ei))._syzygies() nonzero = [x for x in syz if any(y != self.ring.zero for y in x[:r])] res = self.container.submodule(*([-y for y in x[:r]] for x in nonzero)) reln1 = [x[r:r + len(fi)] for x in nonzero] reln2 = [x[r + len(fi):] for x in nonzero] if relations: return res, reln1, reln2 return res
# See: [SCA, section 2.8.4] if relations and len(other.gens) != 1: raise NotImplementedError if len(other.gens) == 0: return self.ring.ideal(1) elif len(other.gens) == 1: # We do some trickery. Let f be the (vector!) generating ``other`` # and f1, .., fn be the (vectors) generating self. # Consider the submodule of R^{r+1} generated by (f, 1) and # {(fi, 0) | i}. Then the intersection with the last module # component yields the quotient. g1 = list(other.gens[0]) + [1] gi = [list(x) + [0] for x in self.gens] # NOTE: We *need* to use an elimination order M = self.ring.free_module(self.rank + 1).submodule(*([g1] + gi), order='ilex', TOP=False) if not relations: return self.ring.ideal(*[x[-1] for x in M._groebner_vec() if all(y == self.ring.zero for y in x[:-1])]) else: G, R = M._groebner_vec(extended=True) indices = [i for i, x in enumerate(G) if all(y == self.ring.zero for y in x[:-1])] return (self.ring.ideal(*[G[i][-1] for i in indices]), [[-x for x in R[i][1:]] for i in indices]) # For more generators, we use I : <h1, .., hn> = intersection of # {I : <hi> | i} # TODO this can be done more efficiently return reduce(lambda x, y: x.intersect(y), (self._module_quotient(self.container.submodule(x)) for x in other.gens))
""" Class for submodules of free modules over quotient rings.
Do not instantiate this. Instead use the submodule methods.
>>> from sympy.abc import x, y >>> from sympy import QQ >>> M = (QQ.old_poly_ring(x, y)/[x**2 - y**2]).free_module(2).submodule([x, x + y]) >>> M <[x + <x**2 - y**2>, x + y + <x**2 - y**2>]> >>> M.contains([y**2, x**2 + x*y]) True >>> M.contains([x, y]) False
Attributes:
- quot - the subquotient of `R^n/IR^n` generated by lifts of our generators """
SubModule.__init__(self, gens, container) self.quot = self.container.quot.submodule( *[self.container.lift(x) for x in self.gens])
return self.quot._contains(self.container.lift(elem))
return [tuple(self.ring.convert(y, self.quot.ring) for y in x) for x in self.quot._syzygies()]
return [self.ring.convert(x, self.quot.ring) for x in self.quot._in_terms_of_generators(self.container.lift(elem))]
########################################################################## ## Quotient Modules ###################################################### ##########################################################################
"""Element of a quotient module."""
"""Equality comparison.""" return self.module.killed_module.contains(d1 - d2)
return repr(self.data) + " + " + repr(self.module.killed_module)
""" Class for quotient modules.
Do not instantiate this directly. For subquotients, see the SubQuotientModule class.
Attributes:
- base - the base module we are a quotient of - killed_module - the submodule used to form the quotient - rank of the base """
Module.__init__(self, ring) if not base.is_submodule(submodule): raise ValueError('%s is not a submodule of %s' % (submodule, base)) self.base = base self.killed_module = submodule self.rank = base.rank
return repr(self.base) + "/" + repr(self.killed_module)
""" Return True if ``self`` is a zero module.
This happens if and only if the base module is the same as the submodule being killed.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) >>> (F/[(1, 0)]).is_zero() False >>> (F/[(1, 0), (0, 1)]).is_zero() True """ return self.base == self.killed_module
""" Return True if ``other`` is a submodule of ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> Q = QQ.old_poly_ring(x).free_module(2) / [(x, x)] >>> S = Q.submodule([1, 0]) >>> Q.is_submodule(S) True >>> S.is_submodule(Q) False """ if isinstance(other, QuotientModule): return self.killed_module == other.killed_module and \ self.base.is_submodule(other.base) if isinstance(other, SubQuotientModule): return other.container == self return False
""" Generate a submodule.
This is the same as taking a quotient of a submodule of the base module.
>>> from sympy.abc import x >>> from sympy import QQ >>> Q = QQ.old_poly_ring(x).free_module(2) / [(x, x)] >>> Q.submodule([x, 0]) <[x, 0] + <[x, x]>> """ return SubQuotientModule(gens, self, **opts)
""" Convert ``elem`` into the internal representation.
This method is called implicitly whenever computations involve elements not in the internal representation.
>>> from sympy.abc import x >>> from sympy import QQ >>> F = QQ.old_poly_ring(x).free_module(2) / [(1, 2), (1, x)] >>> F.convert([1, 0]) [1, 0] + <[1, 2], [1, x]> """ if isinstance(elem, QuotientModuleElement): if elem.module is self: return elem if self.killed_module.is_submodule(elem.module.killed_module): return QuotientModuleElement(self, self.base.convert(elem.data)) raise CoercionFailed return QuotientModuleElement(self, self.base.convert(elem))
""" Return the identity homomorphism on ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> M = QQ.old_poly_ring(x).free_module(2) / [(1, 2), (1, x)] >>> M.identity_hom() Matrix([ [1, 0], : QQ[x]**2/<[1, 2], [1, x]> -> QQ[x]**2/<[1, 2], [1, x]> [0, 1]]) """ return self.base.identity_hom().quotient_codomain( self.killed_module).quotient_domain(self.killed_module)
""" Return the quotient homomorphism to ``self``.
That is, return a homomorphism representing the natural map from ``self.base`` to ``self``.
>>> from sympy.abc import x >>> from sympy import QQ >>> M = QQ.old_poly_ring(x).free_module(2) / [(1, 2), (1, x)] >>> M.quotient_hom() Matrix([ [1, 0], : QQ[x]**2 -> QQ[x]**2/<[1, 2], [1, x]> [0, 1]]) """ return self.base.identity_hom().quotient_codomain( self.killed_module) |