source: sage/rings/polynomial/multi_polynomial_ideal.py @ 7513:c52f4c723299

Revision 7513:c52f4c723299, 55.0 KB checked in by Joel B. Mohler <jbm5@…>, 6 years ago (diff)

Rewrote hash functions for polynomial and fraction field elts to respect '=='
Line 
1"""
2Ideals in multivariate polynomial rings.
3
4Most functionality of multivariate polynomial ideals in SAGE is
5provided through SINGULAR.
6
7AUTHOR:
8    -- William Stein
9    -- Kiran S. Kedlaya (2006-02-12): added Macaulay2 analogues of
10              some Singular features
11    -- Martin Albrecht
12
13EXAMPLES:
14    sage: x,y,z = QQ['x,y,z'].gens()
15    sage: I = ideal(x^5 + y^4 + z^3 - 1,  x^3 + y^3 + z^2 - 1)
16    sage: B = I.groebner_basis()
17    sage: len(B)
18    3
19    sage: [f in I for f in I.gens()]
20    [True, True]
21
22    sage: f = I.gens()[0]
23    sage: I.reduce(f)
24    0
25
26    sage: g = I.gens()[1]
27    sage: I.reduce(g)
28    0
29
30    sage: I.reduce(g+x^2)
31    x^2
32   
33We compute a Groebner basis for cyclic 6, which is a standard
34benchmark and test ideal.
35   
36    sage: R.<x,y,z,t,u,v> = QQ['x,y,z,t,u,v']
37    sage: I = sage.rings.ideal.Cyclic(R,6)
38    sage: B = I.groebner_basis()
39    sage: len(B)
40    45
41
42We compute in a quotient of a polynomial ring over Z/17*Z:
43    sage: R.<x,y> = ZZ[]
44    sage: S.<a,b> = R.quotient((x^2 + y^2, 17))                 # optional -- requires Macaulay2
45    sage: S                                                     # optional
46    Quotient of Multivariate Polynomial Ring in x, y over Integer Ring by the ideal (x^2 + y^2, 17)
47    sage: a^2 + b^2 == 0                                        # optional
48    True
49    sage: a^3 - b^2                                             # optional
50    -1*a*b^2 - b^2
51    sage: (a+b)^17                                              # optional
52    a*b^16 + b^17
53    sage: S(17) == 0                                            # optional
54    True
55
56Working with a polynomial ring over ZZ:
57    sage: R.<x,y,z,w> = ZZ['x,y,z,w']             
58    sage: i = ideal(x^2 + y^2 - z^2 - w^2, x-y)
59    sage: j = i^2
60    sage: j.groebner_basis()                                    # optional
61    [x^2 - 2*x*y + y^2, 2*x*y^2 - 2*y^3 - x*z^2 + y*z^2 - x*w^2 + y*w^2, 4*y^4 - 4*y^2*z^2 + z^4 - 4*y^2*w^2 + 2*z^2*w^2 + w^4]
62    sage: y^2 - 2*x*y + x^2 in j                                # optional
63    True
64    sage: 0 in j                                                # optional
65    True
66
67We do a Groebner basis computation over a number field:
68    sage: K.<zeta> = CyclotomicField(3)
69    sage: R.<x,y,z> = K[]; R
70    Multivariate Polynomial Ring in x, y, z over Cyclotomic Field of order 3 and degree 2
71    sage: i = ideal(x - zeta*y + 1, x^3 - zeta*y^3); i
72    Ideal (x + (-zeta)*y + 1, x^3 + (-zeta)*y^3) of Multivariate Polynomial Ring in x, y, z over Cyclotomic Field of order 3 and degree 2
73    sage: i.groebner_basis()
74    [x + (-zeta)*y + 1, 3*y^3 + (6*zeta + 3)*y^2 + (3*zeta - 3)*y - zeta - 2]
75    sage: S = R.quotient(i); S
76    Quotient of Multivariate Polynomial Ring in x, y, z over Cyclotomic Field of order 3 and degree 2 by the ideal (x + (-zeta)*y + 1, x^3 + (-zeta)*y^3)
77    sage: S.0  - zeta*S.1
78    -1
79    sage: S.0^3 - zeta*S.1^3
80    0
81
82Two examples from the Mathematica documentation (done in SAGE):
83    We compute a Groebner basis:
84        sage: R.<x,y> = PolynomialRing(QQ, order='lex')
85        sage: ideal(x^2 - 2*y^2, x*y - 3).groebner_basis()
86        [2*y^4 - 9, 3*x - 2*y^3]   
87
88    We show that three polynomials have no common root:
89        sage: R.<x,y> = QQ[]
90        sage: ideal(x+y, x^2 - 1, y^2 - 2*x).groebner_basis()
91        [1]
92
93TESTS:
94    sage: x,y,z = QQ['x,y,z'].gens()
95    sage: I = ideal(x^5 + y^4 + z^3 - 1,  x^3 + y^3 + z^2 - 1)
96    sage: I == loads(dumps(I))
97    True
98
99"""
100
101#*****************************************************************************
102#
103#   SAGE: System for Algebra and Geometry Experimentation   
104#
105#       Copyright (C) 2005 William Stein <wstein@gmail.com>
106#
107#  Distributed under the terms of the GNU General Public License (GPL)
108#
109#    This code is distributed in the hope that it will be useful,
110#    but WITHOUT ANY WARRANTY; without even the implied warranty of
111#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
112#    General Public License for more details.
113#
114#  The full text of the GPL is available at:
115#
116#                  http://www.gnu.org/licenses/
117#*****************************************************************************
118
119from sage.rings.ideal import Ideal_generic
120from sage.interfaces.all import singular as singular_default, is_SingularElement
121from sage.interfaces.all import macaulay2 as macaulay2_default
122from sage.interfaces.all import is_SingularElement
123singular = singular_default
124from sage.rings.integer import Integer
125from sage.structure.sequence import Sequence
126from sage.misc.sage_eval import sage_eval
127from sage.misc.misc import prod
128import sage.rings.integer_ring
129import sage.rings.polynomial.toy_buchberger as toy_buchberger
130
131def is_MPolynomialIdeal(x):
132    return isinstance(x, MPolynomialIdeal)
133
134class MPolynomialIdeal_magma_repr:
135    def _magma_(self, magma=None):
136        """
137        Returns a MAGMA ideal matching self if the base ring coercable to MAGMA
138        and MAGMA is available.
139
140        EXAMPLES:
141            sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10)
142            sage: I = sage.rings.ideal.Cyclic(R,4)
143            sage: I._magma_() #optional MAGMA
144            Ideal of Polynomial ring of rank 10 over GF(127)
145            Graded Reverse Lexicographical Order
146            Variables: a, b, c, d, e, f, g, h, i, j
147            Basis:
148            [
149            a + b + c + d,
150            a*b + b*c + a*d + c*d,
151            a*b*c + a*b*d + a*c*d + b*c*d,
152            a*b*c*d + 126
153            ]
154        """
155        if magma == None:
156            import sage.interfaces.magma
157            magma = sage.interfaces.magma.magma
158        return magma.ideal(self.gens())
159
160    def _magma_groebner_basis(self):
161        """
162        Computes a Groebner Basis for self using MAGMA if available.
163
164        EXAMPLES:
165            sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10)
166            sage: I = sage.rings.ideal.Cyclic(R,6)
167            sage: gb = I.groebner_basis("magma:GroebnerBasis") #optional MAGMA
168            sage: len(gb) #optional MAGMA
169            45
170        """
171        try:
172            return self.__magma_groebner_basis
173        except AttributeError:
174            pass
175        R = self.ring()
176        mgb = self._magma_().GroebnerBasis()
177        mgb = [str(mgb[i+1]) for i in range(len(mgb))]
178        if R.base_ring().degree() > 1:
179            a = str(R.base_ring().gen())
180            mgb = [e.replace("$.1",a) for e in mgb]
181        B = Sequence([R(e) for e in mgb], R, check=False, immutable=True)
182        self.__magma_groebner_basis = B
183        return B
184         
185       
186class MPolynomialIdeal_singular_repr:
187    """
188    An ideal in a multivariate polynomial ring, which has an
189    underlying Singular ring associated to it.
190    """
191    def __cmp__(self, other):
192        # Groebner basis determine equality since ideals are in the
193        # same ring with same term order
194       
195        #c = cmp(self.gens(), other.gens())
196        #if c == 0:
197        #    return c
198        l = MPolynomialIdeal(self.ring(), self.groebner_basis()).reduced_basis()
199        r = MPolynomialIdeal(self.ring(),other.groebner_basis()).reduced_basis()
200        return cmp(r,l)
201
202    def _singular_(self, singular=None):
203        """
204        Return Singular ideal corresponding to this ideal.
205
206        EXAMPLES:
207            sage: R, (x,y) = PolynomialRing(QQ, 2, 'xy').objgens()
208            sage: I = R.ideal([x^3 + y, y])
209            sage: S = I._singular_()
210            sage: S
211            x^3+y,
212            y
213        """
214        if singular is None: singular = singular_default
215        try:
216            self.ring()._singular_(singular).set_ring()           
217            I = self.__singular
218            if not (I.parent() is singular):
219                raise ValueError
220            I._check_valid()
221            return I
222        except (AttributeError, ValueError):
223            self.ring()._singular_(singular).set_ring()
224            gens = [str(x) for x in self.gens()]
225            if len(gens) == 0:
226                gens = ['0']
227            self.__singular = singular.ideal(gens)
228        return self.__singular
229
230    def _contains_(self, f):
231        """
232        Returns True if f is in the ideal self.
233       
234        EXAMPLES:
235            sage: R, (x,y) = PolynomialRing(QQ, 2, 'xy').objgens()
236            sage: I = (x^3 + y, y)*R
237            sage: x in I
238            False
239            sage: y in I
240            True
241            sage: x^3 + 2*y in I
242            True
243
244        NOTE: Requires computation of a Groebner basis, which is a
245        very expensive operation.
246        """
247
248        if self.base_ring() == sage.rings.integer_ring.ZZ:
249            g = self._reduce_using_macaulay2(f)
250        else:
251            S = singular_default
252            f = S(f)
253            I = self._singular_(S).groebner()
254            g = f.reduce(I, 1)  # 1 avoids tail reduction (page 67 of singular book)
255        return g.is_zero()
256       
257    def plot(self):
258        """
259        If you somehow manage to install surf, perhaps you can use
260        this function to implicitly plot the real zero locus of this
261        ideal (if principal).
262
263        INPUT:
264            self -- must be a principal ideal in 2 or 3 vars over QQ.
265
266        EXAMPLES:
267        Implicit plotting in 2-d:
268            sage: R.<x,y> = PolynomialRing(QQ,2)
269            sage: I = R.ideal([y^3 - x^2])
270            sage: I.plot()        # cusp         (optional surf)
271            sage: I = R.ideal([y^2 - x^2 - 1])
272            sage: I.plot()        # hyperbola    (optional surf)
273            sage: I = R.ideal([y^2 + x^2*(1/4) - 1])
274            sage: I.plot()        # ellipse      (optional surf)
275            sage: I = R.ideal([y^2-(x^2-1)*(x-2)])
276            sage: I.plot()        # elliptic curve  (optional surf)
277
278        Implicit plotting in 3-d:
279            sage: R.<x,y,z> = PolynomialRing(QQ,3)
280            sage: I = R.ideal([y^2 + x^2*(1/4) - z])
281            sage: I.plot()          # a cone         (optional surf)
282            sage: I = R.ideal([y^2 + z^2*(1/4) - x])
283            sage: I.plot()          # same code, from a different angle  (optional surf)
284            sage: I = R.ideal([x^2*y^2+x^2*z^2+y^2*z^2-16*x*y*z])
285            sage: I.plot()          # Steiner surface   (optional surf)
286
287        AUTHOR:
288            -- David Joyner (2006-02-12)
289        """
290        if self.ring().characteristic() != 0:
291            raise TypeError, "base ring must have characteristic 0"
292        if not self.is_principal():
293            raise TypeError, "self must be principal"
294        singular.lib('surf')
295        I = singular(self)
296        I.plot()
297
298    def complete_primary_decomposition(self, algorithm="sy"):
299        r"""
300        INPUT:
301            algorithm -- string:
302                    'sy' -- (default) use the shimoyama-yokoyama algorithm
303                    'gtz' -- use the gianni-trager-zacharias algorithm
304        OUTPUT:
305            list -- a list of primary ideals and their associated
306                    primes
307                        [(primary ideal, associated prime), ...]
308
309        ALGORITHM: Uses Singular.
310
311        EXAMPLES:
312            sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
313            sage: p = z^2 + 1; q = z^3 + 2
314            sage: I = (p*q^2, y-z^2)*R
315            sage: pd = I.complete_primary_decomposition(); pd
316            [(Ideal (z^6 + 4*z^3 + 4, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^3 + 2, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field), (Ideal (z^2 + 1, y + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^2 + 1, y + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field)]
317
318            sage: I.complete_primary_decomposition(algorithm = 'gtz')
319            [(Ideal (z^6 + 4*z^3 + 4, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^3 + 2, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field), (Ideal (z^2 + 1, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^2 + 1, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field)]
320        """
321        try:
322            return self.__complete_primary_decomposition[algorithm]
323        except AttributeError: 
324            self.__complete_primary_decomposition = {}
325        except KeyError:
326            pass
327        I = self._singular_()
328        I.parent().lib('primdec.lib')
329        if algorithm == 'sy':
330            P = I.primdecSY()
331        elif algorithm == 'gtz':
332            P = I.primdecGTZ()
333
334        R = self.ring()
335        V = [(R.ideal(X[1]), R.ideal(X[2])) for X in P]
336        V = Sequence(V)
337        self.__complete_primary_decomposition[algorithm] = V
338        return self.__complete_primary_decomposition[algorithm]
339
340    def primary_decomposition(self, algorithm='sy'):
341        """
342        EXAMPLES:
343            sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
344            sage: p = z^2 + 1; q = z^3 + 2
345            sage: I = (p*q^2, y-z^2)*R
346            sage: I.primary_decomposition()   
347            [Ideal (z^6 + 4*z^3 + 4, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^2 + 1, y + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field]
348
349        """
350        return [I for I, _ in self.complete_primary_decomposition(algorithm)]
351
352    def triangular_decomposition(self, algorithm=None):
353        """
354        Decompose zero-dimensional ideal self into triangular sets.
355
356        This requires that the given basis is reduced w.r.t. to the lexicographical
357        monomial ordering. If the basis of self does not have this property, the
358        required Groebner basis is computed implicitly.
359
360        INPUT:
361            algorithm -- string or None (default: None)
362
363        ALGORITHMS:
364            singular:triangL -- decomposition of self into triangular systems (Lazard).
365            singular:triangLfak -- decomp. of self into tri. systems plus factorization.
366            singular:triangM -- decomposition of self into triangular systems (Moeller).
367
368        OUTPUT:
369            a list T of lists t such that the variety of self is the union of the varieties
370            of t in L and each t is in triangular form.
371
372        EXAMPLE:
373            sage: P.<e,d,c,b,a> = PolynomialRing(QQ,5,order='lex')
374            sage: I = sage.rings.ideal.Cyclic(P)
375            sage: GB = Ideal(I.groebner_basis('singular:stdfglm'))
376            sage: GB.triangular_decomposition('singular:triangLfak')
377            [Ideal (a - 1, b - 1, c - 1, d^2 + 3*d + 1, e + d + 3) of
378            Multivariate Polynomial Ring in e, d, c, b, a over
379            Rational Field,
380            Ideal (a - 1, b - 1, c^2 + 3*c + 1, d + c + 3, e - 1) of
381            Multivariate Polynomial Ring in e, d, c, b, a over
382            Rational Field,
383            Ideal (a - 1, b^4 + b^3 + b^2 + b + 1, c - b^2, d - b^3, e
384            + b^3 + b^2 + b + 1) of Multivariate Polynomial Ring in e,
385            d, c, b, a over Rational Field,
386            Ideal (a - 1, b^2 + 3*b + 1, c + b + 3, d - 1, e - 1) of
387            Multivariate Polynomial Ring in e, d, c, b, a over
388            Rational Field,
389            Ideal (a^4 + a^3 + a^2 + a + 1, b - 1, c + a^3 + a^2 + a +
390            1, d - a^3, e - a^2) of Multivariate Polynomial Ring in e,
391            d, c, b, a over Rational Field, Ideal (a^4 + a^3 + a^2 + a
392            + 1, b - a, c - a, d^2 + 3*d*a + a^2, e + d + 3*a) of
393            Multivariate Polynomial Ring in e, d, c, b, a over
394            Rational Field,
395            Ideal (a^4 + a^3 + a^2 + a + 1, b - a, c^2 + 3*c*a + a^2,
396            d + c + 3*a, e - a) of Multivariate Polynomial Ring in e,
397            d, c, b, a over Rational Field,
398            Ideal (a^4 + a^3 + a^2 + a + 1, b^3 + b^2*a + b^2 + b*a^2
399            + b*a + b + a^3 + a^2 + a + 1, c + b^2*a^3 + b^2*a^2 +
400            b^2*a + b^2, d - b^2*a^2 - b^2*a - b^2 - b*a^2 - b*a -
401            a^2, e - b^2*a^3 + b*a^2 + b*a + b + a^2 + a) of
402            Multivariate Polynomial Ring in e, d, c, b, a over
403            Rational Field,
404            Ideal (a^4 + a^3 + a^2 + a + 1, b^2 + 3*b*a + a^2, c + b +
405            3*a, d - a, e - a) of Multivariate Polynomial Ring in e,
406            d, c, b, a over Rational Field,
407            Ideal (a^4 + a^3 + 6*a^2 - 4*a + 1, 11*b^2 - 6*b*a^3 -
408            10*b*a^2 - 39*b*a - 2*b - 16*a^3 - 23*a^2 - 104*a + 24,
409            11*c + 3*a^3 + 5*a^2 + 25*a + 1, 11*d + 3*a^3 + 5*a^2 +
410            25*a + 1, 11*e + 11*b - 6*a^3 - 10*a^2 - 39*a - 2) of
411            Multivariate Polynomial Ring in e, d, c, b, a over
412            Rational Field,
413            Ideal (a^4 - 4*a^3 + 6*a^2 + a + 1, 11*b^2 - 6*b*a^3 +
414            26*b*a^2 - 41*b*a + 4*b + 8*a^3 - 31*a^2 + 40*a + 24, 11*c
415            + 3*a^3 - 13*a^2 + 26*a - 2, 11*d + 3*a^3 - 13*a^2 + 26*a
416            - 2, 11*e + 11*b - 6*a^3 + 26*a^2 - 41*a + 4) of
417            Multivariate Polynomial Ring in e, d, c, b, a over
418            Rational Field,
419            Ideal (a^2 + 3*a + 1, b - 1, c - 1, d - 1, e + a + 3) of
420            Multivariate Polynomial Ring in e, d, c, b, a over
421            Rational Field, Ideal (a^2 + 3*a + 1, b + a + 3, c - 1, d
422            - 1, e - 1) of Multivariate Polynomial Ring in e, d, c, b,
423            a over Rational Field]
424            """
425
426        P = self.ring()
427
428        is_groebner = self.basis_is_groebner()
429
430        # make sure to work w.r.t. 'lex'
431        if P.term_order() != 'lex':
432            Q = P.new_ring(order='lex')
433        else:
434            Q = P
435
436        if is_groebner:
437            if Q == P:
438                I = MPolynomialIdeal(P, self.reduced_basis()) # reduce only
439            else:
440                I = MPolynomialIdeal(P, self.reduced_basis())
441                I = MPolynomialIdeal(P, I.transformed_basis('fglm')) # -> 'lex'
442                I = I.change_ring(Q) # transform to 'lex' GB
443        else:
444            if Q == P:
445                I = MPolynomialIdeal(P, self.groebner_basis())
446                I = MPolynomialIdeal(P, I.reduced_basis())
447            else:
448                I = self.change_ring(Q) # transform to 'lex' GB
449                I = MPolynomialIdeal(Q, I.groebner_basis())
450                I = MPolynomialIdeal(Q, I.reduced_basis())
451
452        if I.dimension() != 0:
453            raise TypeError, "dimension must be zero"
454
455        Ibar = I._singular_()
456        Ibar.attrib('isSB',1)
457
458        singular = Ibar.parent()
459        singular.lib("triang")
460
461        if algorithm is None:
462            algorithm = "singular:triangL"
463       
464        if algorithm == "singular:triangL":
465            Tbar = Ibar.triangL()
466        elif algorithm == "singular:triangLfak":
467            Tbar = Ibar.triangLfak()
468        elif algorithm == "singular:triangM":
469            Tbar = Ibar.triangM()
470        else:
471            raise TypeError, "algorithm '%s' unknown"%algorithm
472
473        T = Sequence([ MPolynomialIdeal(Q,[f._sage_(Q) for f in t]) for t in Tbar ])
474
475        return T
476   
477    def associated_primes(self, algorithm='sy'):
478        """
479        EXAMPLES:
480            sage: R.<x,y,z> = PolynomialRing(QQ, 3)
481            sage: p = z^2 + 1; q = z^3 + 2
482            sage: I = (p*q^2, y-z^2)*R
483            sage: I.associated_primes()
484            [Ideal (z^2 - y, y*z + 2, y^2 + 2*z) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (y + 1, z^2 + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field]
485        """
486        return [P for _,P in self.complete_primary_decomposition(algorithm)]
487           
488    def dimension(self):
489        """
490        The dimension of the ring modulo this ideal.
491
492        NOTE: Requires computation of a Groebner basis, which is a
493        very expensive operation.
494        """
495        try:
496            return self.__dimension
497        except AttributeError:
498            v = list(self.groebner_basis())
499            if len(v) == 0:
500                v = [0]
501            self.__dimension = Integer(singular(v,"ideal").dim())
502        return self.__dimension
503
504    def vector_space_dimension(self):
505        """
506        Return the vector space dimension of the ring modulo the ideal
507        generated by the initial terms of the generators of self.
508
509        If the generators form a standard basis, this is the same as
510        the vector space dimension of the ring modulo the ideal.  If
511        the ideal is not zero-dimensional, a TypeError is raised.
512
513        ALGORITHM: Uses Singular.
514
515        EXAMPLE:
516            sage: P.<x,y> = PolynomialRing(QQ,2,order='neglex')
517            sage: I = P * [x^2 + y^2, x^2 - y^2]
518            sage: I.vector_space_dimension()
519            Traceback (most recent call last):
520            ...
521            TypeError: ideal is not zero dimensional
522            sage: J = Ideal(I.groebner_basis())
523            sage: J.vector_space_dimension()
524            4
525        """
526
527        vdim = Integer(self._singular_().vdim())
528        if vdim == -1:
529            raise TypeError, "ideal is not zero dimensional"
530        else:
531            return vdim
532       
533    def _groebner_basis_using_singular(self, algorithm="groebner"):
534        """
535        Return a Groebner basis of this ideal. If a groebner basis for
536        this ideal has been calculated before the cached Groebner
537        basis is returned regardless of the requested algorithm.
538
539        ALGORITHM: Uses Singular.
540
541        INPUT:
542            algorithm -- 'groebner' - use Singular's groebner heuristic to choose
543                                      an algorithm (default)
544                         'std'      - Buchberger's algorithm
545                         'stdhilb'  - computes the standard basis of the homogeneous
546                                      ideal in the basering, via a Hilbert driven
547                                      standard basis computation.
548                         'stdfglm'  - computes the standard basis of the ideal in the basering via fglm
549                                      (from the degrevlex ordering to the ordering of the basering).
550                         'slimgb'   - SlimGB algorithm
551
552        EXAMPLES:
553
554        We compute a Groebner basis of 'cyclic 4' relative to
555        lexicographic ordering.
556       
557            sage: R.<a,b,c,d> = PolynomialRing(QQ, 4, order='lex')
558            sage: I = sage.rings.ideal.Cyclic(R,4); I
559            Ideal (a + b + c + d, a*b + a*d + b*c + c*d, a*b*c + a*b*d + a*c*d + b*c*d, a*b*c*d - 1) of Multivariate Polynomial Ring in a, b, c, d over Rational Field
560            sage: I._groebner_basis_using_singular()
561            [c^2*d^6 - c^2*d^2 - d^4 + 1, c^3*d^2 + c^2*d^3 - c - d, b*d^4 - b + d^5 - d, b*c - b*d^5 + c^2*d^4 + c*d - d^6 - d^2, b^2 + 2*b*d + d^2, a + b + c + d]
562        """
563        try:
564            return self.__groebner_basis
565        except AttributeError:
566            if algorithm=="groebner":
567                S = self._singular_().groebner()
568            elif algorithm=="std":
569                S = self._singular_().std()
570            elif algorithm=="slimgb":
571                S = self._singular_().slimgb()
572            elif algorithm=="stdhilb":
573                S = self._singular_().stdhilb()
574            elif algorithm=="stdfglm":
575                S = self._singular_().stdfglm()
576            else:
577                raise TypeError, "algorithm '%s' unknown"%algorithm
578            R = self.ring()
579            self.__singular_groebner_basis = S #remember this
580            self.__groebner_basis = Sequence([R(S[i+1]) for i in range(len(S))], R,
581                                             check=False, immutable=True)
582        return self.__groebner_basis
583
584    def _groebner_basis_using_libsingular(self, algorithm="std"):
585        """
586        Return a Groebner basis of this ideal. If a groebner basis for
587        this ideal has been calculated before the cached Groebner
588        basis is returned regardless of the requested algorithm.
589
590        ALGORITHM: Uses libSINGULAR.
591
592        INPUT:
593            algorithm -- 'std'      - Buchberger's algorithm
594                         'slimgb'   - SlimGB algorithm
595
596        EXAMPLES:
597
598        We compute a Groebner basis of 'cyclic 4' relative to
599        lexicographic ordering.
600       
601            sage: R.<a,b,c,d> = PolynomialRing(QQ, 4, order='lex')
602            sage: I = sage.rings.ideal.Cyclic(R,4); I
603            Ideal (a + b + c + d, a*b + a*d + b*c + c*d, a*b*c + a*b*d + a*c*d + b*c*d, a*b*c*d - 1) of Multivariate Polynomial Ring in a, b, c, d over Rational Field
604            sage: I._groebner_basis_using_libsingular()
605            [c^2*d^6 - c^2*d^2 - d^4 + 1, c^3*d^2 + c^2*d^3 - c - d, b*d^4 - b + d^5 - d, b*c - b*d^5 + c^2*d^4 + c*d - d^6 - d^2, b^2 + 2*b*d + d^2, a + b + c + d]
606        """
607        from sage.rings.polynomial.multi_polynomial_ideal_libsingular import std_libsingular, slimgb_libsingular
608
609        try:
610            return self.__groebner_basis
611        except AttributeError:
612            if algorithm=="std":
613                S = std_libsingular(self)
614            elif algorithm=="slimgb":
615                S = slimgb_libsingular(self)
616            else:
617                raise TypeError, "algorithm '%s' unknown"%algorithm
618            self.__groebner_basis = S
619        return self.__groebner_basis
620
621    def _singular_groebner_basis(self):
622        try:
623            S = self.__singular_groebner_basis
624        except AttributeError:
625            G = self.groebner_basis()
626            try:
627                return self.__singular_groebner_basis
628            except AttributeError:
629                pass
630
631        try:
632            S._check_valid()
633            return S
634        except ValueError:
635            G = self.groebner_basis()
636            S = singular(G)
637            self.__singular_groebner_basis = S
638        return S
639           
640   
641
642    def genus(self):
643        """
644        Return the genus of the projective curve defined by this
645        ideal, which must be 1 dimensional.
646        """
647        try:
648            return self.__genus
649        except AttributeError:
650            I = self._singular_()
651            I.parent().lib('normal.lib')
652            self.__genus = Integer(I.genus())
653            return self.__genus
654
655    def intersection(self, other):
656        """
657        Return the intersection of the two ideals.
658
659        EXAMPLES:
660            sage: R.<x,y> = PolynomialRing(QQ, 2, order='lex')
661            sage: I = x*R
662            sage: J = y*R
663            sage: I.intersection(J)
664            Ideal (x*y) of Multivariate Polynomial Ring in x, y over Rational Field
665
666        The following simple example illustrates that the product need not equal the intersection.
667            sage: I = (x^2, y)*R
668            sage: J = (y^2, x)*R
669            sage: K = I.intersection(J); K
670            Ideal (y^2, x*y, x^2) of Multivariate Polynomial Ring in x, y over Rational Field
671            sage: IJ = I*J; IJ
672            Ideal (x^2*y^2, x^3, y^3, x*y) of Multivariate Polynomial Ring in x, y over Rational Field
673            sage: IJ == K
674            False
675        """
676        R = self.ring()
677        if not isinstance(other, MPolynomialIdeal_singular_repr) or other.ring() != R:
678            raise ValueError, "other must be an ideal in the ring of self, but it isn't."
679        I = self._singular_()
680        sing = I.parent()
681        J = sing(other)
682        K = I.intersect(J)
683        return R.ideal(K)
684
685
686    def minimal_associated_primes(self):
687        r"""
688        OUTPUT:
689            list -- a list of prime ideals
690
691        EXAMPLES:
692            sage: R.<x,y,z> = PolynomialRing(QQ, 3, 'xyz')
693            sage: p = z^2 + 1; q = z^3 + 2
694            sage: I = (p*q^2, y-z^2)*R
695            sage: I.minimal_associated_primes ()
696            [Ideal (z^2 + 1, -z^2 + y) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^3 + 2, -z^2 + y) of Multivariate Polynomial Ring in x, y, z over Rational Field]
697       
698        ALGORITHM: Uses Singular.
699        """
700        I = self._singular_()
701        I.parent().lib('primdec.lib')
702        M = I.minAssGTZ()
703        R = self.ring()
704        return [R.ideal(J) for J in M]
705
706    def radical(self):
707        r"""
708        The radical of this ideal.
709
710        EXAMPLES:
711        This is an obviously not radical ideal:
712            sage: R.<x,y,z> = PolynomialRing(QQ, 3)
713            sage: I = (x^2, y^3, (x*z)^4 + y^3 + 10*x^2)*R
714            sage: I.radical()
715            Ideal (y, x) of Multivariate Polynomial Ring in x, y, z over Rational Field
716           
717        That the radical is correct is clear from the Groebner basis.
718            sage: I.groebner_basis()
719            [x^2, y^3]
720
721        This is the example from the singular manual:
722            sage: p = z^2 + 1; q = z^3 + 2
723            sage: I = (p*q^2, y-z^2)*R
724            sage: I.radical()
725            Ideal (z^2 - y, y^2*z + y*z + 2*y + 2) of Multivariate Polynomial Ring in x, y, z over Rational Field
726
727        \note{(From Singular manual) A combination of the algorithms
728        of Krick/Logar and Kemper is used.  Works also in positive
729        characteristic (Kempers algorithm).}
730
731            sage: R.<x,y,z> = PolynomialRing(GF(37), 3)
732            sage: p = z^2 + 1; q = z^3 + 2
733            sage: I = (p*q^2, y - z^2)*R
734            sage: I.radical()
735            Ideal (z^2 - y, y^2*z + y*z + 2*y + 2) of Multivariate Polynomial Ring in x, y, z over Finite Field of size 37
736        """
737        S = self.ring()
738        I = self._singular_()
739        I.parent().lib('primdec.lib')
740        r = I.radical()
741        return S.ideal(r)
742
743    def integral_closure(self, p=0, r=True):
744        r"""
745        Let I == self.
746       
747        Returns the integral closure of $I, \ldots, I^p$, where $sI$
748        is an ideal in the polynomial ring $R=k[x(1),...x(n)]$. If $p$ is
749        not given, or $p=0$, compute the closure of all powers up to
750        the maximum degree in t occurring in the closure of $R[It]$ (so
751        this is the last power whose closure is not just the
752        sum/product of the smaller). If $r$ is given and \code{r is True},
753        \code{I.integral_closure()} starts with a check whether I is already a
754        radical ideal.
755
756        INPUT:
757            p -- powers of I (default: 0)
758            r -- check whether self is a radical ideal first (default: True)
759
760        EXAMPLE:
761            sage: R.<x,y> = QQ[]
762            sage: I = ideal([x^2,x*y^4,y^5])
763            sage: I.integral_closure()
764            [x^2, y^5, -x*y^3]
765
766        ALGORITHM: Use Singular
767           
768        """
769        Is = self._singular_()
770        R = self.ring()
771        singular =Is .parent()
772        singular.load('reesclos.lib')
773        ret = Sequence([ R(f) for f in Is.normalI(p,int(r))[1] ], R,
774                       check=False, immutable=True)
775        return ret
776
777    def reduce(self, f):
778        """
779        Reduce an element modulo a standard basis for this ideal.
780        This returns 0 if and only if the element is in this ideal.
781       
782        EXAMPLES:
783            sage: R.<x,y> = PolynomialRing(QQ, 2)
784            sage: I = (x^3 + y, y)*R
785            sage: I.reduce(y)
786            0
787            sage: I.reduce(x^3)
788            0
789            sage: I.reduce(x - y)
790            x
791
792            sage: I = (y^2 - (x^3 + x))*R
793            sage: I.reduce(x^3)
794            y^2 - x
795            sage: I.reduce(x^6)
796            y^4 - 2*x*y^2 + x^2
797            sage: (y^2 - x)^2
798            y^4 - 2*x*y^2 + x^2
799
800        NOTE: Requires computation of a Groebner basis, which is a
801        very expensive operation.
802        """
803        if self.base_ring() == sage.rings.integer_ring.ZZ:
804            return self._reduce_using_macaulay2(f)
805
806        try:
807            singular = self._singular_groebner_basis().parent()
808        except (AttributeError, RuntimeError):
809            singular = self._singular_groebner_basis().parent()
810       
811        f = self.ring()(f)
812        g = singular(f)
813        try:
814            self.ring()._singular_(singular).set_ring()           
815            h = g.reduce(self._singular_groebner_basis())
816        except TypeError:
817            # This is OK, since f is in the right ring -- type error
818            # just means it's a rational
819            return f
820        try:
821            return self.ring()(h)
822        except (TypeError, RuntimeError):
823            return self.ring()(h[1])
824            # Why the above?
825            # For mysterious reasons, sometimes Singular returns a length
826            # one vector with the reduced polynomial in it.
827            # This occurs in the following example:
828            #sage: R.<x,y> = PolynomialRing(QQ, 2)
829            #sage: S.<a,b> = R.quotient(x^2 + y^2)
830            #sage: phi = S.hom([b,a])
831            #sage: loads(dumps(phi))
832
833
834    def syzygy_module(self):
835        r"""
836        Computes the first syzygy (i.e., the module of relations of
837        the given generators) of the ideal.
838
839        ALGORITHM: Uses Singular's syz command
840
841        \note{The syz module is transposed before being returned}
842        """
843        return self._singular_().syz().transpose().sage_matrix(self.ring())
844
845    def reduced_basis(self):
846        r"""
847        returns $(g_1, \dots, g_s)$ such that:
848
849        * $(f_1,\dots,f_n) = (g_1,\dots,g_s)$
850        * $LT(g_i)\neq LT(g_j)$ for all $i\neq j$
851        * $LT(g_i)$ does not divide m for all monomials m of
852          $\{g_1,\dots,g_{i-1},g_{i+1},\dots,g_s\}$
853        * $LC(g_i) == 1$ for all $i$.
854
855        ALGORITHM: Uses Singular's interred command
856
857        \note{G. Pfister recommended setting option(redSB) before
858        using interred for this purpose. Though the manual doesn't
859        mention it.}
860        """
861        from sage.rings.polynomial.multi_polynomial_ideal_libsingular import interred_libsingular
862        from sage.rings.polynomial.multi_polynomial_libsingular import MPolynomialRing_libsingular
863
864        R = self.ring()
865
866        if isinstance(R,MPolynomialRing_libsingular):
867            return interred_libsingular(self)
868        else:
869            s = self._singular_().parent()
870            o = s.option("get")
871            s.option("redSB")
872            s.option("redTail")
873            ret = []
874            for f in self._singular_().interred():
875                f = R(f)
876                ret.append(f/f.lc()) # lead coeffs are not reduced by interred
877            ret = Sequence( ret, R, check=False, immutable=True)
878            s.option("set",o)
879
880        return ret
881
882    def basis_is_groebner(self):
883        """
884        Returns true if self.gens() form a Groebner Basis. This is done by
885        trying to lift Syz(LM(self)) to Syz(self) as self is a Groebner
886        Basis if and only if for every element S in Syz(LM(self)):
887        $$S \cdot G = \sum_{i=0}^{m} h_ig_i \rightarrow_G 0.$$.
888
889        ALGORITHM: Uses Singular
890
891        EXAMPLE:
892            sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10)
893            sage: I = sage.rings.ideal.Cyclic(R,4)
894            sage: I.basis_is_groebner()
895            False
896            sage: I2 = Ideal(I.groebner_basis())
897            sage: I2.basis_is_groebner()
898            True
899
900        \note{From the Singular Manualf for the reduce function we use in
901        this method: 'The result may have no meaning if the second
902        argument (self, malb) is not a standard basis'. I (malb) believe
903        this refers to the mathematical fact that the results may have no
904        meaning if self is no standard basis, i.e., Singular doesn't 'add'
905        any additional 'nonsense' to the result. So we may acutally use
906        reduce to determine if self is a Groebner Basis.}
907        """
908        from sage.matrix.constructor import matrix
909        singular = self._singular_().parent()
910        R = self.ring()
911
912        F = singular( self.gens(), "module" )
913        LTF = singular( [f.lt() for f in self.gens()] , "module" )
914
915        M = (F * LTF.syz()).reduce(self._singular_())
916
917        for i in range(M.nrows()):
918            if int(singular.eval("%s[1][%s+1]!=0"%(M.name(),i))):
919                return False
920
921        self._singular_().attrib('isSB',1)
922        return True
923
924    def transformed_basis(self,algorithm="gwalk", other_ring=None):
925        """
926        Returns a lex or other_ring Groebner Basis for a given ideal
927        self which must be represented through a Groebner Basis.
928       
929        INPUT:
930           algorithm -- Options are:
931                        * fglm - FGLM algorithm. The input ideal must be
932                                 a reduced Groebner Basis of a zero-dimensional ideal
933                        * gwalk (default) - Groebner Walk algorithm
934                        * awalk1 - 'first alternative' algorithm
935                        * awalk2 - 'second alternative' algorithm
936                        * twalk  - Tran algorithm
937                        * fwalk  - Fractal Walk algorithm
938           other_ring  -- only valid for algorithm 'fglm', if provided conversion will
939                          be performed to this ring. Otherwise a lex Groebner basis will
940                          be returned.
941        EXAMPLES:
942           sage: # example from the Singular manual page of fglm
943           sage: R.<x,y,z> = PolynomialRing(QQ,3)
944           sage: I = Ideal([y^3+x^2,x^2*y+x^2, x^3-x^2, z^4-x^2-y])
945           sage: singular.option('redSB')
946           sage: I = Ideal(I.groebner_basis())
947           sage: singular.option('noredSB') #reset
948           sage: S.<z,x,y> = PolynomialRing(QQ,3,order='lex')
949           sage: J = Ideal(I.transformed_basis('fglm',S))
950           sage: J
951           Ideal (y^4 + y^3, x*y^3 - y^3, x^2 + y^3, z^4 + y^3 - y) of Multivariate Polynomial Ring in z, x, y over Rational Field
952           sage: # example from the Singular manual page of gwalk
953           sage: R.<z,y,x>=PolynomialRing(GF(32003),3,order='lex')
954           sage: I=Ideal([y^3+x*y*z+y^2*z+x*z^3,3+x*y+x^2*y+y^2*z])
955           sage: I.transformed_basis('gwalk')
956           [y^9 - y^7*x^2 - y^7*x - y^6*x^3 - y^6*x^2 - 3*y^6 - 3*y^5*x - y^3*x^7 - 3*y^3*x^6 - 3*y^3*x^5 - y^3*x^4 - 9*y^2*x^5 - 18*y^2*x^4 - 9*y^2*x^3 - 27*y*x^3 - 27*y*x^2 - 27*x,
957           z*x + 8297*y^8*x^2 + 8297*y^8*x + 3556*y^7 - 8297*y^6*x^4 + 15409*y^6*x^3 - 8297*y^6*x^2 - 8297*y^5*x^5 + 15409*y^5*x^4 - 8297*y^5*x^3 + 3556*y^5*x^2 + 3556*y^5*x + 3556*y^4*x^3 + 3556*y^4*x^2 - 10668*y^4 - 10668*y^3*x - 8297*y^2*x^9 - 1185*y^2*x^8 + 14224*y^2*x^7 - 1185*y^2*x^6 - 8297*y^2*x^5 - 14223*y*x^7 - 10666*y*x^6 - 10666*y*x^5 - 14223*y*x^4 + x^5 + 2*x^4 + x^3,
958           z*y^2 + y*x^2 + y*x + 3]
959
960
961        ALGORITHM: Uses Singular
962        """
963        from sage.rings.polynomial.multi_polynomial_ring import TermOrder,MPolynomialRing
964        from sage.rings.quotient_ring import is_QuotientRing       
965       
966        Is = self._singular_()
967        R = self.ring()
968
969        if algorithm in ("gwalk","awalk1","awalk2","twalk","fwalk"):
970            singular.LIB("grwalk")
971            gb = singular("%s(%s)"%(algorithm,Is.name()))
972            return [R(f) for f in gb]
973        elif algorithm == "fglm":
974            Rs = self.ring()._singular_()
975
976            # new ring
977            if other_ring==None:
978                nR = MPolynomialRing(R.base_ring(),R.ngens(), names=R.variable_names(), order="lex")
979            else:
980                nR = other_ring
981            nR._singular_().set_ring()
982           
983            nIs = singular.fglm(Rs,Is)
984
985            return [nR(f) for f in nIs]
986
987        else:
988            raise TypeError, "Cannot convert basis with given algorithm"
989
990    def elimination_ideal(self, variables):
991        """
992        Returns the elimination ideal of self with respect to the
993        variables given in 'variables'.
994
995        INPUT:
996            variables -- a list or tuple of variables in self.ring()
997
998        EXAMPLE:
999            sage: R.<x,y,t,s,z> = PolynomialRing(QQ,5)
1000            sage: I = R * [x-t,y-t^2,z-t^3,s-x+y^3]
1001            sage: I.elimination_ideal([t,s])
1002            Ideal (y^2 - x*z, x*y - z, x^2 - y) of Multivariate Polynomial Ring in x, y, t, s, z over Rational Field
1003
1004        ALGORITHM: Uses SINGULAR
1005
1006        NOTE: Requires computation of a Groebner basis, which is a
1007        very expensive operation.
1008        """
1009        if not isinstance(variables, (list,tuple)):
1010            variables = (variables,)
1011       
1012        try:
1013            Is = self.__singular_groebner_basis
1014        except AttributeError:
1015            Is = self._singular_()
1016
1017        R = self.ring()
1018        return MPolynomialIdeal(R, [f.sage_poly(R) for f in Is.eliminate( prod(variables) ) ] )
1019
1020    def quotient(self, J):
1021        r"""
1022        Given ideals I (==self) and J of the same polynomial ring P,
1023        return the ideal quotient of I by J consisting of the
1024        polynomials a of P such that $\{aJ \subset I\}$.
1025
1026        This is also referred to as the colon ideal (I:J).
1027
1028        INPUT:
1029            J -- multivariate polynomial ideal
1030
1031        EXAMPLE:
1032            sage: R.<x,y,z> = PolynomialRing(GF(181),3)
1033            sage: I = Ideal([x^2+x*y*z,y^2-z^3*y,z^3+y^5*x*z])
1034            sage: J = Ideal([x])
1035            sage: Q = I.quotient(J)
1036            sage: y*z + x in I
1037            False
1038            sage: x in J
1039            True
1040            sage: x * (y*z + x) in I
1041            True
1042        """
1043        R = self.ring()
1044
1045        if not isinstance(J, MPolynomialIdeal):
1046            raise TypeError, "J needs to be a multivariate polynomial ideal"
1047
1048        if not R is J.ring() and not R == J.ring():
1049            raise TypeError, "base rings do not match"
1050
1051        return R.ideal([f.sage_poly(R) for f in self._singular_().quotient(J._singular_())])
1052
1053    def variety(self):
1054        """
1055        Return the variety of self.
1056
1057        Given a zero-dimensional ideal I (== self) of a polynomial ring P
1058        whose order is lexicographic, return the variety of I over its
1059        coefficient field K as a list of dictionaries with (variable, value)
1060        pairs.
1061
1062        These dictionaries have cardinality equal to the number of
1063        variables in P and represent assignments of values to these
1064        variables such that all polynomials in I vanish.
1065
1066        EXAMPLE:
1067            sage: K.<w> = GF(27) # this example is from the MAGMA handbook
1068            sage: P.<x, y> = PolynomialRing(K, 2, order='lex')
1069            sage: I = Ideal([ x^8 + y + 2, y^6 + x*y^5 + x^2 ])
1070            sage: I = Ideal(I.groebner_basis()); I
1071            Ideal (y^48 + y^41 - y^40 + y^37 - y^36 - y^33 + y^32 - y^29 + y^28 -
1072            y^25 + y^24 + y^2 + y + 1, x - y^47 - y^45 + y^44 - y^43 + y^41 - y^39 -
1073            y^38 - y^37 - y^36 + y^35 - y^34 - y^33 + y^32 - y^31 + y^30 + y^28 +
1074            y^27 + y^26 + y^25 - y^23 + y^22 + y^21 - y^19 - y^18 - y^16 + y^15 +
1075            y^13 + y^12 - y^10 + y^9 + y^8 + y^7 - y^6 + y^4 + y^3 + y^2 + y - 1) of
1076            Multivariate Polynomial Ring in x, y over Finite Field in w of size 3^3
1077
1078            sage: V = I.variety(); V
1079            [{y: w^2 + 2, x: 2*w}, {y: w^2 + w, x: 2*w + 1}, {y: w^2 + 2*w, x: 2*w + 2}]
1080
1081            sage: [f.subs(v) for f in I.gens() for v in V] # check that all polynomials vanish
1082            [0, 0, 0, 0, 0, 0]
1083
1084            However, we only account for solutions in the ground field and
1085            not in the algebraic closure.
1086
1087            sage: I.vector_space_dimension()
1088            48
1089
1090        ALGORITHM: Uses triangular decomposition.
1091        """
1092        def _variety(T, V, v=None):
1093            if v is None: v = {}
1094            found = False
1095            for f in T:
1096                if f.is_univariate() and not f.is_constant():
1097                    T.remove(f); found = True; break
1098
1099            if found is False:
1100                V.append(v)
1101                return V
1102
1103            variable = f.variable(0)
1104            roots = f.univariate_polynomial().roots()
1105
1106            for root,multiplicity in roots:
1107                vbar = v.copy()
1108                vbar[variable] = root
1109                Tbar = [ f.subs({variable:root}) for f in T ]
1110                _variety(Tbar,V,vbar)
1111
1112            return V
1113
1114        P = self.ring()
1115        T = self.triangular_decomposition('singular:triangLfak')
1116
1117        V = []
1118        for t in T:
1119            Vbar = _variety(list(t.gens()),[])
1120
1121            for v in Vbar:
1122                V.append(dict([(P(var),val) for var,val in v.iteritems()]))
1123        V.sort()
1124        return Sequence(V)
1125
1126class MPolynomialIdeal_macaulay2_repr:
1127    """
1128    An ideal in a multivariate polynomial ring, which has an underlying
1129    Macaulay2 ring associated to it.
1130   
1131    EXAMPLES:
1132        sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4) # optional
1133        sage: I = ideal(x*y-z^2, y^2-w^2)       # optional
1134        sage: I                                 # optional
1135        Ideal (x*y - z^2, y^2 - w^2) of Multivariate Polynomial Ring in x, y, z, w over Integer Ring
1136    """
1137    #def __init__(self, ring, gens, coerce=True):
1138    #    MPolynomialIdeal.__init__(self, ring, gens, coerce=coerce)
1139
1140    def _macaulay2_(self, macaulay2=None):
1141        """
1142        Return Macaulay2 ideal corresponding to this ideal.
1143        """
1144        if macaulay2 is None: macaulay2 = macaulay2_default
1145        try:
1146            I = self.__macaulay2[macaulay2]
1147            I._check_valid()
1148            return I
1149        except KeyError:
1150            pass
1151        except AttributeError:
1152            self.__macaulay2 = {}
1153        except ValueError:
1154            pass
1155       
1156        R = self.ring()
1157        R._macaulay2_set_ring(macaulay2)
1158       
1159        gens = [repr(x) for x in self.gens()]
1160        if len(gens) == 0:
1161            gens = ['0']
1162        z = macaulay2.ideal(gens)
1163        self.__macaulay2[macaulay2] = z
1164        return z
1165
1166    def _macaulay2_groebner_basis(self):
1167        r"""
1168        Return the Groebner basis for this ideal, computed using Macaulay2.
1169
1170        ALGORITHM: Computed using Macaulay2.  A big advantage of
1171        Macaulay2 is that it can compute Groebner basis of ideals in
1172        polynomial rings over the integers.
1173
1174        EXAMPLE:
1175            sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
1176            sage: I = ideal(x*y-z^2, y^2-w^2)                           
1177            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1178            [y^2 - w^2, x*y - z^2, y*z^2 - x*w^2, z^4 - x^2*w^2]
1179
1180        Groebner basis can be used to compute in $\Z/n\Z[x,\ldots]$.
1181
1182            sage: R.<x,y,z> = ZZ[]
1183            sage: I = ideal([y^2*z - x^3 - 19*x*z, y^2, 19^2])         
1184            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1185            [361, y^2, x^3 + 19*x*z]
1186            sage: I = ideal([y^2*z - x^3 - 19^2*x*z, y^2, 19^2])
1187            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1188            [361, y^2, x^3]
1189        """
1190        try:
1191            return self.__groebner_basis
1192        except AttributeError:
1193            I = self._macaulay2_()
1194            G = str(I.gb().generators().str()).replace('\n','')
1195            i = G.rfind('{{')
1196            j = G.rfind('}}')
1197            G = G[i+2:j].split(',')
1198            L = self.ring().gens_dict()
1199            B = [sage_eval(f, L) for f in G]
1200            B = Sequence(B, self.ring(), check=False)
1201            B.sort()
1202            B.set_immutable()
1203            self.__groebner_basis = B
1204            return B
1205           
1206    def _reduce_using_macaulay2(self, f):
1207        """
1208        EXAMPLES:
1209            sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
1210            sage: I = ideal(x*y-z^2, y^2-w^2)
1211            sage: I._reduce_using_macaulay2(x*y-z^2 + y^2)    # optional
1212            w^2
1213        """
1214        I = self._macaulay2_()
1215        M2 = I.parent()
1216        k = M2('(%r) %% %s'%(f, I.name()))
1217        R = self.ring()
1218        return R(k)
1219
1220
1221class MPolynomialIdeal( MPolynomialIdeal_singular_repr, \
1222                        MPolynomialIdeal_macaulay2_repr, \
1223                        MPolynomialIdeal_magma_repr, \
1224                        Ideal_generic ):
1225    """
1226    An ideal of a multivariate polynomial ring.
1227    """
1228    def __init__(self, ring, gens, coerce=True):
1229        """
1230        Create an ideal in a multivariate polynomial ring.
1231
1232        EXAMPLES:
1233            sage: R.<x,y> = PolynomialRing(IntegerRing(), 2, order='lex')
1234            sage: R.ideal([x, y])
1235            Ideal (x, y) of Multivariate Polynomial Ring in x, y over Integer Ring
1236            sage: R.<x0,x1> = GF(3)[]
1237            sage: R.ideal([x0^2, x1^3])
1238            Ideal (x0^2, x1^3) of Multivariate Polynomial Ring in x0, x1 over Finite Field of size 3
1239        """
1240        Ideal_generic.__init__(self, ring, gens, coerce=coerce)
1241
1242    def groebner_fan(self, is_groebner_basis=False, symmetry=None, verbose=False):
1243        r"""
1244        Return the Groebner fan of this ideal.
1245
1246        The base ring must be $\Q$ or a finite field $\F_p$ of with
1247        $p \leq 32749$.
1248
1249        INPUT:
1250            is_groebner_basis -- bool (default False).  if True, then I.gens() must be
1251                                 a Groebner basis with respect to the standard
1252                                 degree lexicographic term order.
1253            symmetry -- default: None; if not None, describes symmetries of the ideal
1254            verbose -- default: False; if True, printout useful info during computations
1255        """
1256        import groebner_fan
1257        return groebner_fan.GroebnerFan(self, is_groebner_basis=is_groebner_basis,
1258                                        symmetry=symmetry, verbose=verbose)
1259
1260    def groebner_basis(self, algorithm=None):
1261        """
1262        Return a Groebner basis of this ideal.
1263
1264        INPUT:
1265            algorithm -- determines the algorithm to use, available are:
1266                         * None - autoselect (default)
1267                         * 'singular:groebner' - Singular's groebner command
1268                         * 'singular:std' - Singular's std command
1269                         * 'singular:stdhilb' - Singular's stdhib command
1270                         * 'singular:stdfglm' - Singular's stdfglm command
1271                         * 'singular:slimgb' - Singular's slimgb command
1272                         * 'libsingular:std' - libSINGULAR's std command
1273                         * 'libsingular:slimgb' - libSINGULAR's slimgb command
1274                         * 'toy:buchberger' - SAGE's toy/educational buchberger without strategy
1275                         * 'toy:buchberger2' - SAGE's toy/educational buchberger with strategy
1276                         * 'macaulay2:gb' (if available) - Macaulay2's gb command
1277                         * 'magma:GroebnerBasis' (if available) - MAGMA's Groebnerbasis command
1278
1279        EXAMPLES:
1280            Consider Katsura-3 over QQ with term ordering 'degrevlex'
1281
1282            sage: P.<a,b,c> = PolynomialRing(QQ,3, order='lex')
1283            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1284            sage: I.groebner_basis()
1285            [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7]
1286
1287
1288            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1289            sage: I.groebner_basis('singular:groebner')
1290            [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7]
1291
1292            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1293            sage: I.groebner_basis('singular:std')
1294            [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7]
1295
1296            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1297            sage: I.groebner_basis('singular:stdhilb')
1298            [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7]
1299
1300            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1301            sage: I.groebner_basis('singular:stdfglm')
1302            [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7]
1303
1304            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1305            sage: I.groebner_basis('singular:slimgb')
1306            [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7]
1307
1308            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1309            sage: I.groebner_basis('toy:buchberger')
1310            [a + 2*b + 2*c - 1, -6*b^2 - 8*b*c + 2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b, 7/250*b + 21/25*c^3 - 79/250*c^2 + 3/250*c, a^2 - a + 2*b^2 + 2*c^2, -5/3*b*c + 1/6*b - 2*c^2 + 2/3*c, -30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c]
1311
1312            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1313            sage: I.groebner_basis('toy:buchberger2')
1314            [a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, 30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, -7/250*b - 21/25*c^3 + 79/250*c^2 - 3/250*c]
1315
1316            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1317            sage: I.groebner_basis('macaulay2:gb') # optional requires Macaulay2
1318            [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7]
1319           
1320            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1321            sage: I.groebner_basis('magma:GroebnerBasis') # optional requires MAGMA
1322            [a - 60*c^3 + 158/7*c^2 + 8/7*c - 1, b + 30*c^3 - 79/7*c^2 + 3/7*c, c^4 - 10/21*c^3 + 1/84*c^2 + 1/84*c]
1323
1324            If Macaulay2 is installed, Groebner bases over ZZ can be computed.
1325
1326            sage: P.<a,b,c> = PolynomialRing(ZZ,3)
1327            sage: I = P * (a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, 2*a*b + 2*b*c - b)
1328            sage: I.groebner_basis() #optional requires Macaulay2
1329            [a + 2*b + 2*c - 1, 10*b*c + 12*c^2 - b - 4*c, 2*b^2 - 4*b*c - 6*c^2 + 2*c,
1330             42*c^3 + b^2 + 2*b*c - 14*c^2 + b, 2*b*c^2 - 6*c^3 + b^2 + 5*b*c + 8*c^2 - b - 2*c,
1331             b^3 + b*c^2 + 12*c^3 + b^2 + b*c - 4*c^2]
1332
1333            SAGE also supports local orderings (via SINGULAR):
1334
1335            sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdegrevlex')
1336            sage: I = P * (  x*y*z + z^5, 2*x^2 + y^3 + z^7, 3*z^5 +y ^5 )
1337            sage: I.groebner_basis()
1338            [2*x^2 + y^3, x*y*z + z^5, y^5 + 3*z^5, y^4*z - 2*x*z^5, z^6]
1339
1340        ALGORITHM: Uses Singular, MAGMA (if available), Macaulay2 (if
1341        available), or toy implementation.
1342
1343        """
1344        if algorithm is None:
1345            if self.ring().base_ring() == sage.rings.integer_ring.ZZ:
1346                return self._macaulay2_groebner_basis()
1347            else:
1348                return self._groebner_basis_using_singular("groebner")
1349        elif algorithm.startswith('singular:'):
1350            return self._groebner_basis_using_singular(algorithm[9:])
1351        elif algorithm.startswith('libsingular:'):
1352            return self._groebner_basis_using_libsingular(algorithm[len('libsingular:'):])
1353        elif algorithm == 'macaulay2:gb':
1354            return self._macaulay2_groebner_basis()
1355        elif algorithm == 'magma:GroebnerBasis':
1356            return self._magma_groebner_basis()
1357        elif algorithm == 'toy:buchberger':
1358            return toy_buchberger.buchberger(self)
1359        elif algorithm == 'toy:buchberger2':
1360            return toy_buchberger.buchberger_improved(self)
1361        else:
1362            raise TypeError, "algorithm '%s' unknown"%algorithm
1363
1364
1365    def change_ring(self, P):
1366        r"""
1367        Return the ideal $I$ in $P$ spanned by the generators $g_1,
1368        ..., g_n$ of self as returned by self.gens().
1369
1370        INPUT:
1371            P -- a multivariate polynomial ring
1372
1373        EXAMPLE:
1374           sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex')
1375           sage: I = sage.rings.ideal.Cyclic(P)
1376           sage: I
1377           Ideal (x + y + z, x*y + x*z + y*z, x*y*z - 1) of Multivariate Polynomial Ring in x, y, z over Rational Field
1378           sage: I.groebner_basis()
1379           [z^3 - 1, y^2 + y*z + z^2, x + y + z]
1380
1381           sage: Q.<x,y,z> = P.new_ring(order='degrevlex'); Q
1382           Multivariate Polynomial Ring in x, y, z over Rational Field
1383           sage: Q.term_order()
1384           Degree reverse lexicographic term order
1385
1386           sage: J = I.change_ring(Q); J
1387           Ideal (x + y + z, x*y + x*z + y*z, x*y*z - 1) of Multivariate Polynomial Ring in x, y, z over Rational Field
1388           sage: J.groebner_basis()
1389           [x + y + z, y^2 + y*z + z^2, z^3 - 1]
1390        """
1391        return P.ideal([P(f) for f in self.gens()])
Note: See TracBrowser for help on using the repository browser.