Coverage for sympy/polys/agca/ideals.py : 46%

"""Computations with ideals of polynomial rings.""" 

from __future__ import print_function, division 

from sympy.polys.polyerrors import CoercionFailed 

from sympy.core.compatibility import reduce 

class Ideal(object): 

""" 

Abstract base class for ideals. 

Do not instantiate - use explicit constructors in the ring class instead: 

>>> from sympy import QQ 

>>> from sympy.abc import x 

>>> QQ.old_poly_ring(x).ideal(x+1) 

<x + 1> 

Attributes 

- ring - the ring this ideal belongs to 

Non-implemented methods: 

- _contains_elem 

- _contains_ideal 

- _quotient 

- _intersect 

- _union 

- _product 

- is_whole_ring 

- is_zero 

- is_prime, is_maximal, is_primary, is_radical 

- is_principal 

- height, depth 

- radical 

Methods that likely should be overridden in subclasses: 

- reduce_element 

""" 

def _contains_elem(self, x): 

"""Implementation of element containment.""" 

raise NotImplementedError 

def _contains_ideal(self, I): 

"""Implementation of ideal containment.""" 

raise NotImplementedError 

def _quotient(self, J): 

"""Implementation of ideal quotient.""" 

raise NotImplementedError 

def _intersect(self, J): 

"""Implementation of ideal intersection.""" 

raise NotImplementedError 

def is_whole_ring(self): 

"""Return True if ``self`` is the whole ring.""" 

raise NotImplementedError 

def is_zero(self): 

"""Return True if ``self`` is the zero ideal.""" 

raise NotImplementedError 

def _equals(self, J): 

"""Implementation of ideal equality.""" 

return self._contains_ideal(J) and J._contains_ideal(self) 

def is_prime(self): 

"""Return True if ``self`` is a prime ideal.""" 

raise NotImplementedError 

def is_maximal(self): 

"""Return True if ``self`` is a maximal ideal.""" 

raise NotImplementedError 

def is_radical(self): 

"""Return True if ``self`` is a radical ideal.""" 

raise NotImplementedError 

def is_primary(self): 

"""Return True if ``self`` is a primary ideal.""" 

raise NotImplementedError 

def is_principal(self): 

"""Return True if ``self`` is a principal ideal.""" 

raise NotImplementedError 

def radical(self): 

"""Compute the radical of ``self``.""" 

raise NotImplementedError 

def depth(self): 

"""Compute the depth of ``self``.""" 

raise NotImplementedError 

def height(self): 

"""Compute the height of ``self``.""" 

raise NotImplementedError 

# TODO more 

# non-implemented methods end here 

def __init__(self, ring): 

self.ring = ring 

def _check_ideal(self, J): 

"""Helper to check ``J`` is an ideal of our ring.""" 

if not isinstance(J, Ideal) or J.ring != self.ring: 

raise ValueError( 

'J must be an ideal of %s, got %s' % (self.ring, J)) 

def contains(self, elem): 

""" 

Return True if ``elem`` is an element of this ideal. 

>>> from sympy.abc import x 

>>> from sympy import QQ 

>>> QQ.old_poly_ring(x).ideal(x+1, x-1).contains(3) 

True 

>>> QQ.old_poly_ring(x).ideal(x**2, x**3).contains(x) 

False 

""" 

return self._contains_elem(self.ring.convert(elem)) 

def subset(self, other): 

""" 

Returns True if ``other`` is is a subset of ``self``. 

Here ``other`` may be an ideal. 

>>> from sympy.abc import x 

>>> from sympy import QQ 

>>> I = QQ.old_poly_ring(x).ideal(x+1) 

>>> I.subset([x**2 - 1, x**2 + 2*x + 1]) 

True 

>>> I.subset([x**2 + 1, x + 1]) 

False 

>>> I.subset(QQ.old_poly_ring(x).ideal(x**2 - 1)) 

True 

""" 

if isinstance(other, Ideal): 

return self._contains_ideal(other) 

return all(self._contains_elem(x) for x in other) 

def quotient(self, J, **opts): 

r""" 

Compute the ideal quotient of ``self`` by ``J``. 

That is, if ``self`` is the ideal `I`, compute the set 

`I : J = \{x \in R | xJ \subset I \}`. 

>>> from sympy.abc import x, y 

>>> from sympy import QQ 

>>> R = QQ.old_poly_ring(x, y) 

>>> R.ideal(x*y).quotient(R.ideal(x)) 

<y> 

""" 

self._check_ideal(J) 

return self._quotient(J, **opts) 

def intersect(self, J): 

""" 

Compute the intersection of self with ideal J. 

>>> from sympy.abc import x, y 

>>> from sympy import QQ 

>>> R = QQ.old_poly_ring(x, y) 

>>> R.ideal(x).intersect(R.ideal(y)) 

<x*y> 

""" 

self._check_ideal(J) 

return self._intersect(J) 

def saturate(self, J): 

r""" 

Compute the ideal saturation of ``self`` by ``J``. 

That is, if ``self`` is the ideal `I`, compute the set 

`I : J^\infty = \{x \in R | xJ^n \subset I \text{ for some } n\}`. 

""" 

raise NotImplementedError 

# Note this can be implemented using repeated quotient 

def union(self, J): 

""" 

Compute the ideal generated by the union of ``self`` and ``J``. 

>>> from sympy.abc import x 

>>> from sympy import QQ 

>>> QQ.old_poly_ring(x).ideal(x**2 - 1).union(QQ.old_poly_ring(x).ideal((x+1)**2)) == QQ.old_poly_ring(x).ideal(x+1) 

True 

""" 

self._check_ideal(J) 

return self._union(J) 

def product(self, J): 

""" 

Compute the ideal product of ``self`` and ``J``. 

That is, compute the ideal generated by products `xy`, for `x` an element 

of ``self`` and `y \in J`. 

>>> from sympy.abc import x, y 

>>> from sympy import QQ 

>>> QQ.old_poly_ring(x, y).ideal(x).product(QQ.old_poly_ring(x, y).ideal(y)) 

<x*y> 

""" 

self._check_ideal(J) 

return self._product(J) 

def reduce_element(self, x): 

""" 

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 

def __add__(self, e): 

if not isinstance(e, Ideal): 

R = self.ring.quotient_ring(self) 

if isinstance(e, R.dtype): 

return e 

if isinstance(e, R.ring.dtype): 

return R(e) 

return R.convert(e) 

self._check_ideal(e) 

return self.union(e) 

__radd__ = __add__ 

def __mul__(self, e): 

if not isinstance(e, Ideal): 

try: 

e = self.ring.ideal(e) 

except CoercionFailed: 

return NotImplemented 

self._check_ideal(e) 

return self.product(e) 

__rmul__ = __mul__ 

def __pow__(self, exp): 

if exp < 0: 

raise NotImplementedError 

# TODO exponentiate by squaring 

return reduce(lambda x, y: x*y, [self]*exp, self.ring.ideal(1)) 

def __eq__(self, e): 

if not isinstance(e, Ideal) or e.ring != self.ring: 

return False 

return self._equals(e) 

def __ne__(self, e): 

return not (self == e) 

class ModuleImplementedIdeal(Ideal): 

""" 

Ideal implementation relying on the modules code. 

Attributes: 

- _module - the underlying module 

""" 

def __init__(self, ring, module): 

Ideal.__init__(self, ring) 

self._module = module 

def _contains_elem(self, x): 

return self._module.contains([x]) 

def _contains_ideal(self, J): 

if not isinstance(J, ModuleImplementedIdeal): 

raise NotImplementedError 

return self._module.is_submodule(J._module) 

def _intersect(self, J): 

if not isinstance(J, ModuleImplementedIdeal): 

raise NotImplementedError 

return self.__class__(self.ring, self._module.intersect(J._module)) 

def _quotient(self, J, **opts): 

if not isinstance(J, ModuleImplementedIdeal): 

raise NotImplementedError 

return self._module.module_quotient(J._module, **opts) 

def _union(self, J): 

if not isinstance(J, ModuleImplementedIdeal): 

raise NotImplementedError 

return self.__class__(self.ring, self._module.union(J._module)) 

@property 

def gens(self): 

""" 

Return generators for ``self``. 

>>> from sympy import QQ 

>>> from sympy.abc import x, y 

>>> list(QQ.old_poly_ring(x, y).ideal(x, y, x**2 + y).gens) 

[x, y, x**2 + y] 

""" 

return (x[0] for x in self._module.gens) 

def is_zero(self): 

""" 

Return True if ``self`` is the zero ideal. 

>>> from sympy.abc import x 

>>> from sympy import QQ 

>>> QQ.old_poly_ring(x).ideal(x).is_zero() 

False 

>>> QQ.old_poly_ring(x).ideal().is_zero() 

True 

""" 

return self._module.is_zero() 

def is_whole_ring(self): 

""" 

Return True if ``self`` is the whole ring, i.e. one generator is a unit. 

>>> from sympy.abc import x 

>>> from sympy import QQ, ilex 

>>> QQ.old_poly_ring(x).ideal(x).is_whole_ring() 

False 

>>> QQ.old_poly_ring(x).ideal(3).is_whole_ring() 

True 

>>> QQ.old_poly_ring(x, order=ilex).ideal(2 + x).is_whole_ring() 

True 

""" 

return self._module.is_full_module() 

def __repr__(self): 

from sympy import sstr 

return '<' + ','.join(sstr(x) for [x] in self._module.gens) + '>' 

# NOTE this is the only method using the fact that the module is a SubModule 

def _product(self, J): 

if not isinstance(J, ModuleImplementedIdeal): 

raise NotImplementedError 

return self.__class__(self.ring, self._module.submodule( 

*[[x*y] for [x] in self._module.gens for [y] in J._module.gens])) 

def in_terms_of_generators(self, e): 

""" 

Express ``e`` in terms of the generators of ``self``. 

>>> from sympy.abc import x 

>>> from sympy import QQ 

>>> I = QQ.old_poly_ring(x).ideal(x**2 + 1, x) 

>>> I.in_terms_of_generators(1) 

[1, -x] 

""" 

return self._module.in_terms_of_generators([e]) 

def reduce_element(self, x, **options): 

return self._module.reduce_element([x], **options)[0]