source:sage/rings/multi_polynomial_ideal.py@4077:96ed94d32305

Revision 4077:96ed94d32305, 33.9 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

Martin's patch.

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