source: sage/rings/polynomial/multi_polynomial_ideal.py @ 7102:d7dd712d2e0b

Revision 7102:d7dd712d2e0b, 55.0 KB checked in by Martin Albrecht <malb@…>, 6 years ago (diff)

wrapped getting/setting singular attributes
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 + 2*w, x: 2*w + 2}, {y: w^2 + w, x: 2*w + 1}]
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        return Sequence(V)
1124
1125class MPolynomialIdeal_macaulay2_repr:
1126    """
1127    An ideal in a multivariate polynomial ring, which has an underlying
1128    Macaulay2 ring associated to it.
1129   
1130    EXAMPLES:
1131        sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4) # optional
1132        sage: I = ideal(x*y-z^2, y^2-w^2)       # optional
1133        sage: I                                 # optional
1134        Ideal (x*y - z^2, y^2 - w^2) of Multivariate Polynomial Ring in x, y, z, w over Integer Ring
1135    """
1136    #def __init__(self, ring, gens, coerce=True):
1137    #    MPolynomialIdeal.__init__(self, ring, gens, coerce=coerce)
1138
1139    def _macaulay2_(self, macaulay2=None):
1140        """
1141        Return Macaulay2 ideal corresponding to this ideal.
1142        """
1143        if macaulay2 is None: macaulay2 = macaulay2_default
1144        try:
1145            I = self.__macaulay2[macaulay2]
1146            I._check_valid()
1147            return I
1148        except KeyError:
1149            pass
1150        except AttributeError:
1151            self.__macaulay2 = {}
1152        except ValueError:
1153            pass
1154       
1155        R = self.ring()
1156        R._macaulay2_set_ring(macaulay2)
1157       
1158        gens = [repr(x) for x in self.gens()]
1159        if len(gens) == 0:
1160            gens = ['0']
1161        z = macaulay2.ideal(gens)
1162        self.__macaulay2[macaulay2] = z
1163        return z
1164
1165    def _macaulay2_groebner_basis(self):
1166        r"""
1167        Return the Groebner basis for this ideal, computed using Macaulay2.
1168
1169        ALGORITHM: Computed using Macaulay2.  A big advantage of
1170        Macaulay2 is that it can compute Groebner basis of ideals in
1171        polynomial rings over the integers.
1172
1173        EXAMPLE:
1174            sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
1175            sage: I = ideal(x*y-z^2, y^2-w^2)                           
1176            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1177            [y^2 - w^2, x*y - z^2, y*z^2 - x*w^2, z^4 - x^2*w^2]
1178
1179        Groebner basis can be used to compute in $\Z/n\Z[x,\ldots]$.
1180
1181            sage: R.<x,y,z> = ZZ[]
1182            sage: I = ideal([y^2*z - x^3 - 19*x*z, y^2, 19^2])         
1183            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1184            [361, y^2, x^3 + 19*x*z]
1185            sage: I = ideal([y^2*z - x^3 - 19^2*x*z, y^2, 19^2])
1186            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1187            [361, y^2, x^3]
1188        """
1189        try:
1190            return self.__groebner_basis
1191        except AttributeError:
1192            I = self._macaulay2_()
1193            G = str(I.gb().generators().str()).replace('\n','')
1194            i = G.rfind('{{')
1195            j = G.rfind('}}')
1196            G = G[i+2:j].split(',')
1197            L = self.ring().gens_dict()
1198            B = [sage_eval(f, L) for f in G]
1199            B = Sequence(B, self.ring(), check=False)
1200            B.sort()
1201            B.set_immutable()
1202            self.__groebner_basis = B
1203            return B
1204           
1205    def _reduce_using_macaulay2(self, f):
1206        """
1207        EXAMPLES:
1208            sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
1209            sage: I = ideal(x*y-z^2, y^2-w^2)
1210            sage: I._reduce_using_macaulay2(x*y-z^2 + y^2)    # optional
1211            w^2
1212        """
1213        I = self._macaulay2_()
1214        M2 = I.parent()
1215        k = M2('(%r) %% %s'%(f, I.name()))
1216        R = self.ring()
1217        return R(k)
1218
1219
1220class MPolynomialIdeal( MPolynomialIdeal_singular_repr, \
1221                        MPolynomialIdeal_macaulay2_repr, \
1222                        MPolynomialIdeal_magma_repr, \
1223                        Ideal_generic ):
1224    """
1225    An ideal of a multivariate polynomial ring.
1226    """
1227    def __init__(self, ring, gens, coerce=True):
1228        """
1229        Create an ideal in a multivariate polynomial ring.
1230
1231        EXAMPLES:
1232            sage: R.<x,y> = PolynomialRing(IntegerRing(), 2, order='lex')
1233            sage: R.ideal([x, y])
1234            Ideal (x, y) of Multivariate Polynomial Ring in x, y over Integer Ring
1235            sage: R.<x0,x1> = GF(3)[]
1236            sage: R.ideal([x0^2, x1^3])
1237            Ideal (x0^2, x1^3) of Multivariate Polynomial Ring in x0, x1 over Finite Field of size 3
1238        """
1239        Ideal_generic.__init__(self, ring, gens, coerce=coerce)
1240
1241    def groebner_fan(self, is_groebner_basis=False, symmetry=None, verbose=False):
1242        r"""
1243        Return the Groebner fan of this ideal.
1244
1245        The base ring must be $\Q$ or a finite field $\F_p$ of with
1246        $p \leq 32749$.
1247
1248        INPUT:
1249            is_groebner_basis -- bool (default False).  if True, then I.gens() must be
1250                                 a Groebner basis with respect to the standard
1251                                 degree lexicographic term order.
1252            symmetry -- default: None; if not None, describes symmetries of the ideal
1253            verbose -- default: False; if True, printout useful info during computations
1254        """
1255        import groebner_fan
1256        return groebner_fan.GroebnerFan(self, is_groebner_basis=is_groebner_basis,
1257                                        symmetry=symmetry, verbose=verbose)
1258
1259    def groebner_basis(self, algorithm=None):
1260        """
1261        Return a Groebner basis of this ideal.
1262
1263        INPUT:
1264            algorithm -- determines the algorithm to use, available are:
1265                         * None - autoselect (default)
1266                         * 'singular:groebner' - Singular's groebner command
1267                         * 'singular:std' - Singular's std command
1268                         * 'singular:stdhilb' - Singular's stdhib command
1269                         * 'singular:stdfglm' - Singular's stdfglm command
1270                         * 'singular:slimgb' - Singular's slimgb command
1271                         * 'libsingular:std' - libSINGULAR's std command
1272                         * 'libsingular:slimgb' - libSINGULAR's slimgb command
1273                         * 'toy:buchberger' - SAGE's toy/educational buchberger without strategy
1274                         * 'toy:buchberger2' - SAGE's toy/educational buchberger with strategy
1275                         * 'macaulay2:gb' (if available) - Macaulay2's gb command
1276                         * 'magma:GroebnerBasis' (if available) - MAGMA's Groebnerbasis command
1277
1278        EXAMPLES:
1279            Consider Katsura-3 over QQ with term ordering 'degrevlex'
1280
1281            sage: P.<a,b,c> = PolynomialRing(QQ,3, order='lex')
1282            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1283            sage: I.groebner_basis()
1284            [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]
1285
1286
1287            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1288            sage: I.groebner_basis('singular:groebner')
1289            [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]
1290
1291            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1292            sage: I.groebner_basis('singular:std')
1293            [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]
1294
1295            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1296            sage: I.groebner_basis('singular:stdhilb')
1297            [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]
1298
1299            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1300            sage: I.groebner_basis('singular:stdfglm')
1301            [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]
1302
1303            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1304            sage: I.groebner_basis('singular:slimgb')
1305            [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]
1306
1307            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1308            sage: I.groebner_basis('toy:buchberger')
1309            [-30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c, -2*b^2 - b*c + 1/2*b, -7/125*b - 42/25*c^3 + 79/125*c^2 - 3/125*c,
1310            a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, -5*b*c + 1/2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b]
1311           
1312            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1313            sage: I.groebner_basis('toy:buchberger2')
1314            [30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, a + 2*b + 2*c - 1,
1315             7/125*b + 42/25*c^3 - 79/125*c^2 + 3/125*c, a^2 - a + 2*b^2 + 2*c^2]
1316
1317            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1318            sage: I.groebner_basis('macaulay2:gb') # optional requires Macaulay2
1319            [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]
1320           
1321            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1322            sage: I.groebner_basis('magma:GroebnerBasis') # optional requires MAGMA
1323            [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]
1324
1325            If Macaulay2 is installed, Groebner bases over ZZ can be computed.
1326
1327            sage: P.<a,b,c> = PolynomialRing(ZZ,3)
1328            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)
1329            sage: I.groebner_basis() #optional requires Macaulay2
1330            [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,
1331             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,
1332             b^3 + b*c^2 + 12*c^3 + b^2 + b*c - 4*c^2]
1333
1334            SAGE also supports local orderings (via SINGULAR):
1335
1336            sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdegrevlex')
1337            sage: I = P * (  x*y*z + z^5, 2*x^2 + y^3 + z^7, 3*z^5 +y ^5 )
1338            sage: I.groebner_basis()
1339            [2*x^2 + y^3, x*y*z + z^5, y^5 + 3*z^5, y^4*z - 2*x*z^5, z^6]
1340
1341        ALGORITHM: Uses Singular, MAGMA (if available), Macaulay2 (if
1342        available), or toy implementation.
1343
1344        """
1345        if algorithm is None:
1346            if self.ring().base_ring() == sage.rings.integer_ring.ZZ:
1347                return self._macaulay2_groebner_basis()
1348            else:
1349                return self._groebner_basis_using_singular("groebner")
1350        elif algorithm.startswith('singular:'):
1351            return self._groebner_basis_using_singular(algorithm[9:])
1352        elif algorithm.startswith('libsingular:'):
1353            return self._groebner_basis_using_libsingular(algorithm[len('libsingular:'):])
1354        elif algorithm == 'macaulay2:gb':
1355            return self._macaulay2_groebner_basis()
1356        elif algorithm == 'magma:GroebnerBasis':
1357            return self._magma_groebner_basis()
1358        elif algorithm == 'toy:buchberger':
1359            return toy_buchberger.buchberger(self)
1360        elif algorithm == 'toy:buchberger2':
1361            return toy_buchberger.buchberger_improved(self)
1362        else:
1363            raise TypeError, "algorithm '%s' unknown"%algorithm
1364
1365
1366    def change_ring(self, P):
1367        r"""
1368        Return the ideal $I$ in $P$ spanned by the generators $g_1,
1369        ..., g_n$ of self as returned by self.gens().
1370
1371        INPUT:
1372            P -- a multivariate polynomial ring
1373
1374        EXAMPLE:
1375           sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex')
1376           sage: I = sage.rings.ideal.Cyclic(P)
1377           sage: I
1378           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
1379           sage: I.groebner_basis()
1380           [z^3 - 1, y^2 + y*z + z^2, x + y + z]
1381
1382           sage: Q.<x,y,z> = P.new_ring(order='degrevlex'); Q
1383           Multivariate Polynomial Ring in x, y, z over Rational Field
1384           sage: Q.term_order()
1385           Degree reverse lexicographic term order
1386
1387           sage: J = I.change_ring(Q); J
1388           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
1389           sage: J.groebner_basis()
1390           [x + y + z, y^2 + y*z + z^2, z^3 - 1]
1391        """
1392        return P.ideal([P(f) for f in self.gens()])
Note: See TracBrowser for help on using the repository browser.