# source:sage/rings/multi_polynomial_ideal.py@2808:98cd79fcb738

Revision 2808:98cd79fcb738, 31.8 KB checked in by 'Martin Albrecht <malb@…, 6 years ago (diff)

bugfix: ideal membership over ZZ if M2 is installed
fixes #247

Line
1"""
2Ideals in multivariate polynomial rings.
3
4AUTHOR:
5    -- William Stein
6    -- Kiran S. Kedlaya (2006-02-12): added Macaulay2 analogues of
7              some Singular features
8    -- Martin Albrecht (2006-08-28): reorganized class hierarchy
9
10EXAMPLES:
11    sage: x,y,z = QQ['x,y,z'].gens()
12    sage: I = ideal(x^5 + y^4 + z^3 - 1,  x^3 + y^3 + z^2 - 1)
13    sage: B = I.groebner_basis()
14    sage: len(B)
15    3
16    sage: [f in I for f in I.gens()]
17    [True, True]
18
19    sage: f = I.gens()[0]
20    sage: I.reduce(f)
21    0
22
23    sage: g = I.gens()[1]
24    sage: I.reduce(g)
25    0
26
27    sage: I.reduce(g+x^2)
28    x^2
29
30We compute a Groebner basis for cyclic 6, which is a standard
31benchmark and test ideal.
32
33    sage: R.<x,y,z,t,u,v> = QQ['x,y,z,t,u,v']
34    sage: I = sage.rings.ideal.Cyclic(R,6)
35    sage: B = I.groebner_basis()
36    sage: len(B)
37    45
38
39We compute in a quotient of a polynomial ring over Z/17*Z:
40    sage: R.<x,y> = PolynomialRing(ZZ, 2)
41    sage: S.<a,b> = R.quotient((x^2 + y^2, 17))                 # optional -- requires Macaulay2
42    sage: S                                                     # optional
43    Quotient of Polynomial Ring in x, y over Integer Ring by the ideal (17, y^2 + x^2)
44    sage: a^2 + b^2 == 0                                        # optional
45    True
46    sage: a^3 - b^2                                             # optional
47    -1*b^2 - a*b^2
48    sage: (a+b)^17                                              # optional
49    b^17 + a*b^16
50    sage: S(17) == 0                                            # optional
51    True
52"""
53
54#*****************************************************************************
55#
56#   SAGE: System for Algebra and Geometry Experimentation
57#
58#       Copyright (C) 2005 William Stein <wstein@gmail.com>
59#
61#
62#    This code is distributed in the hope that it will be useful,
63#    but WITHOUT ANY WARRANTY; without even the implied warranty of
64#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
65#    General Public License for more details.
66#
67#  The full text of the GPL is available at:
68#
70#*****************************************************************************
71
72from ideal import Ideal_generic
73from sage.interfaces.all import singular as singular_default, is_SingularElement
74from sage.interfaces.all import macaulay2 as macaulay2_default
75from sage.interfaces.all import is_SingularElement
76singular = singular_default
77from integer import Integer
78from sage.structure.sequence import Sequence
79from sage.misc.sage_eval import sage_eval
80import sage.rings.integer_ring
81
82
83def is_MPolynomialIdeal(x):
84    return isinstance(x, MPolynomialIdeal)
85
86class MPolynomialIdeal_magma_repr:
87    def _magma_(self, magma=None):
88        """
89        Returns a MAGMA ideal matching self if the base ring coercable to MAGMA
90        and MAGMA is available.
91
92        EXAMPLES:
93            sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10)
94            sage: I = sage.rings.ideal.Cyclic(R,4)
95            sage: I._magma_() #optional MAGMA
96            Ideal of Polynomial ring of rank 10 over GF(127)
98            Variables: a, b, c, d, e, f, g, h, i, j
99            Basis:
100            [
101            a + b + c + d,
102            a*b + b*c + a*d + c*d,
103            a*b*c + a*b*d + a*c*d + b*c*d,
104            a*b*c*d + 126
105            ]
106        """
107        if magma == None:
108            import sage.interfaces.magma
109            magma = sage.interfaces.magma.magma
110        mlist = magma(self.gens())
111        return magma("ideal<%s|%s>"%(self.ring()._magma_().name(),mlist.name()))
112
113    def _magma_groebner_basis(self):
114        """
115        Computes a Groebner Basis for self using MAGMA if available.
116
117        EXAMPLES:
118            sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10)
119            sage: I = sage.rings.ideal.Cyclic(R,6)
120            sage: gb = I.groebner_basis("magma:GroebnerBasis") #optional MAGMA
121            sage: len(gb) #optional MAGMA
122            45
123        """
124        try:
125            return self.__magma_groebner_basis
126        except AttributeError:
127            pass
128        R = self.ring()
129        mgb = self._magma_().GroebnerBasis()
130        B = Sequence([R(str(mgb[i+1])) for i in range(len(mgb))], R,
131                        check=False, immutable=True)
132        self.__magma_groebner_basis = B
133        return B
134
135
136class MPolynomialIdeal_singular_repr:
137    """
138    An ideal in a multivariate polynomial ring, which has an
139    underlying Singular ring associated to it.
140    """
141    def __cmp__(self, other):
142        # Groebner basis determine equality since ideals are in the
143        # same ring with same term order
144
145        #c = cmp(self.gens(), other.gens())
146        #if c == 0:
147        #    return c
148        l = MPolynomialIdeal(self.ring(), self.groebner_basis()).reduced_basis()
149        r = MPolynomialIdeal(self.ring(),other.groebner_basis()).reduced_basis()
150        return cmp(r,l)
151
152    def _singular_(self, singular=None):
153        """
154        Return Singular ideal corresponding to this ideal.
155
156        EXAMPLES:
157            sage: R, (x,y) = PolynomialRing(QQ, 2, 'xy').objgens()
158            sage: I = R.ideal([x^3 + y, y])
159            sage: S = I._singular_()
160            sage: S
161            y,
162            x^3+y
163        """
164        if singular is None: singular = singular_default
165        try:
166            self.ring()._singular_(singular).set_ring()
167            I = self.__singular
168            if not (I.parent() is singular):
169                raise ValueError
170            I._check_valid()
171            return I
172        except (AttributeError, ValueError):
173            self.ring()._singular_(singular).set_ring()
174            gens = [str(x) for x in self.gens()]
175            if len(gens) == 0:
176                gens = ['0']
177            self.__singular = singular.ideal(gens)
178        return self.__singular
179
180    def _contains_(self, f):
181        """
182        EXAMPLES:
183            sage: R, (x,y) = PolynomialRing(QQ, 2, 'xy').objgens()
184            sage: I = (x^3 + y, y)*R
185            sage: x in I
186            False
187            sage: y in I
188            True
189            sage: x^3 + 2*y in I
190            True
191        """
192
193        if self.base_ring() == sage.rings.integer_ring.ZZ:
194            g = self._reduce_using_macaulay2(f)
195        else:
196            S = singular_default
197            f = S(f)
198            I = self._singular_(S).groebner()
199            g = f.reduce(I, 1)  # 1 avoids tail reduction (page 67 of singular book)
200        return g.is_zero()
201
202    def plot(self):
203        """
204        If you somehow manage to install surf, perhaps you can use
205        this function to implicitly plot the real zero locus of this
206        ideal (if principal).
207
208        INPUT:
209            self -- must be a principal ideal in 2 or 3 vars over QQ.
210
211        EXAMPLES:
212        Implicit plotting in 2-d:
213            sage: R.<x,y> = PolynomialRing(QQ,2)
214            sage: I = R.ideal([y^3 - x^2])
215            sage.: I.plot()        # cusp         (optional surf)
216            sage: I = R.ideal([y^2 - x^2 - 1])
217            sage.: I.plot()        # hyperbola    (optional surf)
218            sage: I = R.ideal([y^2 + x^2*(1/4) - 1])
219            sage.: I.plot()        # ellipse      (optional surf)
220            sage: I = R.ideal([y^2-(x^2-1)*(x-2)])
221            sage.: I.plot()        # elliptic curve  (optional surf)
222
223        Implicit plotting in 3-d:
224            sage: R.<x,y,z> = PolynomialRing(QQ,3)
225            sage: I = R.ideal([y^2 + x^2*(1/4) - z])
226            sage.: I.plot()          # a cone         (optional surf)
227            sage: I = R.ideal([y^2 + z^2*(1/4) - x])
228            sage.: I.plot()          # same code, from a different angle  (optional surf)
229            sage: I = R.ideal([x^2*y^2+x^2*z^2+y^2*z^2-16*x*y*z])
230            sage.: I.plot()          # Steiner surface   (optional surf)
231
232        AUTHOR:
233            -- David Joyner (2006-02-12)
234        """
235        if self.ring().characteristic() != 0:
236            raise TypeError, "base ring must have characteristic 0"
237        if not self.is_principal():
238            raise TypeError, "self must be principal"
239        singular.lib('surf')
240        I = singular(self)
241        I.plot()
242
243    def complete_primary_decomposition(self, algorithm="sy"):
244        r"""
245        INPUT:
246            algorithm -- string:
247                    'sy' -- (default) use the shimoyama-yokoyama algorithm
248                    'gtz' -- use the gianni-trager-zacharias algorithm
249        OUTPUT:
250            list -- a list of primary ideals and their associated
251                    primes
252                        [(primary ideal, associated prime), ...]
253
254        ALGORITHM: Uses Singular.
255
256        EXAMPLES:
257            sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
258            sage: p = z^2 + 1; q = z^3 + 2
259            sage: I = (p*q^2, y-z^2)*R
260            sage: pd = I.complete_primary_decomposition(); pd
261            [(Ideal (1 + z^2, 1 + y) of Polynomial Ring in x, y, z over Rational Field, Ideal (1 + z^2, 1 + y) of Polynomial Ring in x, y, z over Rational Field), (Ideal (4 + 4*z^3 + z^6, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field, Ideal (2 + z^3, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field)]
262
263            sage: I.complete_primary_decomposition(algorithm = 'gtz')
264            [(Ideal (1 + z^2, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field, Ideal (1 + z^2, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field), (Ideal (4 + 4*z^3 + z^6, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field, Ideal (2 + z^3, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field)]
265        """
266        try:
267            return self.__complete_primary_decomposition[algorithm]
268        except AttributeError:
269            self.__complete_primary_decomposition = {}
270        except KeyError:
271            pass
272        I = self._singular_()
273        I.parent().lib('primdec.lib')
274        if algorithm == 'sy':
275            P = I.primdecSY()
276        elif algorithm == 'gtz':
277            P = I.primdecGTZ()
278
279        R = self.ring()
280        V = [(R.ideal(X[1]), R.ideal(X[2])) for X in P]
281        V = Sequence(V)
282        self.__complete_primary_decomposition[algorithm] = V
283        return self.__complete_primary_decomposition[algorithm]
284
285    def primary_decomposition(self, algorithm='sy'):
286        """
287        EXAMPLES:
288            sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
289            sage: p = z^2 + 1; q = z^3 + 2
290            sage: I = (p*q^2, y-z^2)*R
291            sage: I.primary_decomposition()
292            [Ideal (1 + z^2, 1 + y) of Polynomial Ring in x, y, z over Rational Field, Ideal (4 + 4*z^3 + z^6, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field]
293
294        """
295        return [I for I, _ in self.complete_primary_decomposition(algorithm)]
296
297    def associated_primes(self, algorithm='sy'):
298        """
299        EXAMPLES:
300            sage: R.<x,y,z> = PolynomialRing(QQ, 3)
301            sage: p = z^2 + 1; q = z^3 + 2
302            sage: I = (p*q^2, y-z^2)*R
303            sage: I.associated_primes()
304            [Ideal (1 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field, Ideal (z^2 - y, 2 + y*z, 2*z + y^2) of Polynomial Ring in x, y, z over Rational Field]
305        """
306        return [P for _,P in self.complete_primary_decomposition(algorithm)]
307
308    def dimension(self):
309        """
310        The dimension of the ring modulo this ideal.
311        """
312        try:
313            return self.__dimension
314        except AttributeError:
315            v = list(self.groebner_basis())
316            if len(v) == 0:
317                v = [0]
318            self.__dimension = Integer(singular(v,"ideal").dim())
319        return self.__dimension
320
321    def _singular_groebner_basis(self, algorithm="groebner"):
322        """
323        Return a Groebner basis of this ideal. If a groebner basis for
324        this ideal has been calculated before the cached groebner
325        basis is returned regardless of the requested algorithm.
326
327        ALGORITHM: Uses Singular.
328
329        INPUT:
330            algorithm -- 'groebner' - use Singular's groebner heuristic to choose
331                                      an algorithm (default)
332                         'std'      - Buchberger's algorithm
333                         'stdhilb'  - computes the standard basis of the homogeneous
334                                      ideal in the basering, via a Hilbert driven
335                                      standard basis computation.
336                         'stdfglm'  - computes the standard basis of the ideal in the basering via fglm
337                                      (from the degrevlex ordering to the ordering of the basering).
338                         'slimgb'   - SlimGB algorithm
339
340        EXAMPLES:
341
342        We compute a Groebner basis of 'cyclic 4' relative to
343        lexicographic ordering.
344
345            sage: R.<a,b,c,d> = PolynomialRing(QQ, 4, order='lex')
346            sage: I = sage.rings.ideal.Cyclic(R,4); I
347            Ideal (d + c + b + a, c*d + b*c + a*d + a*b, b*c*d + a*c*d + a*b*d + a*b*c, -1 + a*b*c*d) of Polynomial Ring in a, b, c, d over Rational Field
348            sage: I.groebner_basis()
349            [1 - d^4 - c^2*d^2 + c^2*d^6, -1*d - c + c^2*d^3 + c^3*d^2, -1*d + d^5 - b + b*d^4, -1*d^2 - d^6 + c*d + c^2*d^4 - b*d^5 + b*c, d^2 + 2*b*d + b^2, d + c + b + a]
350
351        \note{Some Groebner basis calculations crash on 64-bit
352        opterons with \SAGE's singular build, but work fine with an
354        binary from the Singular website it will not have this problem
355        (you can use it with \SAGE by putting it in local/bin/).}
356        """
357        try:
358            return self.__groebner_basis
359        except AttributeError:
360            if algorithm=="groebner":
361                S = self._singular_().groebner()
362            elif algorithm=="std":
363                S = self._singular_().std()
364            elif algorithm=="slimgb":
365                S = self._singular_().slimgb()
366            elif algorithm=="stdhilb":
367                S = self._singular_().stdhilb()
368            elif algorithm=="stdfglm":
369                S = self._singular_().stdfglm()
370            else:
371                raise TypeError, "algorithm '%s' unknown"%algorithm
372            R = self.ring()
373            self.__singular_groebner_basis = S #remember this
374            self.__groebner_basis = Sequence([R(S[i+1]) for i in range(len(S))], R,
375                                             check=False, immutable=True)
376        return self.__groebner_basis
377
378    def genus(self):
379        """
380        Return the genus of the projective curve defined by this
381        ideal, which must be 1 dimensional.
382        """
383        try:
384            return self.__genus
385        except AttributeError:
386            I = self._singular_()
387            I.parent().lib('normal.lib')
388            self.__genus = Integer(I.genus())
389            return self.__genus
390
391    def intersection(self, other):
392        """
393        Return the intersection of the two ideals.
394
395        EXAMPLES:
396            sage: R.<x,y> = PolynomialRing(QQ, 2, order='lex')
397            sage: I = x*R
398            sage: J = y*R
399            sage: I.intersection(J)
400            Ideal (x*y) of Polynomial Ring in x, y over Rational Field
401
402        The following simple example illustrates that the product need not equal the intersection.
403            sage: I = (x^2, y)*R
404            sage: J = (y^2, x)*R
405            sage: K = I.intersection(J); K
406            Ideal (y^2, x*y, x^2) of Polynomial Ring in x, y over Rational Field
407            sage: IJ = I*J; IJ
408            Ideal (y^3, x*y, x^2*y^2, x^3) of Polynomial Ring in x, y over Rational Field
409            sage: IJ == K
410            False
411        """
412        R = self.ring()
413        if not isinstance(other, MPolynomialIdeal_singular_repr) or other.ring() != R:
414            raise ValueError, "other must be an ideal in the ring of self, but it isn't."
415        I = self._singular_()
416        sing = I.parent()
417        J = sing(other)
418        K = I.intersect(J)
419        return R.ideal(K)
420
421
422    def minimal_associated_primes(self):
423        r"""
424        OUTPUT:
425            list -- a list of prime ideals
426
427        EXAMPLES:
428            sage: R.<x,y,z> = PolynomialRing(QQ, 3, 'xyz')
429            sage: p = z^2 + 1; q = z^3 + 2
430            sage: I = (p*q^2, y-z^2)*R
431            sage: I.minimal_associated_primes ()
432            [Ideal (-1*z^2 + y, 2 + z^3) of Polynomial Ring in x, y, z over Rational Field, Ideal (-1*z^2 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field]
433
434        ALGORITHM: Uses Singular.
435        """
436        I = self._singular_()
437        I.parent().lib('primdec.lib')
438        M = I.minAssGTZ()
439        R = self.ring()
440        return [R.ideal(J) for J in M]
441
443        r"""
444        The radical of this ideal.
445
446        EXAMPLES:
447        This is an obviously not radical ideal:
448            sage: R.<x,y,z> = PolynomialRing(QQ, 3)
449            sage: I = (x^2, y^3, (x*z)^4 + y^3 + 10*x^2)*R
451            Ideal (y, x) of Polynomial Ring in x, y, z over Rational Field
452
453        That the radical is correct is clear from the Groebner basis.
454            sage: I.groebner_basis()
455            [x^2, y^3]
456
457        This is the example from the singular manual:
458            sage: p = z^2 + 1; q = z^3 + 2
459            sage: I = (p*q^2, y-z^2)*R
461            Ideal (z^2 - y, 2 + 2*y + y*z + y^2*z) of Polynomial Ring in x, y, z over Rational Field
462
463        \note{(From Singular manual) A combination of the algorithms
464        of Krick/Logar and Kemper is used.  Works also in positive
465        characteristic (Kempers algorithm).}
466
467            sage: R.<x,y,z> = PolynomialRing(GF(37), 3)
468            sage: p = z^2 + 1; q = z^3 + 2
469            sage: I = (p*q^2, y - z^2)*R
471            Ideal (z^2 + 36*y, 2 + 2*y + y*z + y^2*z) of Polynomial Ring in x, y, z over Finite Field of size 37
472        """
473        S = self.ring()
474        I = self._singular_()
475        I.parent().lib('primdec.lib')
477        return S.ideal(r)
478
479    def reduce(self, f):
480        """
481        Reduce an element modulo a standard basis for this ideal.
482        This returns 0 if and only if the element is in this ideal.
483
484        EXAMPLES:
485            sage: R.<x,y> = PolynomialRing(QQ, 2)
486            sage: I = (x^3 + y, y)*R
487            sage: I.reduce(y)
488            0
489            sage: I.reduce(x^3)
490            0
491            sage: I.reduce(x - y)
492            x
493
494            sage: I = (y^2 - (x^3 + x))*R
495            sage: I.reduce(x^3)
496            y^2 - x
497            sage: I.reduce(x^6)
498            y^4 - 2*x*y^2 + x^2
499            sage: (y^2 - x)^2
500            y^4 - 2*x*y^2 + x^2
501        """
502        if self.base_ring() == sage.rings.integer_ring.ZZ:
503            return self._reduce_using_macaulay2(f)
504
505        try:
506            singular = self.__singular_groebner_basis.parent()
507        except AttributeError:
508            self.groebner_basis()
509            singular = self.__singular_groebner_basis.parent()
510
511        f = self.ring()(f)
512        g = singular(f)
513        try:
514            h = g.reduce(self.__singular_groebner_basis)
515        except TypeError:
516            # This is OK, since f is in the right ring -- type error
517            # just means it's a rational
518            return f
519        return self.ring()(h)
520
521
522    def syzygy_module(self):
523        r"""
524        Computes the first syzygy (i.e., the module of relations of
525        the given generators) of the ideal.
526
527        ALGORITHM: Uses Singular's syz command
528
529        \note{The syz module is transposed before being returned}
530        """
531        return self._singular_().syz().transpose().sage_matrix(self.ring())
532
533    def reduced_basis(self):
534        r"""
535        returns $(g_1, \dots, g_s)$ such that:
536
537        * $(f_1,\dots,f_n) = (g_1,\dots,g_s)$
538        * $L(g_i)\neq L(g_j)$ for all $i\neq j$
539        * $L(g_i)$ does not divide m for all monomials m of
540          $\{g_1,\dots,g_{i-1},g_{i+1},\dots,g_s\}$
541
542        ALGORITHM: Uses Singular's interred command
543
544        \note{G. Pfister recommended setting option(redSB) before
545        using interred for this purpose. Though the manual doesn't
546        mention it.}
547        """
548        s = self._singular_().parent()
549        o = s.option("get")
550        s.option("redSB")
551        R = self.ring()
552        ret = Sequence([ R(f) for f in self._singular_().interred() ], R,
553                       check=False, immutable=True)
554        s.option("set",o)
555        return ret
556
557    def basis_is_groebner(self):
558        """
559        Returns true if self.gens() form a Groebner Basis. This is done by
560        trying to lift Syz(LM(self)) to Syz(self) as self is a Groebner
561        Basis if and only if for every element S in Syz(LM(self)):
562        $$S \cdot G = \sum_{i=0}^{m} h_ig_i \rightarrow_G 0.$$.
563
564        ALGORITHM: Uses Singular
565
566        EXAMPLE:
567            sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10)
568            sage: I = sage.rings.ideal.Cyclic(R,4)
569            sage: I.basis_is_groebner()
570            False
571            sage: I2 = Ideal(I.groebner_basis())
572            sage: I2.basis_is_groebner()
573            True
574
575        \note{From the Singular Manualf for the reduce function we use in
576        this method: 'The result may have no meaning if the second
577        argument (self, malb) is not a standard basis'. I (malb) believe
578        this refers to the mathematical fact that the results may have no
579        meaning if self is no standard basis, i.e., Singular doesn't 'add'
580        any additional 'nonsense' to the result. So we may acutally use
581        reduce to determine if self is a Groebner Basis.}
582        """
583        from sage.matrix.constructor import matrix
584        singular = self._singular_().parent()
585        R = self.ring()
586
587        F = singular( self.gens(), "module" )
588        LTF = singular( [f.lt() for f in self.gens()] , "module" )
589
590        M = (F * LTF.syz()).reduce(self._singular_())
591
592        for i in range(M.nrows()):
593            if int(singular.eval("%s[1][%s+1]!=0"%(M.name(),i))):
594                return False
595        return True
596
597    def transformed_basis(self,algorithm="gwalk", other_ring=None):
598        """
599        Returns a lex or other_ring Groebner Basis for a given ideal
600        self which must be represented through a Groebner Basis.
601
602        INPUT:
603           algorithm -- Options are:
604                        * fglm - FGLM algorithm. The input ideal must be
605                                 a reduced Groebner Basis of a zero-dimensional ideal
606                        * gwalk (default) - Groebner Walk algorithm
607                        * awalk1 - 'first alternative' algorithm
608                        * awalk2 - 'second alternative' algorithm
609                        * twalk  - Tran algorithm
610                        * fwalk  - Fractal Walk algorithm
611           other_ring  -- only valid for algorithm 'fglm', if provided conversion will
612                          be performed to this ring. Otherwise a lex Groebner basis will
613                          be returned.
614        EXAMPLES:
615           sage: # example from the Singular manual page of fglm
616           sage: R.<x,y,z> = PolynomialRing(QQ,3)
617           sage: I = Ideal([y^3+x^2,x^2*y+x^2, x^3-x^2, z^4-x^2-y])
618           sage: singular.option('redSB')
619           sage: I = Ideal(I.groebner_basis())
620           sage: singular.option('noredSB') #reset
621           sage: S.<z,x,y> = PolynomialRing(QQ,3,order='lex')
622           sage: J = Ideal(I.transformed_basis('fglm',S))
623           sage: J
624           Ideal (y^3 + y^4, -1*y^3 + x*y^3, y^3 + x^2, -1*y + y^3 + z^4) of Polynomial Ring in z, x, y over Rational Field
625           sage: # example from the Singular manual page of gwalk
626           sage: R.<z,y,x>=PolynomialRing(GF(32003),3,order='lex')
627           sage: I=Ideal([y^3+x*y*z+y^2*z+x*z^3,3+x*y+x^2*y+y^2*z])
628           sage: I.transformed_basis('gwalk')
629           [31976*x + 31976*y*x^2 + 31976*y*x^3 + 31994*y^2*x^3 + 31985*y^2*x^4 + 31994*y^2*x^5 + 32002*y^3*x^4 + 32000*y^3*x^5 + 32000*y^3*x^6 + 32002*y^3*x^7 + 32000*y^5*x + 32000*y^6 + 32002*y^6*x^2 + 32002*y^6*x^3 + 32002*y^7*x + 32002*y^7*x^2 + y^9,
630           x^3 + 2*x^4 + x^5 + 17780*y*x^4 + 21337*y*x^5 + 21337*y*x^6 + 17780*y*x^7 + 23706*y^2*x^5 + 30818*y^2*x^6 + 14224*y^2*x^7 + 30818*y^2*x^8 + 23706*y^2*x^9 + 21335*y^3*x + 21335*y^4 + 3556*y^4*x^2 + 3556*y^4*x^3 + 3556*y^5*x + 3556*y^5*x^2 + 23706*y^5*x^3 + 15409*y^5*x^4 + 23706*y^5*x^5 + 23706*y^6*x^2 + 15409*y^6*x^3 + 23706*y^6*x^4 + 3556*y^7 + 8297*y^8*x + 8297*y^8*x^2 + z*x,
631           3 + y*x + y*x^2 + z*y^2]
632
633
634        ALGORITHM: Uses Singular
635        """
636        from sage.rings.multi_polynomial_ring import TermOrder,MPolynomialRing
637        from sage.rings.quotient_ring import is_QuotientRing
638
639        Is = self._singular_()
640        R = self.ring()
641
642        if algorithm in ("gwalk","awalk1","awalk2","twalk","fwalk"):
643            singular.LIB("grwalk")
644            gb = singular("%s(%s)"%(algorithm,Is.name()))
645            return [R(f) for f in gb]
646        elif algorithm == "fglm":
647            Rs = self.ring()._singular_()
648
649            # new ring
650            if other_ring==None:
651                nR = MPolynomialRing(R.base_ring(),R.ngens(), names=R.variable_names(), order="lex")
652            else:
653                nR = other_ring
654            nR._singular_().set_ring()
655
656            nIs = singular.fglm(Rs,Is)
657
658            return [nR(f) for f in nIs]
659
660        else:
661            raise TypeError, "Cannot convert basis with given algorithm"
662
663
664class MPolynomialIdeal_macaulay2_repr:
665    """
666    An ideal in a multivariate polynomial ring, which has an underlying
667    Macaulay2 ring associated to it.
668
669    EXAMPLES:
670        sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4) # optional
671        sage: I = ideal(x*y-z^2, y^2-w^2)       # optional
672        sage: I                                 # optional
673        Ideal (-1*w^2 + y^2, -1*z^2 + x*y) of Polynomial Ring in x, y, z, w over Integer Ring
674    """
675    #def __init__(self, ring, gens, coerce=True):
676    #    MPolynomialIdeal.__init__(self, ring, gens, coerce=coerce)
677
678    def _macaulay2_(self, macaulay2=None):
679        """
680        Return Macaulay2 ideal corresponding to this ideal.
681        """
682        if macaulay2 is None: macaulay2 = macaulay2_default
683        try:
684            self.ring()._macaulay2_(macaulay2)
685            I = self.__macaulay2
686            if not (I.parent() is macaulay2):
687                raise ValueError
688            I._check_valid()
689            return I
690        except (AttributeError, ValueError):
691            self.ring()._macaulay2_(macaulay2)
692            gens = [str(x) for x in self.gens()]
693            if len(gens) == 0:
694                gens = ['0']
695            self.__macaulay2 = macaulay2.ideal(gens)
696        return self.__macaulay2
697
698    def _macaulay2_groebner_basis(self):
699        r"""
700        Return the Groebner basis for this ideal, computed using Macaulay2.
701
702        ALGORITHM: Computed using Macaulay2.  A big advantage of
703        Macaulay2 is that it can compute Groebner basis of ideals in
704        polynomial rings over the integers.
705
706        EXAMPLE:
707            sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
708            sage: I = ideal(x*y-z^2, y^2-w^2)
709            sage: I.groebner_basis()                                     # optional -- requires macaulay2
710            [-1*w^2 + y^2, -1*z^2 + x*y, y*z^2 - x*w^2, z^4 - x^2*w^2]
711
712        Groebner basis can be used to compute in $\Z/n\Z[x,\ldots]$.
713
714            sage: R.<x,y,z> = ZZ[]
715            sage: I = ideal([y^2*z - x^3 - 19*x*z, y^2, 19^2])
716            sage: I.groebner_basis()                                     # optional -- requires macaulay2
717            [361, y^2, 19*x*z + x^3]
718            sage: I = ideal([y^2*z - x^3 - 19^2*x*z, y^2, 19^2])
719            sage: I.groebner_basis()                                     # optional -- requires macaulay2
720            [361, y^2, x^3]
721        """
722        try:
723            return self.__groebner_basis
724        except AttributeError:
725            I = self._macaulay2_()
726            G = str(I.gb().generators().str()).replace('\n','')
727            i = G.rfind('{{')
728            j = G.rfind('}}')
729            G = G[i+2:j].split(',')
730            L = self.ring().var_dict()
731            B = [sage_eval(f, L) for f in G]
732            B = Sequence(B, self.ring(), check=False, immutable=True)
733            B.sort()
734            self.__groebner_basis = B
735            return B
736
737    def _reduce_using_macaulay2(self, f):
738        I = self._macaulay2_()
739        M2 = I.parent()
740        R = self.ring()
741        g = M2(R(f))
742        try:
743            k = M2('%s %% %s'%(g.name(), I.name()))
744        except TypeError:
745            # This is OK, since f is in the right ring -- type error
746            # just means it's in base ring (e.g., a constant)
747            return f
748        return R(k)
749
750
751class MPolynomialIdeal( MPolynomialIdeal_singular_repr, \
752                        MPolynomialIdeal_macaulay2_repr, \
753                        MPolynomialIdeal_magma_repr, \
754                        Ideal_generic ):
755    """
756    An ideal of a multivariate polynomial ring.
757    """
758    def __init__(self, ring, gens, coerce=True):
759        """
760        Create an ideal in a multivariate polynomial ring.
761
762        EXAMPLES:
763            sage: R.<x,y> = PolynomialRing(IntegerRing(), 2, order='lex')
764            sage: R.ideal([x, y])
765            Ideal (y, x) of Polynomial Ring in x, y over Integer Ring
766            sage: R.<x0,x1> = GF(3)[]
767            sage: R.ideal([x0^2, x1^3])
768            Ideal (x0^2, x1^3) of Polynomial Ring in x0, x1 over Finite Field of size 3
769        """
770        Ideal_generic.__init__(self, ring, gens, coerce=coerce)
771
772    def groebner_fan(self, is_groebner_basis=False, symmetry=None, verbose=False):
773        r"""
774        Return the Groebner fan of this ideal.
775
776        The base ring must be $\Q$ or a finite field $\F_p$ of with
777        $p \leq 32749$.
778
779        INPUT:
780            is_groebner_basis -- bool (default False).  if True, then I.gens() must be
781                                 a Groebner basis with respect to the standard
782                                 degree lexicographic term order.
783            symmetry -- default: None; if not None, describes symmetries of the ideal
784            verbose -- default: False; if True, printout useful info during computations
785        """
786        import groebner_fan
787        return groebner_fan.GroebnerFan(self, is_groebner_basis=is_groebner_basis,
788                                        symmetry=symmetry, verbose=verbose)
789
790    def groebner_basis(self, algorithm=None):
791        """
792        Return a Groebner basis of this ideal.
793
794        INPUT:
795            algorithm -- determines the algorithm to use, available are:
796                         * None - autoselect (default)
797                         * 'singular:groebner' - Singular's groebner command
798                         * 'singular:std' - Singular's std command
799                         * 'singular:stdhilb' - Singular's stdhib command
800                         * 'singular:stdfglm' - Singular's stdfglm command
801                         * 'singular:slimgb' - Singular's slimgb command
802                         * 'macaulay2:gb' (if available) - Macaulay2's gb command
803                         * 'magma:GroebnerBasis' (if available) - MAGMA's Groebnerbasis command
804
805        ALGORITHM: Uses Singular, MAGMA, or Macaulay2 (if available)
806
807        """
808        if algorithm is None:
809            if self.ring().base_ring() == sage.rings.integer_ring.ZZ:
810                return self._macaulay2_groebner_basis()
811            else:
812                return self._singular_groebner_basis("groebner")
813        elif algorithm.startswith('singular:'):
814            return self._singular_groebner_basis(algorithm[9:])
815        elif algorithm == 'macaulay2:gb':
816            return self._macaulay2_groebner_basis()
817        elif algorithm == 'magma:GroebnerBasis':
818            return self._magma_groebner_basis()
819        else:
820            raise TypeError, "algorithm '%s' unknown"%algorithm
Note: See TracBrowser for help on using the repository browser.