source: sage/rings/polynomial/multi_polynomial_ideal.py @ 7075:e2963fe3d09a

Revision 7075:e2963fe3d09a, 55.0 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

Carl Witty -- fix bug in new singular coding.
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        return True
921
922    def transformed_basis(self,algorithm="gwalk", other_ring=None):
923        """
924        Returns a lex or other_ring Groebner Basis for a given ideal
925        self which must be represented through a Groebner Basis.
926       
927        INPUT:
928           algorithm -- Options are:
929                        * fglm - FGLM algorithm. The input ideal must be
930                                 a reduced Groebner Basis of a zero-dimensional ideal
931                        * gwalk (default) - Groebner Walk algorithm
932                        * awalk1 - 'first alternative' algorithm
933                        * awalk2 - 'second alternative' algorithm
934                        * twalk  - Tran algorithm
935                        * fwalk  - Fractal Walk algorithm
936           other_ring  -- only valid for algorithm 'fglm', if provided conversion will
937                          be performed to this ring. Otherwise a lex Groebner basis will
938                          be returned.
939        EXAMPLES:
940           sage: # example from the Singular manual page of fglm
941           sage: R.<x,y,z> = PolynomialRing(QQ,3)
942           sage: I = Ideal([y^3+x^2,x^2*y+x^2, x^3-x^2, z^4-x^2-y])
943           sage: singular.option('redSB')
944           sage: I = Ideal(I.groebner_basis())
945           sage: singular.option('noredSB') #reset
946           sage: S.<z,x,y> = PolynomialRing(QQ,3,order='lex')
947           sage: J = Ideal(I.transformed_basis('fglm',S))
948           sage: J
949           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
950           sage: # example from the Singular manual page of gwalk
951           sage: R.<z,y,x>=PolynomialRing(GF(32003),3,order='lex')
952           sage: I=Ideal([y^3+x*y*z+y^2*z+x*z^3,3+x*y+x^2*y+y^2*z])
953           sage: I.transformed_basis('gwalk')
954           [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,
955           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,
956           z*y^2 + y*x^2 + y*x + 3]
957
958
959        ALGORITHM: Uses Singular
960        """
961        from sage.rings.polynomial.multi_polynomial_ring import TermOrder,MPolynomialRing
962        from sage.rings.quotient_ring import is_QuotientRing       
963       
964        Is = self._singular_()
965        R = self.ring()
966
967        if algorithm in ("gwalk","awalk1","awalk2","twalk","fwalk"):
968            singular.LIB("grwalk")
969            gb = singular("%s(%s)"%(algorithm,Is.name()))
970            return [R(f) for f in gb]
971        elif algorithm == "fglm":
972            Rs = self.ring()._singular_()
973
974            # new ring
975            if other_ring==None:
976                nR = MPolynomialRing(R.base_ring(),R.ngens(), names=R.variable_names(), order="lex")
977            else:
978                nR = other_ring
979            nR._singular_().set_ring()
980           
981            nIs = singular.fglm(Rs,Is)
982
983            return [nR(f) for f in nIs]
984
985        else:
986            raise TypeError, "Cannot convert basis with given algorithm"
987
988    def elimination_ideal(self, variables):
989        """
990        Returns the elimination ideal of self with respect to the
991        variables given in 'variables'.
992
993        INPUT:
994            variables -- a list or tuple of variables in self.ring()
995
996        EXAMPLE:
997            sage: R.<x,y,t,s,z> = PolynomialRing(QQ,5)
998            sage: I = R * [x-t,y-t^2,z-t^3,s-x+y^3]
999            sage: I.elimination_ideal([t,s])
1000            Ideal (y^2 - x*z, x*y - z, x^2 - y) of Multivariate Polynomial Ring in x, y, t, s, z over Rational Field
1001
1002        ALGORITHM: Uses SINGULAR
1003
1004        NOTE: Requires computation of a Groebner basis, which is a
1005        very expensive operation.
1006        """
1007        if not isinstance(variables, (list,tuple)):
1008            variables = (variables,)
1009       
1010        try:
1011            Is = self.__singular_groebner_basis
1012        except AttributeError:
1013            Is = self._singular_()
1014
1015        R = self.ring()
1016        return MPolynomialIdeal(R, [f.sage_poly(R) for f in Is.eliminate( prod(variables) ) ] )
1017
1018    def quotient(self, J):
1019        r"""
1020        Given ideals I (==self) and J of the same polynomial ring P,
1021        return the ideal quotient of I by J consisting of the
1022        polynomials a of P such that $\{aJ \subset I\}$.
1023
1024        This is also referred to as the colon ideal (I:J).
1025
1026        INPUT:
1027            J -- multivariate polynomial ideal
1028
1029        EXAMPLE:
1030            sage: R.<x,y,z> = PolynomialRing(GF(181),3)
1031            sage: I = Ideal([x^2+x*y*z,y^2-z^3*y,z^3+y^5*x*z])
1032            sage: J = Ideal([x])
1033            sage: Q = I.quotient(J)
1034            sage: y*z + x in I
1035            False
1036            sage: x in J
1037            True
1038            sage: x * (y*z + x) in I
1039            True
1040        """
1041        R = self.ring()
1042
1043        if not isinstance(J, MPolynomialIdeal):
1044            raise TypeError, "J needs to be a multivariate polynomial ideal"
1045
1046        if not R is J.ring() and not R == J.ring():
1047            raise TypeError, "base rings do not match"
1048
1049        return R.ideal([f.sage_poly(R) for f in self._singular_().quotient(J._singular_())])
1050
1051    def variety(self):
1052        """
1053        Return the variety of self.
1054
1055        Given a zero-dimensional ideal I (== self) of a polynomial ring P
1056        whose order is lexicographic, return the variety of I over its
1057        coefficient field K as a list of dictionaries with (variable, value)
1058        pairs.
1059
1060        These dictionaries have cardinality equal to the number of
1061        variables in P and represent assignments of values to these
1062        variables such that all polynomials in I vanish.
1063
1064        EXAMPLE:
1065            sage: K.<w> = GF(27) # this example is from the MAGMA handbook
1066            sage: P.<x, y> = PolynomialRing(K, 2, order='lex')
1067            sage: I = Ideal([ x^8 + y + 2, y^6 + x*y^5 + x^2 ])
1068            sage: I = Ideal(I.groebner_basis()); I
1069            Ideal (y^48 + y^41 - y^40 + y^37 - y^36 - y^33 + y^32 - y^29 + y^28 -
1070            y^25 + y^24 + y^2 + y + 1, x - y^47 - y^45 + y^44 - y^43 + y^41 - y^39 -
1071            y^38 - y^37 - y^36 + y^35 - y^34 - y^33 + y^32 - y^31 + y^30 + y^28 +
1072            y^27 + y^26 + y^25 - y^23 + y^22 + y^21 - y^19 - y^18 - y^16 + y^15 +
1073            y^13 + y^12 - y^10 + y^9 + y^8 + y^7 - y^6 + y^4 + y^3 + y^2 + y - 1) of
1074            Multivariate Polynomial Ring in x, y over Finite Field in w of size 3^3
1075
1076            sage: V = I.variety(); V
1077            [{y: w^2 + 2, x: 2*w}, {y: w^2 + 2*w, x: 2*w + 2}, {y: w^2 + w, x: 2*w + 1}]
1078
1079            sage: [f.subs(v) for f in I.gens() for v in V] # check that all polynomials vanish
1080            [0, 0, 0, 0, 0, 0]
1081
1082            However, we only account for solutions in the ground field and
1083            not in the algebraic closure.
1084
1085            sage: I.vector_space_dimension()
1086            48
1087
1088        ALGORITHM: Uses triangular decomposition.
1089        """
1090        def _variety(T, V, v=None):
1091            if v is None: v = {}
1092            found = False
1093            for f in T:
1094                if f.is_univariate() and not f.is_constant():
1095                    T.remove(f); found = True; break
1096
1097            if found is False:
1098                V.append(v)
1099                return V
1100
1101            variable = f.variable(0)
1102            roots = f.univariate_polynomial().roots()
1103
1104            for root,multiplicity in roots:
1105                vbar = v.copy()
1106                vbar[variable] = root
1107                Tbar = [ f.subs({variable:root}) for f in T ]
1108                _variety(Tbar,V,vbar)
1109
1110            return V
1111
1112        P = self.ring()
1113        T = self.triangular_decomposition('singular:triangLfak')
1114
1115        V = []
1116        for t in T:
1117            Vbar = _variety(list(t.gens()),[])
1118
1119            for v in Vbar:
1120                V.append(dict([(P(var),val) for var,val in v.iteritems()]))
1121        return Sequence(V)
1122
1123class MPolynomialIdeal_macaulay2_repr:
1124    """
1125    An ideal in a multivariate polynomial ring, which has an underlying
1126    Macaulay2 ring associated to it.
1127   
1128    EXAMPLES:
1129        sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4) # optional
1130        sage: I = ideal(x*y-z^2, y^2-w^2)       # optional
1131        sage: I                                 # optional
1132        Ideal (x*y - z^2, y^2 - w^2) of Multivariate Polynomial Ring in x, y, z, w over Integer Ring
1133    """
1134    #def __init__(self, ring, gens, coerce=True):
1135    #    MPolynomialIdeal.__init__(self, ring, gens, coerce=coerce)
1136
1137    def _macaulay2_(self, macaulay2=None):
1138        """
1139        Return Macaulay2 ideal corresponding to this ideal.
1140        """
1141        if macaulay2 is None: macaulay2 = macaulay2_default
1142        try:
1143            I = self.__macaulay2[macaulay2]
1144            I._check_valid()
1145            return I
1146        except KeyError:
1147            pass
1148        except AttributeError:
1149            self.__macaulay2 = {}
1150        except ValueError:
1151            pass
1152       
1153        R = self.ring()
1154        R._macaulay2_set_ring(macaulay2)
1155       
1156        gens = [repr(x) for x in self.gens()]
1157        if len(gens) == 0:
1158            gens = ['0']
1159        z = macaulay2.ideal(gens)
1160        self.__macaulay2[macaulay2] = z
1161        return z
1162
1163    def _macaulay2_groebner_basis(self):
1164        r"""
1165        Return the Groebner basis for this ideal, computed using Macaulay2.
1166
1167        ALGORITHM: Computed using Macaulay2.  A big advantage of
1168        Macaulay2 is that it can compute Groebner basis of ideals in
1169        polynomial rings over the integers.
1170
1171        EXAMPLE:
1172            sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
1173            sage: I = ideal(x*y-z^2, y^2-w^2)                           
1174            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1175            [y^2 - w^2, x*y - z^2, y*z^2 - x*w^2, z^4 - x^2*w^2]
1176
1177        Groebner basis can be used to compute in $\Z/n\Z[x,\ldots]$.
1178
1179            sage: R.<x,y,z> = ZZ[]
1180            sage: I = ideal([y^2*z - x^3 - 19*x*z, y^2, 19^2])         
1181            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1182            [361, y^2, x^3 + 19*x*z]
1183            sage: I = ideal([y^2*z - x^3 - 19^2*x*z, y^2, 19^2])
1184            sage: I.groebner_basis()                                     # optional -- requires macaulay2
1185            [361, y^2, x^3]
1186        """
1187        try:
1188            return self.__groebner_basis
1189        except AttributeError:
1190            I = self._macaulay2_()
1191            G = str(I.gb().generators().str()).replace('\n','')
1192            i = G.rfind('{{')
1193            j = G.rfind('}}')
1194            G = G[i+2:j].split(',')
1195            L = self.ring().gens_dict()
1196            B = [sage_eval(f, L) for f in G]
1197            B = Sequence(B, self.ring(), check=False)
1198            B.sort()
1199            B.set_immutable()
1200            self.__groebner_basis = B
1201            return B
1202           
1203    def _reduce_using_macaulay2(self, f):
1204        """
1205        EXAMPLES:
1206            sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
1207            sage: I = ideal(x*y-z^2, y^2-w^2)
1208            sage: I._reduce_using_macaulay2(x*y-z^2 + y^2)    # optional
1209            w^2
1210        """
1211        I = self._macaulay2_()
1212        M2 = I.parent()
1213        k = M2('(%r) %% %s'%(f, I.name()))
1214        R = self.ring()
1215        return R(k)
1216
1217
1218class MPolynomialIdeal( MPolynomialIdeal_singular_repr, \
1219                        MPolynomialIdeal_macaulay2_repr, \
1220                        MPolynomialIdeal_magma_repr, \
1221                        Ideal_generic ):
1222    """
1223    An ideal of a multivariate polynomial ring.
1224    """
1225    def __init__(self, ring, gens, coerce=True):
1226        """
1227        Create an ideal in a multivariate polynomial ring.
1228
1229        EXAMPLES:
1230            sage: R.<x,y> = PolynomialRing(IntegerRing(), 2, order='lex')
1231            sage: R.ideal([x, y])
1232            Ideal (x, y) of Multivariate Polynomial Ring in x, y over Integer Ring
1233            sage: R.<x0,x1> = GF(3)[]
1234            sage: R.ideal([x0^2, x1^3])
1235            Ideal (x0^2, x1^3) of Multivariate Polynomial Ring in x0, x1 over Finite Field of size 3
1236        """
1237        Ideal_generic.__init__(self, ring, gens, coerce=coerce)
1238
1239    def groebner_fan(self, is_groebner_basis=False, symmetry=None, verbose=False):
1240        r"""
1241        Return the Groebner fan of this ideal.
1242
1243        The base ring must be $\Q$ or a finite field $\F_p$ of with
1244        $p \leq 32749$.
1245
1246        INPUT:
1247            is_groebner_basis -- bool (default False).  if True, then I.gens() must be
1248                                 a Groebner basis with respect to the standard
1249                                 degree lexicographic term order.
1250            symmetry -- default: None; if not None, describes symmetries of the ideal
1251            verbose -- default: False; if True, printout useful info during computations
1252        """
1253        import groebner_fan
1254        return groebner_fan.GroebnerFan(self, is_groebner_basis=is_groebner_basis,
1255                                        symmetry=symmetry, verbose=verbose)
1256
1257    def groebner_basis(self, algorithm=None):
1258        """
1259        Return a Groebner basis of this ideal.
1260
1261        INPUT:
1262            algorithm -- determines the algorithm to use, available are:
1263                         * None - autoselect (default)
1264                         * 'singular:groebner' - Singular's groebner command
1265                         * 'singular:std' - Singular's std command
1266                         * 'singular:stdhilb' - Singular's stdhib command
1267                         * 'singular:stdfglm' - Singular's stdfglm command
1268                         * 'singular:slimgb' - Singular's slimgb command
1269                         * 'libsingular:std' - libSINGULAR's std command
1270                         * 'libsingular:slimgb' - libSINGULAR's slimgb command
1271                         * 'toy:buchberger' - SAGE's toy/educational buchberger without strategy
1272                         * 'toy:buchberger2' - SAGE's toy/educational buchberger with strategy
1273                         * 'macaulay2:gb' (if available) - Macaulay2's gb command
1274                         * 'magma:GroebnerBasis' (if available) - MAGMA's Groebnerbasis command
1275
1276        EXAMPLES:
1277            Consider Katsura-3 over QQ with term ordering 'degrevlex'
1278
1279            sage: P.<a,b,c> = PolynomialRing(QQ,3, order='lex')
1280            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1281            sage: I.groebner_basis()
1282            [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]
1283
1284
1285            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1286            sage: I.groebner_basis('singular:groebner')
1287            [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]
1288
1289            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1290            sage: I.groebner_basis('singular:std')
1291            [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]
1292
1293            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1294            sage: I.groebner_basis('singular:stdhilb')
1295            [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]
1296
1297            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1298            sage: I.groebner_basis('singular:stdfglm')
1299            [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]
1300
1301            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1302            sage: I.groebner_basis('singular:slimgb')
1303            [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]
1304
1305            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1306            sage: I.groebner_basis('toy:buchberger')
1307            [-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,
1308            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]
1309           
1310            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1311            sage: I.groebner_basis('toy:buchberger2')
1312            [30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, a + 2*b + 2*c - 1,
1313             7/125*b + 42/25*c^3 - 79/125*c^2 + 3/125*c, a^2 - a + 2*b^2 + 2*c^2]
1314
1315            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1316            sage: I.groebner_basis('macaulay2:gb') # optional requires Macaulay2
1317            [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]
1318           
1319            sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
1320            sage: I.groebner_basis('magma:GroebnerBasis') # optional requires MAGMA
1321            [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]
1322
1323            If Macaulay2 is installed, Groebner bases over ZZ can be computed.
1324
1325            sage: P.<a,b,c> = PolynomialRing(ZZ,3)
1326            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)
1327            sage: I.groebner_basis() #optional requires Macaulay2
1328            [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,
1329             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,
1330             b^3 + b*c^2 + 12*c^3 + b^2 + b*c - 4*c^2]
1331
1332            SAGE also supports local orderings (via SINGULAR):
1333
1334            sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdegrevlex')
1335            sage: I = P * (  x*y*z + z^5, 2*x^2 + y^3 + z^7, 3*z^5 +y ^5 )
1336            sage: I.groebner_basis()
1337            [2*x^2 + y^3, x*y*z + z^5, y^5 + 3*z^5, y^4*z - 2*x*z^5, z^6]
1338
1339        ALGORITHM: Uses Singular, MAGMA (if available), Macaulay2 (if
1340        available), or toy implementation.
1341
1342        """
1343        if algorithm is None:
1344            if self.ring().base_ring() == sage.rings.integer_ring.ZZ:
1345                return self._macaulay2_groebner_basis()
1346            else:
1347                return self._groebner_basis_using_singular("groebner")
1348        elif algorithm.startswith('singular:'):
1349            return self._groebner_basis_using_singular(algorithm[9:])
1350        elif algorithm.startswith('libsingular:'):
1351            return self._groebner_basis_using_libsingular(algorithm[len('libsingular:'):])
1352        elif algorithm == 'macaulay2:gb':
1353            return self._macaulay2_groebner_basis()
1354        elif algorithm == 'magma:GroebnerBasis':
1355            return self._magma_groebner_basis()
1356        elif algorithm == 'toy:buchberger':
1357            return toy_buchberger.buchberger(self)
1358        elif algorithm == 'toy:buchberger2':
1359            return toy_buchberger.buchberger_improved(self)
1360        else:
1361            raise TypeError, "algorithm '%s' unknown"%algorithm
1362
1363
1364    def change_ring(self, P):
1365        r"""
1366        Return the ideal $I$ in $P$ spanned by the generators $g_1,
1367        ..., g_n$ of self as returned by self.gens().
1368
1369        INPUT:
1370            P -- a multivariate polynomial ring
1371
1372        EXAMPLE:
1373           sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex')
1374           sage: I = sage.rings.ideal.Cyclic(P)
1375           sage: I
1376           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
1377           sage: I.groebner_basis()
1378           [z^3 - 1, y^2 + y*z + z^2, x + y + z]
1379
1380           sage: Q.<x,y,z> = P.new_ring(order='degrevlex'); Q
1381           Multivariate Polynomial Ring in x, y, z over Rational Field
1382           sage: Q.term_order()
1383           Degree reverse lexicographic term order
1384
1385           sage: J = I.change_ring(Q); J
1386           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
1387           sage: J.groebner_basis()
1388           [x + y + z, y^2 + y*z + z^2, z^3 - 1]
1389        """
1390        return P.ideal([P(f) for f in self.gens()])
Note: See TracBrowser for help on using the repository browser.