source: sage/rings/multi_polynomial_ideal.py @ 6:52eaa5430e09

Revision 6:52eaa5430e09, 18.0 KB checked in by Gonzalo Tornaria <tornaria@…>, 7 years ago (diff)

[project @ patch to sage-1.0.3]
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
9EXAMPLES:
10    sage: x,y,z = QQ['x,y,z'].gens()
11    sage: I = ideal(x^5 + y^4 + z^3 - 1,  x^3 + y^3 + z^2 - 1)
12    sage: B = I.groebner_basis()
13    sage: len(B)
14    8
15    sage: [f in I for f in I.gens()]
16    [True, True]
17
18    sage: f = I.gens()[0]
19    sage: I.reduce(f)
20    0
21
22    sage: g = I.gens()[1]
23    sage: I.reduce(g)
24    0
25
26    sage: I.reduce(g+x^2)
27    x^2
28   
29We compute a Groebner basis for cyclic 6, which is a standard
30benchmark and test ideal.
31   
32    sage: x,y,z,t,u,v = QQ['x,y,z,t,u,v'].gens()
33    sage: I = ideal(x + y + z + t + u + v, x*y + y*z + z*t + t*u + u*v + v*x, x*y*z + y*z*t + z*t*u + t*u*v + u*v*x + v*x*y, x*y*z*t + y*z*t*u + z*t*u*v + t*u*v*x + u*v*x*y + v*x*y*z, x*y*z*t*u + y*z*t*u*v + z*t*u*v*x + t*u*v*x*y + u*v*x*y*z + v*x*y*z*t, x*y*z*t*u*v - 1)
34    sage: B = I.groebner_basis()
35    sage: len(B)
36    17
37"""
38
39#*****************************************************************************
40#
41#   SAGE: System for Algebra and Geometry Experimentation   
42#
43#       Copyright (C) 2005 William Stein <wstein@ucsd.edu>
44#
45#  Distributed under the terms of the GNU General Public License (GPL)
46#
47#    This code is distributed in the hope that it will be useful,
48#    but WITHOUT ANY WARRANTY; without even the implied warranty of
49#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
50#    General Public License for more details.
51#
52#  The full text of the GPL is available at:
53#
54#                  http://www.gnu.org/licenses/
55#*****************************************************************************
56
57from ideal import Ideal_generic
58from sage.interfaces.all import singular as singular_default, is_SingularElement
59from sage.interfaces.all import macaulay2 as macaulay2_default
60from sage.interfaces.all import is_SingularElement
61singular = singular_default
62from integer import Integer
63from sage.structure.sequence import Sequence
64from sage.misc.sage_eval import sage_eval
65
66class MPolynomialIdeal(Ideal_generic):
67    """
68    An ideal of a multivariate polynomial ring.
69    """
70    def __init__(self, ring, gens, coerce=True):
71        """
72        Create an ideal in a multivariate polynomial ring.
73
74        EXAMPLES:
75            sage: R = PolynomialRing(IntegerRing(), 2, ['x','y']); x,y = R.gens()
76            sage: R.ideal([x, y])
77            Ideal (y, x) of Polynomial Ring in x, y over Integer Ring
78            sage: R = PolynomialRing(GF(3), 2); x = R.gens()
79            sage: R.ideal([x[0]**2, x[1]**3])
80            Ideal (x_1^3, x_0^2) of Polynomial Ring in x_0, x_1 over Finite Field of size 3
81        """
82        Ideal_generic.__init__(self, ring, gens, coerce=coerce)
83       
84class MPolynomialIdeal_singular_repr(MPolynomialIdeal):
85    """
86    An ideal in a multivariate polynomial ring, which has an underlying Singular
87    ring associated to it.
88   
89    EXAMPLES:
90    """
91    def __init__(self, ring, gens, coerce=True):
92        MPolynomialIdeal.__init__(self, ring, gens, coerce=coerce)
93
94    def _cmp_(self, other):
95        # Groebner basis determine equality since ideals are in the same ring with same term order
96        #c = cmp(self.gens(), other.gens())
97        #if c == 0:
98        #    return c
99        return cmp(self.groebner_basis(), other.groebner_basis())
100
101    def _singular_(self, singular=None):
102        """
103        Return Singular ideal corresponding to this ideal.
104
105        EXAMPLES:
106            sage: R, (x,y) = PolynomialRing(Q, 2, 'xy').objgens()
107            sage: I = R.ideal([x^3 + y, y])
108            sage: S = I._singular_()
109            sage: S
110            y,
111            x^3+y
112        """
113        if singular is None: singular = singular_default
114        try:
115            self.ring()._singular_(singular).set_ring()           
116            I = self.__singular
117            if not (I.parent() is singular):
118                raise ValueError
119            I._check_valid()
120            return I
121        except (AttributeError, ValueError):
122            self.ring()._singular_(singular).set_ring()
123            gens = [str(x) for x in self.gens()]
124            if len(gens) == 0:
125                gens = ['0']
126            self.__singular = singular.ideal(gens)
127        return self.__singular
128
129    def _contains_(self, f):
130        """
131        EXAMPLES:
132            sage: R, (x,y) = PolynomialRing(Q, 2, 'xy').objgens()
133            sage: I = (x^3 + y, y)*R
134            sage: x in I
135            False
136            sage: y in I
137            True
138            sage: x^3 + 2*y in I
139            True
140        """
141        S = singular_default
142        f = S(f)
143        I = self._singular_(S).std()
144        g = f.reduce(I, 1)  # 1 avoids tail reduction (page 67 of singular book)
145        return g.is_zero()
146       
147    def plot(self):
148        """
149        If you somehow manage to install surf, perhaps you can use
150        this function to implicitly plot the real zero locus of this
151        ideal (if principal).
152
153        INPUT:
154            self -- must be a principal ideal in 2 or 3 vars over QQ.
155
156        EXAMPLES:
157        Implicit plotting in 2-d:
158            sage: R, (x,y) = MPolynomialRing(QQ,2).objgens()
159            sage: I = R.ideal([y^3 - x^2])
160            sage.: I.plot()        # cusp         (optional surf)
161            sage: I = R.ideal([y^2 - x^2 - 1])
162            sage.: I.plot()        # hyperbola    (optional surf)
163            sage: I = R.ideal([y^2 + x^2*(1/4) - 1])
164            sage.: I.plot()        # ellipse      (optional surf)
165            sage: I = R.ideal([y^2-(x^2-1)*(x-2)])
166            sage.: I.plot()        # elliptic curve  (optional surf)
167
168        Implicit plotting in 3-d:
169            sage: R, (x,y,z) = MPolynomialRing(QQ,3).objgens()
170            sage: I = R.ideal([y^2 + x^2*(1/4) - z])
171            sage.: I.plot()          # a cone         (optional surf)
172            sage: I = R.ideal([y^2 + z^2*(1/4) - x])
173            sage.: I.plot()          # same code, from a different angle  (optional surf)
174            sage: I = R.ideal([x^2*y^2+x^2*z^2+y^2*z^2-16*x*y*z])
175            sage.: I.plot()          # Steiner surface   (optional surf)
176
177        AUTHOR:
178            -- David Joyner (2006-02-12)
179        """
180        if self.ring().characteristic() != 0:
181            raise TypeError, "base ring must have characteristic 0"
182        if not self.is_principal():
183            raise TypeError, "self must be principal"
184        singular.lib('surf')
185        I = singular(self)
186        I.plot()
187
188    def complete_primary_decomposition(self, algorithm="sy"):
189        r"""
190        INPUT:
191            algorithm -- string:
192                    'sy' -- (default) use the shimoyama-yokoyama algorithm
193                    'gtz' -- use the gianni-trager-zacharias algorithm
194        OUTPUT:
195            list -- a list of primary ideals and their associated
196                    primes
197                        [(primary ideal, associated prime), ...]
198
199        ALGORITHM: Uses Singular.
200
201        EXAMPLES:
202            sage: R, (x,y,z) = PolynomialRing(Q, 3, 'xyz').objgens()
203            sage: p = z^2 + 1; q = z^3 + 2
204            sage: I = (p*q^2, y-z^2)*R
205            sage: pd = I.complete_primary_decomposition(); pd
206            [(Ideal (1 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field,
207              Ideal (1 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field),
208             (Ideal (4 + 4*z^3 + z^6, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field,
209              Ideal (2 + z^3, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field)]
210            sage: I.complete_primary_decomposition(algorithm = 'gtz')
211            [(Ideal (-1*z^2 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field,
212              Ideal (-1*z^2 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field),
213             (Ideal (4 + 4*z^3 + z^6, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field,
214              Ideal (2 + z^3, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field)]
215        """
216        try:
217            return self.__complete_primary_decomposition[algorithm]
218        except AttributeError: 
219            self.__complete_primary_decomposition = {}
220        except KeyError:
221            pass
222        I = self._singular_()
223        I.parent().lib('primdec.lib')
224        if algorithm == 'sy':
225            P = I.primdecSY()
226        elif algorithm == 'gtz':
227            P = I.primdecGTZ()
228
229        R = self.ring()
230        V = [(R.ideal(X[1]), R.ideal(X[2])) for X in P]
231        V = Sequence(V)
232        self.__complete_primary_decomposition[algorithm] = V
233        return self.__complete_primary_decomposition[algorithm]
234
235    def primary_decomposition(self, algorithm='sy'):
236        """
237        EXAMPLES:
238            sage: R, (x,y,z) = PolynomialRing(Q, 3, 'xyz').objgens()
239            sage: p = z^2 + 1; q = z^3 + 2
240            sage: I = (p*q^2, y-z^2)*R
241            sage: I.primary_decomposition()
242            [Ideal (1 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field,
243            Ideal (4 + 4*z^3 + z^6, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field]
244        """
245        return [I for I, _ in self.complete_primary_decomposition(algorithm)]
246
247    def associated_primes(self, algorithm='sy'):
248        """
249        EXAMPLES:
250            sage: R, (x,y,z) = PolynomialRing(Q, 3, 'xyz').objgens()
251            sage: p = z^2 + 1; q = z^3 + 2
252            sage: I = (p*q^2, y-z^2)*R
253            sage: I.associated_primes()
254            [Ideal (1 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field,
255             Ideal (2 + z^3, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field]
256        """
257        return [P for _,P in self.complete_primary_decomposition(algorithm)]
258           
259    def dimension(self):
260        """
261        The dimension of the ring modulo this ideal.
262        """
263        try:
264            return self.__dimension
265        except AttributeError:
266            self.__dimension = Integer(self._singular_().std().dim())
267        return self.__dimension
268       
269    def groebner_basis(self):
270        """
271        Return a Groebner basis of this ideal.
272
273        ALGORITHM: Uses Singular.
274
275        EXAMPLES:
276
277        We compute a Groebner basis of "cyclic 4" relative to
278        lexicographic ordering.
279       
280            sage: R = PolynomialRing(RationalField(), 4, ['a','b','c','d'], 'lex')
281            sage: a,b,c,d = R.gens()
282            sage: I = R.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])
283            sage: I
284            Ideal (d + c + b + a, -1 + a*b*c*d, c*d + b*c + a*d + a*b, b*c*d + a*c*d + a*b*d + a*b*c) of Polynomial Ring in a, b, c, d over Rational Field
285            sage: I.groebner_basis()
286             [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]
287
288        \note{Some Groebner basis calculations crash on 64-bit
289        opterons with \SAGE's singular build, but work fine with an
290        official binary.  If you download and install a Singular
291        binary from the Singular website it will not have this problem
292        (you can use it with \SAGE by putting it in local/bin/).}
293        """
294        try:
295            return self.__groebner_basis
296        except AttributeError:
297            S = self._singular_().groebner()
298            R = self.ring()
299            self.__groebner_basis = Sequence([R(S[i+1]) for i in range(len(S))], R,
300                                             check=False, immutable=True)
301        return self.__groebner_basis
302   
303    def genus(self):
304        """
305        Return the genus of the projective curve defined by this
306        ideal, which must be 1 dimensional.
307        """
308        try:
309            return self.__genus
310        except AttributeError:
311            I = self._singular_()
312            I.parent().lib('normal.lib')
313            self.__genus = Integer(I.genus())
314            return self.__genus
315
316    def intersection(self, other):
317        """
318        Return the intersection of the two ideals.
319
320        EXAMPLES:
321            sage: R, (x,y) = PolynomialRing(Q, 2, 'xy').objgens()
322            sage: I = x*R
323            sage: J = y*R
324            sage: I.intersection(J)
325            Ideal (x*y) of Polynomial Ring in x, y over Rational Field
326
327        The following simple example illustrates that the product need not equal the intersection.
328            sage: I = (x^2, y)*R
329            sage: J = (y^2, x)*R
330            sage: K = I.intersection(J); K
331            Ideal (x^2, x*y, y^2) of Polynomial Ring in x, y over Rational Field
332            sage: IJ = I*J; IJ
333            Ideal (x^2*y^2, x^3, x*y, y^3) of Polynomial Ring in x, y over Rational Field
334            sage: IJ == K
335            False
336        """
337        R = self.ring()
338        if not isinstance(other, MPolynomialIdeal_singular_repr) or other.ring() != R:
339            raise ValueError, "other (=%s) must be an ideal in the ring %s"%(other, R)
340        I = self._singular_()
341        sing = I.parent()
342        J = sing(other)
343        K = I.intersect(J)
344        return R.ideal(K)
345
346
347    def minimal_associated_primes(self):
348        r"""
349        OUTPUT:
350            list -- a list of prime ideals
351
352        EXAMPLES:
353            sage: R, (x,y,z) = PolynomialRing(Q, 3, 'xyz').objgens()
354            sage: p = z^2 + 1; q = z^3 + 2
355            sage: I = (p*q^2, y-z^2)*R
356            sage: I.minimal_associated_primes ()
357            [Ideal (2 + z^3, -1*z^2 + y) of Polynomial Ring in x, y, z over Rational Field,
358             Ideal (-1*z^2 + y, 1 + z^2) of Polynomial Ring in x, y, z over Rational Field]
359
360        ALGORITHM: Uses Singular.
361        """
362        I = self._singular_()
363        I.parent().lib('primdec.lib')
364        M = I.minAssGTZ()
365        R = self.ring()
366        return [R.ideal(J) for J in M]
367
368    def radical(self):
369        r"""
370        The radical of this ideal.
371
372        EXAMPLES:
373        This is an obviously not radical ideal:
374            sage: R, (x,y,z) = PolynomialRing(QQ, 3, 'xyz').objgens()
375            sage: I = (x^2, y^3, (x*z)^4 + y^3 + 10*x^2)*R
376            sage: I.radical()
377            Ideal (y, x) of Polynomial Ring in x, y, z over Rational Field
378           
379        That the radical is correct is clear from the Groebner basis.
380            sage: I.groebner_basis()
381            [y^3, x^2]
382
383        This is the example from the singular manual:
384            sage: p = z^2 + 1; q = z^3 + 2
385            sage: I = (p*q^2, y-z^2)*R
386            sage: I.radical()
387            Ideal (-1*z^2 + y, 2 + 2*z^2 + z^3 + z^5) of Polynomial Ring in x, y, z over Rational Field
388
389        \note{(From Singular manual) A combination of the algorithms
390        of Krick/Logar and Kemper is used.  Works also in positive
391        characteristic (Kempers algorithm).}
392
393            sage: R,(x,y,z) = PolynomialRing(GF(37), 3, 'xyz').objgens()
394            sage: p = z^2 + 1; q = z^3 + 2
395            sage: I = (p*q^2, y - z^2)*R
396            sage: I.radical()
397            Ideal (36*z^2 + y, 2 + 2*z^2 + z^3 + z^5) of Polynomial Ring in x, y, z over Finite Field of size 37
398        """
399        S = self.ring()
400        I = self._singular_()
401        I.parent().lib('primdec.lib')       
402        r = I.radical()
403        return S.ideal(r)
404   
405    def reduce(self, f):
406        """
407        Reduce an element modulo a standard basis for this ideal.
408        This returns 0 if and only if the element is in this ideal.
409       
410        EXAMPLES:
411            sage: R, (x,y) = PolynomialRing(Q, 2, 'xy').objgens()
412            sage: I = (x^3 + y, y)*R
413            sage: I.reduce(y)
414            0
415            sage: I.reduce(x^3)
416            0
417            sage: I.reduce(x - y)
418            x
419
420            sage: I = (y^2 - (x^3 + x))*R
421            sage: I.reduce(x^3)
422            y^2 - x
423            sage: I.reduce(x^6)
424            y^4 - 2*x*y^2 + x^2
425            sage: (y^2 - x)^2
426            y^4 - 2*x*y^2 + x^2
427        """
428        try:
429            f = self.ring()(f)
430            S = singular_default
431            I = self._singular_(S)
432            g = S(f)
433            h = g.reduce(I.std())
434            return self.ring()(h)
435       
436        except TypeError:
437           
438            return f
439
440class MPolynomialIdeal_macaulay2_repr(MPolynomialIdeal):
441    """
442    An ideal in a multivariate polynomial ring, which has an underlying
443    Macaulay2 ring associated to it.
444   
445    EXAMPLES:
446        sage: x,y,z,w = PolynomialRing(ZZ, 4, 'xyzw', macaulay2=True).gens()
447        sage: I = ideal(x*y-z^2, y^2-w^2)
448        sage: I
449        Ideal (-1*w^2 + y^2, -1*z^2 + x*y) of Polynomial Ring in x, y, z, w over Integer Ring       
450    """
451    def __init__(self, ring, gens, coerce=True):
452        MPolynomialIdeal.__init__(self, ring, gens, coerce=coerce)
453
454    def _macaulay2_(self, macaulay2=None):
455        """
456        Return Macaulay2 ideal corresponding to this ideal.
457        """
458        if macaulay2 is None: macaulay2 = macaulay2_default
459        try:
460            self.ring()._macaulay2_(macaulay2)           
461            I = self.__macaulay2
462            if not (I.parent() is macaulay2):
463                raise ValueError
464            I._check_valid()
465            return I
466        except (AttributeError, ValueError):
467            self.ring()._macaulay2_(macaulay2)
468            gens = [str(x) for x in self.gens()]
469            if len(gens) == 0:
470                gens = ['0']
471            self.__macaulay2 = macaulay2.ideal(gens)
472        return self.__macaulay2
473
474    def groebner_basis(self):
475        """
476        Return the Groebner basis for this ideal.
477
478        ALGORITHM: Computed using Macaulay2.
479
480        EXAMPLE:
481            sage: x,y,z,w = PolynomialRing(ZZ, 4, 'xyzw', macaulay2=True).gens()
482            sage: I = ideal(x*y-z^2, y^2-w^2)
483            sage: I.groebner_basis()
484            [-1*w^2 + y^2, -1*z^2 + x*y, -1*y*z^2 + x*w^2]
485        """
486        try:
487            return self.__groebner_basis
488        except AttributeError:
489            I = self._macaulay2_()
490            G = str(I.gb().generators()).replace('\n','')
491            i = G.rfind('{{')
492            j = G.rfind('}}')
493            G = G[i+2:j].split(',')
494            L = self.ring().var_dict()
495            B = [sage_eval(f, L) for f in G]
496            B.sort()
497            self.__groebner_basis = B
498            return B
499           
500
Note: See TracBrowser for help on using the repository browser.