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

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

wrapped getting/setting singular attributes

Line
1"""
2Ideals in multivariate polynomial rings.
3
4Most functionality of multivariate polynomial ideals in SAGE is
5provided through SINGULAR.
6
7AUTHOR:
8    -- William Stein
9    -- Kiran S. Kedlaya (2006-02-12): added Macaulay2 analogues of
10              some Singular features
11    -- Martin Albrecht
12
13EXAMPLES:
14    sage: x,y,z = QQ['x,y,z'].gens()
15    sage: I = ideal(x^5 + y^4 + z^3 - 1,  x^3 + y^3 + z^2 - 1)
16    sage: B = I.groebner_basis()
17    sage: len(B)
18    3
19    sage: [f in I for f in I.gens()]
20    [True, True]
21
22    sage: f = I.gens()[0]
23    sage: I.reduce(f)
24    0
25
26    sage: g = I.gens()[1]
27    sage: I.reduce(g)
28    0
29
30    sage: I.reduce(g+x^2)
31    x^2
32
33We compute a Groebner basis for cyclic 6, which is a standard
34benchmark and test ideal.
35
36    sage: R.<x,y,z,t,u,v> = QQ['x,y,z,t,u,v']
37    sage: I = sage.rings.ideal.Cyclic(R,6)
38    sage: B = I.groebner_basis()
39    sage: len(B)
40    45
41
42We compute in a quotient of a polynomial ring over Z/17*Z:
43    sage: R.<x,y> = ZZ[]
44    sage: S.<a,b> = R.quotient((x^2 + y^2, 17))                 # optional -- requires Macaulay2
45    sage: S                                                     # optional
46    Quotient of Multivariate Polynomial Ring in x, y over Integer Ring by the ideal (x^2 + y^2, 17)
47    sage: a^2 + b^2 == 0                                        # optional
48    True
49    sage: a^3 - b^2                                             # optional
50    -1*a*b^2 - b^2
51    sage: (a+b)^17                                              # optional
52    a*b^16 + b^17
53    sage: S(17) == 0                                            # optional
54    True
55
56Working with a polynomial ring over ZZ:
57    sage: R.<x,y,z,w> = ZZ['x,y,z,w']
58    sage: i = ideal(x^2 + y^2 - z^2 - w^2, x-y)
59    sage: j = i^2
60    sage: j.groebner_basis()                                    # optional
61    [x^2 - 2*x*y + y^2, 2*x*y^2 - 2*y^3 - x*z^2 + y*z^2 - x*w^2 + y*w^2, 4*y^4 - 4*y^2*z^2 + z^4 - 4*y^2*w^2 + 2*z^2*w^2 + w^4]
62    sage: y^2 - 2*x*y + x^2 in j                                # optional
63    True
64    sage: 0 in j                                                # optional
65    True
66
67We do a Groebner basis computation over a number field:
68    sage: K.<zeta> = CyclotomicField(3)
69    sage: R.<x,y,z> = K[]; R
70    Multivariate Polynomial Ring in x, y, z over Cyclotomic Field of order 3 and degree 2
71    sage: i = ideal(x - zeta*y + 1, x^3 - zeta*y^3); i
72    Ideal (x + (-zeta)*y + 1, x^3 + (-zeta)*y^3) of Multivariate Polynomial Ring in x, y, z over Cyclotomic Field of order 3 and degree 2
73    sage: i.groebner_basis()
74    [x + (-zeta)*y + 1, 3*y^3 + (6*zeta + 3)*y^2 + (3*zeta - 3)*y - zeta - 2]
75    sage: S = R.quotient(i); S
76    Quotient of Multivariate Polynomial Ring in x, y, z over Cyclotomic Field of order 3 and degree 2 by the ideal (x + (-zeta)*y + 1, x^3 + (-zeta)*y^3)
77    sage: S.0  - zeta*S.1
78    -1
79    sage: S.0^3 - zeta*S.1^3
80    0
81
82Two examples from the Mathematica documentation (done in SAGE):
83    We compute a Groebner basis:
84        sage: R.<x,y> = PolynomialRing(QQ, order='lex')
85        sage: ideal(x^2 - 2*y^2, x*y - 3).groebner_basis()
86        [2*y^4 - 9, 3*x - 2*y^3]
87
88    We show that three polynomials have no common root:
89        sage: R.<x,y> = QQ[]
90        sage: ideal(x+y, x^2 - 1, y^2 - 2*x).groebner_basis()
91        [1]
92
93TESTS:
94    sage: x,y,z = QQ['x,y,z'].gens()
95    sage: I = ideal(x^5 + y^4 + z^3 - 1,  x^3 + y^3 + z^2 - 1)
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#
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#
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)
146            Variables: a, b, c, d, e, f, g, h, i, j
147            Basis:
148            [
149            a + b + c + d,
150            a*b + b*c + a*d + c*d,
151            a*b*c + a*b*d + a*c*d + b*c*d,
152            a*b*c*d + 126
153            ]
154        """
155        if magma == None:
156            import sage.interfaces.magma
157            magma = sage.interfaces.magma.magma
158        return magma.ideal(self.gens())
159
160    def _magma_groebner_basis(self):
161        """
162        Computes a Groebner Basis for self using MAGMA if available.
163
164        EXAMPLES:
165            sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10)
166            sage: I = sage.rings.ideal.Cyclic(R,6)
167            sage: gb = I.groebner_basis("magma:GroebnerBasis") #optional MAGMA
168            sage: len(gb) #optional MAGMA
169            45
170        """
171        try:
172            return self.__magma_groebner_basis
173        except AttributeError:
174            pass
175        R = self.ring()
176        mgb = self._magma_().GroebnerBasis()
177        mgb = [str(mgb[i+1]) for i in range(len(mgb))]
178        if R.base_ring().degree() > 1:
179            a = str(R.base_ring().gen())
180            mgb = [e.replace("$.1",a) for e in mgb] 181 B = Sequence([R(e) for e in mgb], R, check=False, immutable=True) 182 self.__magma_groebner_basis = B 183 return B 184 185 186class MPolynomialIdeal_singular_repr: 187 """ 188 An ideal in a multivariate polynomial ring, which has an 189 underlying Singular ring associated to it. 190 """ 191 def __cmp__(self, other): 192 # Groebner basis determine equality since ideals are in the 193 # same ring with same term order 194 195 #c = cmp(self.gens(), other.gens()) 196 #if c == 0: 197 # return c 198 l = MPolynomialIdeal(self.ring(), self.groebner_basis()).reduced_basis() 199 r = MPolynomialIdeal(self.ring(),other.groebner_basis()).reduced_basis() 200 return cmp(r,l) 201 202 def _singular_(self, singular=None): 203 """ 204 Return Singular ideal corresponding to this ideal. 205 206 EXAMPLES: 207 sage: R, (x,y) = PolynomialRing(QQ, 2, 'xy').objgens() 208 sage: I = R.ideal([x^3 + y, y]) 209 sage: S = I._singular_() 210 sage: S 211 x^3+y, 212 y 213 """ 214 if singular is None: singular = singular_default 215 try: 216 self.ring()._singular_(singular).set_ring() 217 I = self.__singular 218 if not (I.parent() is singular): 219 raise ValueError 220 I._check_valid() 221 return I 222 except (AttributeError, ValueError): 223 self.ring()._singular_(singular).set_ring() 224 gens = [str(x) for x in self.gens()] 225 if len(gens) == 0: 226 gens = ['0'] 227 self.__singular = singular.ideal(gens) 228 return self.__singular 229 230 def _contains_(self, f): 231 """ 232 Returns True if f is in the ideal self. 233 234 EXAMPLES: 235 sage: R, (x,y) = PolynomialRing(QQ, 2, 'xy').objgens() 236 sage: I = (x^3 + y, y)*R 237 sage: x in I 238 False 239 sage: y in I 240 True 241 sage: x^3 + 2*y in I 242 True 243 244 NOTE: Requires computation of a Groebner basis, which is a 245 very expensive operation. 246 """ 247 248 if self.base_ring() == sage.rings.integer_ring.ZZ: 249 g = self._reduce_using_macaulay2(f) 250 else: 251 S = singular_default 252 f = S(f) 253 I = self._singular_(S).groebner() 254 g = f.reduce(I, 1) # 1 avoids tail reduction (page 67 of singular book) 255 return g.is_zero() 256 257 def plot(self): 258 """ 259 If you somehow manage to install surf, perhaps you can use 260 this function to implicitly plot the real zero locus of this 261 ideal (if principal). 262 263 INPUT: 264 self -- must be a principal ideal in 2 or 3 vars over QQ. 265 266 EXAMPLES: 267 Implicit plotting in 2-d: 268 sage: R.<x,y> = PolynomialRing(QQ,2) 269 sage: I = R.ideal([y^3 - x^2]) 270 sage: I.plot() # cusp (optional surf) 271 sage: I = R.ideal([y^2 - x^2 - 1]) 272 sage: I.plot() # hyperbola (optional surf) 273 sage: I = R.ideal([y^2 + x^2*(1/4) - 1]) 274 sage: I.plot() # ellipse (optional surf) 275 sage: I = R.ideal([y^2-(x^2-1)*(x-2)]) 276 sage: I.plot() # elliptic curve (optional surf) 277 278 Implicit plotting in 3-d: 279 sage: R.<x,y,z> = PolynomialRing(QQ,3) 280 sage: I = R.ideal([y^2 + x^2*(1/4) - z]) 281 sage: I.plot() # a cone (optional surf) 282 sage: I = R.ideal([y^2 + z^2*(1/4) - x]) 283 sage: I.plot() # same code, from a different angle (optional surf) 284 sage: I = R.ideal([x^2*y^2+x^2*z^2+y^2*z^2-16*x*y*z]) 285 sage: I.plot() # Steiner surface (optional surf) 286 287 AUTHOR: 288 -- David Joyner (2006-02-12) 289 """ 290 if self.ring().characteristic() != 0: 291 raise TypeError, "base ring must have characteristic 0" 292 if not self.is_principal(): 293 raise TypeError, "self must be principal" 294 singular.lib('surf') 295 I = singular(self) 296 I.plot() 297 298 def complete_primary_decomposition(self, algorithm="sy"): 299 r""" 300 INPUT: 301 algorithm -- string: 302 'sy' -- (default) use the shimoyama-yokoyama algorithm 303 'gtz' -- use the gianni-trager-zacharias algorithm 304 OUTPUT: 305 list -- a list of primary ideals and their associated 306 primes 307 [(primary ideal, associated prime), ...] 308 309 ALGORITHM: Uses Singular. 310 311 EXAMPLES: 312 sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex') 313 sage: p = z^2 + 1; q = z^3 + 2 314 sage: I = (p*q^2, y-z^2)*R 315 sage: pd = I.complete_primary_decomposition(); pd 316 [(Ideal (z^6 + 4*z^3 + 4, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^3 + 2, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field), (Ideal (z^2 + 1, y + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^2 + 1, y + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field)] 317 318 sage: I.complete_primary_decomposition(algorithm = 'gtz') 319 [(Ideal (z^6 + 4*z^3 + 4, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^3 + 2, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field), (Ideal (z^2 + 1, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^2 + 1, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field)] 320 """ 321 try: 322 return self.__complete_primary_decomposition[algorithm] 323 except AttributeError: 324 self.__complete_primary_decomposition = {} 325 except KeyError: 326 pass 327 I = self._singular_() 328 I.parent().lib('primdec.lib') 329 if algorithm == 'sy': 330 P = I.primdecSY() 331 elif algorithm == 'gtz': 332 P = I.primdecGTZ() 333 334 R = self.ring() 335 V = [(R.ideal(X[1]), R.ideal(X[2])) for X in P] 336 V = Sequence(V) 337 self.__complete_primary_decomposition[algorithm] = V 338 return self.__complete_primary_decomposition[algorithm] 339 340 def primary_decomposition(self, algorithm='sy'): 341 """ 342 EXAMPLES: 343 sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex') 344 sage: p = z^2 + 1; q = z^3 + 2 345 sage: I = (p*q^2, y-z^2)*R 346 sage: I.primary_decomposition() 347 [Ideal (z^6 + 4*z^3 + 4, y - z^2) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^2 + 1, y + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field] 348 349 """ 350 return [I for I, _ in self.complete_primary_decomposition(algorithm)] 351 352 def triangular_decomposition(self, algorithm=None): 353 """ 354 Decompose zero-dimensional ideal self into triangular sets. 355 356 This requires that the given basis is reduced w.r.t. to the lexicographical 357 monomial ordering. If the basis of self does not have this property, the 358 required Groebner basis is computed implicitly. 359 360 INPUT: 361 algorithm -- string or None (default: None) 362 363 ALGORITHMS: 364 singular:triangL -- decomposition of self into triangular systems (Lazard). 365 singular:triangLfak -- decomp. of self into tri. systems plus factorization. 366 singular:triangM -- decomposition of self into triangular systems (Moeller). 367 368 OUTPUT: 369 a list T of lists t such that the variety of self is the union of the varieties 370 of t in L and each t is in triangular form. 371 372 EXAMPLE: 373 sage: P.<e,d,c,b,a> = PolynomialRing(QQ,5,order='lex') 374 sage: I = sage.rings.ideal.Cyclic(P) 375 sage: GB = Ideal(I.groebner_basis('singular:stdfglm')) 376 sage: GB.triangular_decomposition('singular:triangLfak') 377 [Ideal (a - 1, b - 1, c - 1, d^2 + 3*d + 1, e + d + 3) of 378 Multivariate Polynomial Ring in e, d, c, b, a over 379 Rational Field, 380 Ideal (a - 1, b - 1, c^2 + 3*c + 1, d + c + 3, e - 1) of 381 Multivariate Polynomial Ring in e, d, c, b, a over 382 Rational Field, 383 Ideal (a - 1, b^4 + b^3 + b^2 + b + 1, c - b^2, d - b^3, e 384 + b^3 + b^2 + b + 1) of Multivariate Polynomial Ring in e, 385 d, c, b, a over Rational Field, 386 Ideal (a - 1, b^2 + 3*b + 1, c + b + 3, d - 1, e - 1) of 387 Multivariate Polynomial Ring in e, d, c, b, a over 388 Rational Field, 389 Ideal (a^4 + a^3 + a^2 + a + 1, b - 1, c + a^3 + a^2 + a + 390 1, d - a^3, e - a^2) of Multivariate Polynomial Ring in e, 391 d, c, b, a over Rational Field, Ideal (a^4 + a^3 + a^2 + a 392 + 1, b - a, c - a, d^2 + 3*d*a + a^2, e + d + 3*a) of 393 Multivariate Polynomial Ring in e, d, c, b, a over 394 Rational Field, 395 Ideal (a^4 + a^3 + a^2 + a + 1, b - a, c^2 + 3*c*a + a^2, 396 d + c + 3*a, e - a) of Multivariate Polynomial Ring in e, 397 d, c, b, a over Rational Field, 398 Ideal (a^4 + a^3 + a^2 + a + 1, b^3 + b^2*a + b^2 + b*a^2 399 + b*a + b + a^3 + a^2 + a + 1, c + b^2*a^3 + b^2*a^2 + 400 b^2*a + b^2, d - b^2*a^2 - b^2*a - b^2 - b*a^2 - b*a - 401 a^2, e - b^2*a^3 + b*a^2 + b*a + b + a^2 + a) of 402 Multivariate Polynomial Ring in e, d, c, b, a over 403 Rational Field, 404 Ideal (a^4 + a^3 + a^2 + a + 1, b^2 + 3*b*a + a^2, c + b + 405 3*a, d - a, e - a) of Multivariate Polynomial Ring in e, 406 d, c, b, a over Rational Field, 407 Ideal (a^4 + a^3 + 6*a^2 - 4*a + 1, 11*b^2 - 6*b*a^3 - 408 10*b*a^2 - 39*b*a - 2*b - 16*a^3 - 23*a^2 - 104*a + 24, 409 11*c + 3*a^3 + 5*a^2 + 25*a + 1, 11*d + 3*a^3 + 5*a^2 + 410 25*a + 1, 11*e + 11*b - 6*a^3 - 10*a^2 - 39*a - 2) of 411 Multivariate Polynomial Ring in e, d, c, b, a over 412 Rational Field, 413 Ideal (a^4 - 4*a^3 + 6*a^2 + a + 1, 11*b^2 - 6*b*a^3 + 414 26*b*a^2 - 41*b*a + 4*b + 8*a^3 - 31*a^2 + 40*a + 24, 11*c 415 + 3*a^3 - 13*a^2 + 26*a - 2, 11*d + 3*a^3 - 13*a^2 + 26*a 416 - 2, 11*e + 11*b - 6*a^3 + 26*a^2 - 41*a + 4) of 417 Multivariate Polynomial Ring in e, d, c, b, a over 418 Rational Field, 419 Ideal (a^2 + 3*a + 1, b - 1, c - 1, d - 1, e + a + 3) of 420 Multivariate Polynomial Ring in e, d, c, b, a over 421 Rational Field, Ideal (a^2 + 3*a + 1, b + a + 3, c - 1, d 422 - 1, e - 1) of Multivariate Polynomial Ring in e, d, c, b, 423 a over Rational Field] 424 """ 425 426 P = self.ring() 427 428 is_groebner = self.basis_is_groebner() 429 430 # make sure to work w.r.t. 'lex' 431 if P.term_order() != 'lex': 432 Q = P.new_ring(order='lex') 433 else: 434 Q = P 435 436 if is_groebner: 437 if Q == P: 438 I = MPolynomialIdeal(P, self.reduced_basis()) # reduce only 439 else: 440 I = MPolynomialIdeal(P, self.reduced_basis()) 441 I = MPolynomialIdeal(P, I.transformed_basis('fglm')) # -> 'lex' 442 I = I.change_ring(Q) # transform to 'lex' GB 443 else: 444 if Q == P: 445 I = MPolynomialIdeal(P, self.groebner_basis()) 446 I = MPolynomialIdeal(P, I.reduced_basis()) 447 else: 448 I = self.change_ring(Q) # transform to 'lex' GB 449 I = MPolynomialIdeal(Q, I.groebner_basis()) 450 I = MPolynomialIdeal(Q, I.reduced_basis()) 451 452 if I.dimension() != 0: 453 raise TypeError, "dimension must be zero" 454 455 Ibar = I._singular_() 456 Ibar.attrib('"isSB"',1) 457 458 singular = Ibar.parent() 459 singular.lib("triang") 460 461 if algorithm is None: 462 algorithm = "singular:triangL" 463 464 if algorithm == "singular:triangL": 465 Tbar = Ibar.triangL() 466 elif algorithm == "singular:triangLfak": 467 Tbar = Ibar.triangLfak() 468 elif algorithm == "singular:triangM": 469 Tbar = Ibar.triangM() 470 else: 471 raise TypeError, "algorithm '%s' unknown"%algorithm 472 473 T = Sequence([ MPolynomialIdeal(Q,[f._sage_(Q) for f in t]) for t in Tbar ]) 474 475 return T 476 477 def associated_primes(self, algorithm='sy'): 478 """ 479 EXAMPLES: 480 sage: R.<x,y,z> = PolynomialRing(QQ, 3) 481 sage: p = z^2 + 1; q = z^3 + 2 482 sage: I = (p*q^2, y-z^2)*R 483 sage: I.associated_primes() 484 [Ideal (z^2 - y, y*z + 2, y^2 + 2*z) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (y + 1, z^2 + 1) of Multivariate Polynomial Ring in x, y, z over Rational Field] 485 """ 486 return [P for _,P in self.complete_primary_decomposition(algorithm)] 487 488 def dimension(self): 489 """ 490 The dimension of the ring modulo this ideal. 491 492 NOTE: Requires computation of a Groebner basis, which is a 493 very expensive operation. 494 """ 495 try: 496 return self.__dimension 497 except AttributeError: 498 v = list(self.groebner_basis()) 499 if len(v) == 0: 500 v = [0] 501 self.__dimension = Integer(singular(v,"ideal").dim()) 502 return self.__dimension 503 504 def vector_space_dimension(self): 505 """ 506 Return the vector space dimension of the ring modulo the ideal 507 generated by the initial terms of the generators of self. 508 509 If the generators form a standard basis, this is the same as 510 the vector space dimension of the ring modulo the ideal. If 511 the ideal is not zero-dimensional, a TypeError is raised. 512 513 ALGORITHM: Uses Singular. 514 515 EXAMPLE: 516 sage: P.<x,y> = PolynomialRing(QQ,2,order='neglex') 517 sage: I = P * [x^2 + y^2, x^2 - y^2] 518 sage: I.vector_space_dimension() 519 Traceback (most recent call last): 520 ... 521 TypeError: ideal is not zero dimensional 522 sage: J = Ideal(I.groebner_basis()) 523 sage: J.vector_space_dimension() 524 4 525 """ 526 527 vdim = Integer(self._singular_().vdim()) 528 if vdim == -1: 529 raise TypeError, "ideal is not zero dimensional" 530 else: 531 return vdim 532 533 def _groebner_basis_using_singular(self, algorithm="groebner"): 534 """ 535 Return a Groebner basis of this ideal. If a groebner basis for 536 this ideal has been calculated before the cached Groebner 537 basis is returned regardless of the requested algorithm. 538 539 ALGORITHM: Uses Singular. 540 541 INPUT: 542 algorithm -- 'groebner' - use Singular's groebner heuristic to choose 543 an algorithm (default) 544 'std' - Buchberger's algorithm 545 'stdhilb' - computes the standard basis of the homogeneous 546 ideal in the basering, via a Hilbert driven 547 standard basis computation. 548 'stdfglm' - computes the standard basis of the ideal in the basering via fglm 549 (from the degrevlex ordering to the ordering of the basering). 550 'slimgb' - SlimGB algorithm 551 552 EXAMPLES: 553 554 We compute a Groebner basis of 'cyclic 4' relative to 555 lexicographic ordering. 556 557 sage: R.<a,b,c,d> = PolynomialRing(QQ, 4, order='lex') 558 sage: I = sage.rings.ideal.Cyclic(R,4); I 559 Ideal (a + b + c + d, a*b + a*d + b*c + c*d, a*b*c + a*b*d + a*c*d + b*c*d, a*b*c*d - 1) of Multivariate Polynomial Ring in a, b, c, d over Rational Field 560 sage: I._groebner_basis_using_singular() 561 [c^2*d^6 - c^2*d^2 - d^4 + 1, c^3*d^2 + c^2*d^3 - c - d, b*d^4 - b + d^5 - d, b*c - b*d^5 + c^2*d^4 + c*d - d^6 - d^2, b^2 + 2*b*d + d^2, a + b + c + d] 562 """ 563 try: 564 return self.__groebner_basis 565 except AttributeError: 566 if algorithm=="groebner": 567 S = self._singular_().groebner() 568 elif algorithm=="std": 569 S = self._singular_().std() 570 elif algorithm=="slimgb": 571 S = self._singular_().slimgb() 572 elif algorithm=="stdhilb": 573 S = self._singular_().stdhilb() 574 elif algorithm=="stdfglm": 575 S = self._singular_().stdfglm() 576 else: 577 raise TypeError, "algorithm '%s' unknown"%algorithm 578 R = self.ring() 579 self.__singular_groebner_basis = S #remember this 580 self.__groebner_basis = Sequence([R(S[i+1]) for i in range(len(S))], R, 581 check=False, immutable=True) 582 return self.__groebner_basis 583 584 def _groebner_basis_using_libsingular(self, algorithm="std"): 585 """ 586 Return a Groebner basis of this ideal. If a groebner basis for 587 this ideal has been calculated before the cached Groebner 588 basis is returned regardless of the requested algorithm. 589 590 ALGORITHM: Uses libSINGULAR. 591 592 INPUT: 593 algorithm -- 'std' - Buchberger's algorithm 594 'slimgb' - SlimGB algorithm 595 596 EXAMPLES: 597 598 We compute a Groebner basis of 'cyclic 4' relative to 599 lexicographic ordering. 600 601 sage: R.<a,b,c,d> = PolynomialRing(QQ, 4, order='lex') 602 sage: I = sage.rings.ideal.Cyclic(R,4); I 603 Ideal (a + b + c + d, a*b + a*d + b*c + c*d, a*b*c + a*b*d + a*c*d + b*c*d, a*b*c*d - 1) of Multivariate Polynomial Ring in a, b, c, d over Rational Field 604 sage: I._groebner_basis_using_libsingular() 605 [c^2*d^6 - c^2*d^2 - d^4 + 1, c^3*d^2 + c^2*d^3 - c - d, b*d^4 - b + d^5 - d, b*c - b*d^5 + c^2*d^4 + c*d - d^6 - d^2, b^2 + 2*b*d + d^2, a + b + c + d] 606 """ 607 from sage.rings.polynomial.multi_polynomial_ideal_libsingular import std_libsingular, slimgb_libsingular 608 609 try: 610 return self.__groebner_basis 611 except AttributeError: 612 if algorithm=="std": 613 S = std_libsingular(self) 614 elif algorithm=="slimgb": 615 S = slimgb_libsingular(self) 616 else: 617 raise TypeError, "algorithm '%s' unknown"%algorithm 618 self.__groebner_basis = S 619 return self.__groebner_basis 620 621 def _singular_groebner_basis(self): 622 try: 623 S = self.__singular_groebner_basis 624 except AttributeError: 625 G = self.groebner_basis() 626 try: 627 return self.__singular_groebner_basis 628 except AttributeError: 629 pass 630 631 try: 632 S._check_valid() 633 return S 634 except ValueError: 635 G = self.groebner_basis() 636 S = singular(G) 637 self.__singular_groebner_basis = S 638 return S 639 640 641 642 def genus(self): 643 """ 644 Return the genus of the projective curve defined by this 645 ideal, which must be 1 dimensional. 646 """ 647 try: 648 return self.__genus 649 except AttributeError: 650 I = self._singular_() 651 I.parent().lib('normal.lib') 652 self.__genus = Integer(I.genus()) 653 return self.__genus 654 655 def intersection(self, other): 656 """ 657 Return the intersection of the two ideals. 658 659 EXAMPLES: 660 sage: R.<x,y> = PolynomialRing(QQ, 2, order='lex') 661 sage: I = x*R 662 sage: J = y*R 663 sage: I.intersection(J) 664 Ideal (x*y) of Multivariate Polynomial Ring in x, y over Rational Field 665 666 The following simple example illustrates that the product need not equal the intersection. 667 sage: I = (x^2, y)*R 668 sage: J = (y^2, x)*R 669 sage: K = I.intersection(J); K 670 Ideal (y^2, x*y, x^2) of Multivariate Polynomial Ring in x, y over Rational Field 671 sage: IJ = I*J; IJ 672 Ideal (x^2*y^2, x^3, y^3, x*y) of Multivariate Polynomial Ring in x, y over Rational Field 673 sage: IJ == K 674 False 675 """ 676 R = self.ring() 677 if not isinstance(other, MPolynomialIdeal_singular_repr) or other.ring() != R: 678 raise ValueError, "other must be an ideal in the ring of self, but it isn't." 679 I = self._singular_() 680 sing = I.parent() 681 J = sing(other) 682 K = I.intersect(J) 683 return R.ideal(K) 684 685 686 def minimal_associated_primes(self): 687 r""" 688 OUTPUT: 689 list -- a list of prime ideals 690 691 EXAMPLES: 692 sage: R.<x,y,z> = PolynomialRing(QQ, 3, 'xyz') 693 sage: p = z^2 + 1; q = z^3 + 2 694 sage: I = (p*q^2, y-z^2)*R 695 sage: I.minimal_associated_primes () 696 [Ideal (z^2 + 1, -z^2 + y) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z^3 + 2, -z^2 + y) of Multivariate Polynomial Ring in x, y, z over Rational Field] 697 698 ALGORITHM: Uses Singular. 699 """ 700 I = self._singular_() 701 I.parent().lib('primdec.lib') 702 M = I.minAssGTZ() 703 R = self.ring() 704 return [R.ideal(J) for J in M] 705 706 def radical(self): 707 r""" 708 The radical of this ideal. 709 710 EXAMPLES: 711 This is an obviously not radical ideal: 712 sage: R.<x,y,z> = PolynomialRing(QQ, 3) 713 sage: I = (x^2, y^3, (x*z)^4 + y^3 + 10*x^2)*R 714 sage: I.radical() 715 Ideal (y, x) of Multivariate Polynomial Ring in x, y, z over Rational Field 716 717 That the radical is correct is clear from the Groebner basis. 718 sage: I.groebner_basis() 719 [x^2, y^3] 720 721 This is the example from the singular manual: 722 sage: p = z^2 + 1; q = z^3 + 2 723 sage: I = (p*q^2, y-z^2)*R 724 sage: I.radical() 725 Ideal (z^2 - y, y^2*z + y*z + 2*y + 2) of Multivariate Polynomial Ring in x, y, z over Rational Field 726 727 \note{(From Singular manual) A combination of the algorithms 728 of Krick/Logar and Kemper is used. Works also in positive 729 characteristic (Kempers algorithm).} 730 731 sage: R.<x,y,z> = PolynomialRing(GF(37), 3) 732 sage: p = z^2 + 1; q = z^3 + 2 733 sage: I = (p*q^2, y - z^2)*R 734 sage: I.radical() 735 Ideal (z^2 - y, y^2*z + y*z + 2*y + 2) of Multivariate Polynomial Ring in x, y, z over Finite Field of size 37 736 """ 737 S = self.ring() 738 I = self._singular_() 739 I.parent().lib('primdec.lib') 740 r = I.radical() 741 return S.ideal(r) 742 743 def integral_closure(self, p=0, r=True): 744 r""" 745 Let I == self. 746 747 Returns the integral closure of$I, \ldots, I^p$, where$sI$748 is an ideal in the polynomial ring$R=k[x(1),...x(n)]$. If$p$is 749 not given, or$p=0$, compute the closure of all powers up to 750 the maximum degree in t occurring in the closure of$R[It]$(so 751 this is the last power whose closure is not just the 752 sum/product of the smaller). If$r$is given and \code{r is True}, 753 \code{I.integral_closure()} starts with a check whether I is already a 754 radical ideal. 755 756 INPUT: 757 p -- powers of I (default: 0) 758 r -- check whether self is a radical ideal first (default: True) 759 760 EXAMPLE: 761 sage: R.<x,y> = QQ[] 762 sage: I = ideal([x^2,x*y^4,y^5]) 763 sage: I.integral_closure() 764 [x^2, y^5, -x*y^3] 765 766 ALGORITHM: Use Singular 767 768 """ 769 Is = self._singular_() 770 R = self.ring() 771 singular =Is .parent() 772 singular.load('reesclos.lib') 773 ret = Sequence([ R(f) for f in Is.normalI(p,int(r))[1] ], R, 774 check=False, immutable=True) 775 return ret 776 777 def reduce(self, f): 778 """ 779 Reduce an element modulo a standard basis for this ideal. 780 This returns 0 if and only if the element is in this ideal. 781 782 EXAMPLES: 783 sage: R.<x,y> = PolynomialRing(QQ, 2) 784 sage: I = (x^3 + y, y)*R 785 sage: I.reduce(y) 786 0 787 sage: I.reduce(x^3) 788 0 789 sage: I.reduce(x - y) 790 x 791 792 sage: I = (y^2 - (x^3 + x))*R 793 sage: I.reduce(x^3) 794 y^2 - x 795 sage: I.reduce(x^6) 796 y^4 - 2*x*y^2 + x^2 797 sage: (y^2 - x)^2 798 y^4 - 2*x*y^2 + x^2 799 800 NOTE: Requires computation of a Groebner basis, which is a 801 very expensive operation. 802 """ 803 if self.base_ring() == sage.rings.integer_ring.ZZ: 804 return self._reduce_using_macaulay2(f) 805 806 try: 807 singular = self._singular_groebner_basis().parent() 808 except (AttributeError, RuntimeError): 809 singular = self._singular_groebner_basis().parent() 810 811 f = self.ring()(f) 812 g = singular(f) 813 try: 814 self.ring()._singular_(singular).set_ring() 815 h = g.reduce(self._singular_groebner_basis()) 816 except TypeError: 817 # This is OK, since f is in the right ring -- type error 818 # just means it's a rational 819 return f 820 try: 821 return self.ring()(h) 822 except (TypeError, RuntimeError): 823 return self.ring()(h[1]) 824 # Why the above? 825 # For mysterious reasons, sometimes Singular returns a length 826 # one vector with the reduced polynomial in it. 827 # This occurs in the following example: 828 #sage: R.<x,y> = PolynomialRing(QQ, 2) 829 #sage: S.<a,b> = R.quotient(x^2 + y^2) 830 #sage: phi = S.hom([b,a]) 831 #sage: loads(dumps(phi)) 832 833 834 def syzygy_module(self): 835 r""" 836 Computes the first syzygy (i.e., the module of relations of 837 the given generators) of the ideal. 838 839 ALGORITHM: Uses Singular's syz command 840 841 \note{The syz module is transposed before being returned} 842 """ 843 return self._singular_().syz().transpose().sage_matrix(self.ring()) 844 845 def reduced_basis(self): 846 r""" 847 returns$(g_1, \dots, g_s)$such that: 848 849 *$(f_1,\dots,f_n) = (g_1,\dots,g_s)$850 *$LT(g_i)\neq LT(g_j)$for all$i\neq j$851 *$LT(g_i)$does not divide m for all monomials m of 852$\{g_1,\dots,g_{i-1},g_{i+1},\dots,g_s\}$853 *$LC(g_i) == 1$for all$i$. 854 855 ALGORITHM: Uses Singular's interred command 856 857 \note{G. Pfister recommended setting option(redSB) before 858 using interred for this purpose. Though the manual doesn't 859 mention it.} 860 """ 861 from sage.rings.polynomial.multi_polynomial_ideal_libsingular import interred_libsingular 862 from sage.rings.polynomial.multi_polynomial_libsingular import MPolynomialRing_libsingular 863 864 R = self.ring() 865 866 if isinstance(R,MPolynomialRing_libsingular): 867 return interred_libsingular(self) 868 else: 869 s = self._singular_().parent() 870 o = s.option("get") 871 s.option("redSB") 872 s.option("redTail") 873 ret = [] 874 for f in self._singular_().interred(): 875 f = R(f) 876 ret.append(f/f.lc()) # lead coeffs are not reduced by interred 877 ret = Sequence( ret, R, check=False, immutable=True) 878 s.option("set",o) 879 880 return ret 881 882 def basis_is_groebner(self): 883 """ 884 Returns true if self.gens() form a Groebner Basis. This is done by 885 trying to lift Syz(LM(self)) to Syz(self) as self is a Groebner 886 Basis if and only if for every element S in Syz(LM(self)): 887 $$S \cdot G = \sum_{i=0}^{m} h_ig_i \rightarrow_G 0.$$. 888 889 ALGORITHM: Uses Singular 890 891 EXAMPLE: 892 sage: R.<a,b,c,d,e,f,g,h,i,j> = PolynomialRing(GF(127),10) 893 sage: I = sage.rings.ideal.Cyclic(R,4) 894 sage: I.basis_is_groebner() 895 False 896 sage: I2 = Ideal(I.groebner_basis()) 897 sage: I2.basis_is_groebner() 898 True 899 900 \note{From the Singular Manualf for the reduce function we use in 901 this method: 'The result may have no meaning if the second 902 argument (self, malb) is not a standard basis'. I (malb) believe 903 this refers to the mathematical fact that the results may have no 904 meaning if self is no standard basis, i.e., Singular doesn't 'add' 905 any additional 'nonsense' to the result. So we may acutally use 906 reduce to determine if self is a Groebner Basis.} 907 """ 908 from sage.matrix.constructor import matrix 909 singular = self._singular_().parent() 910 R = self.ring() 911 912 F = singular( self.gens(), "module" ) 913 LTF = singular( [f.lt() for f in self.gens()] , "module" ) 914 915 M = (F * LTF.syz()).reduce(self._singular_()) 916 917 for i in range(M.nrows()): 918 if int(singular.eval("%s[1][%s+1]!=0"%(M.name(),i))): 919 return False 920 921 self._singular_().attrib('isSB',1) 922 return True 923 924 def transformed_basis(self,algorithm="gwalk", other_ring=None): 925 """ 926 Returns a lex or other_ring Groebner Basis for a given ideal 927 self which must be represented through a Groebner Basis. 928 929 INPUT: 930 algorithm -- Options are: 931 * fglm - FGLM algorithm. The input ideal must be 932 a reduced Groebner Basis of a zero-dimensional ideal 933 * gwalk (default) - Groebner Walk algorithm 934 * awalk1 - 'first alternative' algorithm 935 * awalk2 - 'second alternative' algorithm 936 * twalk - Tran algorithm 937 * fwalk - Fractal Walk algorithm 938 other_ring -- only valid for algorithm 'fglm', if provided conversion will 939 be performed to this ring. Otherwise a lex Groebner basis will 940 be returned. 941 EXAMPLES: 942 sage: # example from the Singular manual page of fglm 943 sage: R.<x,y,z> = PolynomialRing(QQ,3) 944 sage: I = Ideal([y^3+x^2,x^2*y+x^2, x^3-x^2, z^4-x^2-y]) 945 sage: singular.option('redSB') 946 sage: I = Ideal(I.groebner_basis()) 947 sage: singular.option('noredSB') #reset 948 sage: S.<z,x,y> = PolynomialRing(QQ,3,order='lex') 949 sage: J = Ideal(I.transformed_basis('fglm',S)) 950 sage: J 951 Ideal (y^4 + y^3, x*y^3 - y^3, x^2 + y^3, z^4 + y^3 - y) of Multivariate Polynomial Ring in z, x, y over Rational Field 952 sage: # example from the Singular manual page of gwalk 953 sage: R.<z,y,x>=PolynomialRing(GF(32003),3,order='lex') 954 sage: I=Ideal([y^3+x*y*z+y^2*z+x*z^3,3+x*y+x^2*y+y^2*z]) 955 sage: I.transformed_basis('gwalk') 956 [y^9 - y^7*x^2 - y^7*x - y^6*x^3 - y^6*x^2 - 3*y^6 - 3*y^5*x - y^3*x^7 - 3*y^3*x^6 - 3*y^3*x^5 - y^3*x^4 - 9*y^2*x^5 - 18*y^2*x^4 - 9*y^2*x^3 - 27*y*x^3 - 27*y*x^2 - 27*x, 957 z*x + 8297*y^8*x^2 + 8297*y^8*x + 3556*y^7 - 8297*y^6*x^4 + 15409*y^6*x^3 - 8297*y^6*x^2 - 8297*y^5*x^5 + 15409*y^5*x^4 - 8297*y^5*x^3 + 3556*y^5*x^2 + 3556*y^5*x + 3556*y^4*x^3 + 3556*y^4*x^2 - 10668*y^4 - 10668*y^3*x - 8297*y^2*x^9 - 1185*y^2*x^8 + 14224*y^2*x^7 - 1185*y^2*x^6 - 8297*y^2*x^5 - 14223*y*x^7 - 10666*y*x^6 - 10666*y*x^5 - 14223*y*x^4 + x^5 + 2*x^4 + x^3, 958 z*y^2 + y*x^2 + y*x + 3] 959 960 961 ALGORITHM: Uses Singular 962 """ 963 from sage.rings.polynomial.multi_polynomial_ring import TermOrder,MPolynomialRing 964 from sage.rings.quotient_ring import is_QuotientRing 965 966 Is = self._singular_() 967 R = self.ring() 968 969 if algorithm in ("gwalk","awalk1","awalk2","twalk","fwalk"): 970 singular.LIB("grwalk") 971 gb = singular("%s(%s)"%(algorithm,Is.name())) 972 return [R(f) for f in gb] 973 elif algorithm == "fglm": 974 Rs = self.ring()._singular_() 975 976 # new ring 977 if other_ring==None: 978 nR = MPolynomialRing(R.base_ring(),R.ngens(), names=R.variable_names(), order="lex") 979 else: 980 nR = other_ring 981 nR._singular_().set_ring() 982 983 nIs = singular.fglm(Rs,Is) 984 985 return [nR(f) for f in nIs] 986 987 else: 988 raise TypeError, "Cannot convert basis with given algorithm" 989 990 def elimination_ideal(self, variables): 991 """ 992 Returns the elimination ideal of self with respect to the 993 variables given in 'variables'. 994 995 INPUT: 996 variables -- a list or tuple of variables in self.ring() 997 998 EXAMPLE: 999 sage: R.<x,y,t,s,z> = PolynomialRing(QQ,5) 1000 sage: I = R * [x-t,y-t^2,z-t^3,s-x+y^3] 1001 sage: I.elimination_ideal([t,s]) 1002 Ideal (y^2 - x*z, x*y - z, x^2 - y) of Multivariate Polynomial Ring in x, y, t, s, z over Rational Field 1003 1004 ALGORITHM: Uses SINGULAR 1005 1006 NOTE: Requires computation of a Groebner basis, which is a 1007 very expensive operation. 1008 """ 1009 if not isinstance(variables, (list,tuple)): 1010 variables = (variables,) 1011 1012 try: 1013 Is = self.__singular_groebner_basis 1014 except AttributeError: 1015 Is = self._singular_() 1016 1017 R = self.ring() 1018 return MPolynomialIdeal(R, [f.sage_poly(R) for f in Is.eliminate( prod(variables) ) ] ) 1019 1020 def quotient(self, J): 1021 r""" 1022 Given ideals I (==self) and J of the same polynomial ring P, 1023 return the ideal quotient of I by J consisting of the 1024 polynomials a of P such that$\{aJ \subset I\}$. 1025 1026 This is also referred to as the colon ideal (I:J). 1027 1028 INPUT: 1029 J -- multivariate polynomial ideal 1030 1031 EXAMPLE: 1032 sage: R.<x,y,z> = PolynomialRing(GF(181),3) 1033 sage: I = Ideal([x^2+x*y*z,y^2-z^3*y,z^3+y^5*x*z]) 1034 sage: J = Ideal([x]) 1035 sage: Q = I.quotient(J) 1036 sage: y*z + x in I 1037 False 1038 sage: x in J 1039 True 1040 sage: x * (y*z + x) in I 1041 True 1042 """ 1043 R = self.ring() 1044 1045 if not isinstance(J, MPolynomialIdeal): 1046 raise TypeError, "J needs to be a multivariate polynomial ideal" 1047 1048 if not R is J.ring() and not R == J.ring(): 1049 raise TypeError, "base rings do not match" 1050 1051 return R.ideal([f.sage_poly(R) for f in self._singular_().quotient(J._singular_())]) 1052 1053 def variety(self): 1054 """ 1055 Return the variety of self. 1056 1057 Given a zero-dimensional ideal I (== self) of a polynomial ring P 1058 whose order is lexicographic, return the variety of I over its 1059 coefficient field K as a list of dictionaries with (variable, value) 1060 pairs. 1061 1062 These dictionaries have cardinality equal to the number of 1063 variables in P and represent assignments of values to these 1064 variables such that all polynomials in I vanish. 1065 1066 EXAMPLE: 1067 sage: K.<w> = GF(27) # this example is from the MAGMA handbook 1068 sage: P.<x, y> = PolynomialRing(K, 2, order='lex') 1069 sage: I = Ideal([ x^8 + y + 2, y^6 + x*y^5 + x^2 ]) 1070 sage: I = Ideal(I.groebner_basis()); I 1071 Ideal (y^48 + y^41 - y^40 + y^37 - y^36 - y^33 + y^32 - y^29 + y^28 - 1072 y^25 + y^24 + y^2 + y + 1, x - y^47 - y^45 + y^44 - y^43 + y^41 - y^39 - 1073 y^38 - y^37 - y^36 + y^35 - y^34 - y^33 + y^32 - y^31 + y^30 + y^28 + 1074 y^27 + y^26 + y^25 - y^23 + y^22 + y^21 - y^19 - y^18 - y^16 + y^15 + 1075 y^13 + y^12 - y^10 + y^9 + y^8 + y^7 - y^6 + y^4 + y^3 + y^2 + y - 1) of 1076 Multivariate Polynomial Ring in x, y over Finite Field in w of size 3^3 1077 1078 sage: V = I.variety(); V 1079 [{y: w^2 + 2, x: 2*w}, {y: w^2 + 2*w, x: 2*w + 2}, {y: w^2 + w, x: 2*w + 1}] 1080 1081 sage: [f.subs(v) for f in I.gens() for v in V] # check that all polynomials vanish 1082 [0, 0, 0, 0, 0, 0] 1083 1084 However, we only account for solutions in the ground field and 1085 not in the algebraic closure. 1086 1087 sage: I.vector_space_dimension() 1088 48 1089 1090 ALGORITHM: Uses triangular decomposition. 1091 """ 1092 def _variety(T, V, v=None): 1093 if v is None: v = {} 1094 found = False 1095 for f in T: 1096 if f.is_univariate() and not f.is_constant(): 1097 T.remove(f); found = True; break 1098 1099 if found is False: 1100 V.append(v) 1101 return V 1102 1103 variable = f.variable(0) 1104 roots = f.univariate_polynomial().roots() 1105 1106 for root,multiplicity in roots: 1107 vbar = v.copy() 1108 vbar[variable] = root 1109 Tbar = [ f.subs({variable:root}) for f in T ] 1110 _variety(Tbar,V,vbar) 1111 1112 return V 1113 1114 P = self.ring() 1115 T = self.triangular_decomposition('singular:triangLfak') 1116 1117 V = [] 1118 for t in T: 1119 Vbar = _variety(list(t.gens()),[]) 1120 1121 for v in Vbar: 1122 V.append(dict([(P(var),val) for var,val in v.iteritems()])) 1123 return Sequence(V) 1124 1125class MPolynomialIdeal_macaulay2_repr: 1126 """ 1127 An ideal in a multivariate polynomial ring, which has an underlying 1128 Macaulay2 ring associated to it. 1129 1130 EXAMPLES: 1131 sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4) # optional 1132 sage: I = ideal(x*y-z^2, y^2-w^2) # optional 1133 sage: I # optional 1134 Ideal (x*y - z^2, y^2 - w^2) of Multivariate Polynomial Ring in x, y, z, w over Integer Ring 1135 """ 1136 #def __init__(self, ring, gens, coerce=True): 1137 # MPolynomialIdeal.__init__(self, ring, gens, coerce=coerce) 1138 1139 def _macaulay2_(self, macaulay2=None): 1140 """ 1141 Return Macaulay2 ideal corresponding to this ideal. 1142 """ 1143 if macaulay2 is None: macaulay2 = macaulay2_default 1144 try: 1145 I = self.__macaulay2[macaulay2] 1146 I._check_valid() 1147 return I 1148 except KeyError: 1149 pass 1150 except AttributeError: 1151 self.__macaulay2 = {} 1152 except ValueError: 1153 pass 1154 1155 R = self.ring() 1156 R._macaulay2_set_ring(macaulay2) 1157 1158 gens = [repr(x) for x in self.gens()] 1159 if len(gens) == 0: 1160 gens = ['0'] 1161 z = macaulay2.ideal(gens) 1162 self.__macaulay2[macaulay2] = z 1163 return z 1164 1165 def _macaulay2_groebner_basis(self): 1166 r""" 1167 Return the Groebner basis for this ideal, computed using Macaulay2. 1168 1169 ALGORITHM: Computed using Macaulay2. A big advantage of 1170 Macaulay2 is that it can compute Groebner basis of ideals in 1171 polynomial rings over the integers. 1172 1173 EXAMPLE: 1174 sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4) 1175 sage: I = ideal(x*y-z^2, y^2-w^2) 1176 sage: I.groebner_basis() # optional -- requires macaulay2 1177 [y^2 - w^2, x*y - z^2, y*z^2 - x*w^2, z^4 - x^2*w^2] 1178 1179 Groebner basis can be used to compute in$\Z/n\Z[x,\ldots]$. 1180 1181 sage: R.<x,y,z> = ZZ[] 1182 sage: I = ideal([y^2*z - x^3 - 19*x*z, y^2, 19^2]) 1183 sage: I.groebner_basis() # optional -- requires macaulay2 1184 [361, y^2, x^3 + 19*x*z] 1185 sage: I = ideal([y^2*z - x^3 - 19^2*x*z, y^2, 19^2]) 1186 sage: I.groebner_basis() # optional -- requires macaulay2 1187 [361, y^2, x^3] 1188 """ 1189 try: 1190 return self.__groebner_basis 1191 except AttributeError: 1192 I = self._macaulay2_() 1193 G = str(I.gb().generators().str()).replace('\n','') 1194 i = G.rfind('{{') 1195 j = G.rfind('}}') 1196 G = G[i+2:j].split(',') 1197 L = self.ring().gens_dict() 1198 B = [sage_eval(f, L) for f in G] 1199 B = Sequence(B, self.ring(), check=False) 1200 B.sort() 1201 B.set_immutable() 1202 self.__groebner_basis = B 1203 return B 1204 1205 def _reduce_using_macaulay2(self, f): 1206 """ 1207 EXAMPLES: 1208 sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4) 1209 sage: I = ideal(x*y-z^2, y^2-w^2) 1210 sage: I._reduce_using_macaulay2(x*y-z^2 + y^2) # optional 1211 w^2 1212 """ 1213 I = self._macaulay2_() 1214 M2 = I.parent() 1215 k = M2('(%r) %% %s'%(f, I.name())) 1216 R = self.ring() 1217 return R(k) 1218 1219 1220class MPolynomialIdeal( MPolynomialIdeal_singular_repr, \ 1221 MPolynomialIdeal_macaulay2_repr, \ 1222 MPolynomialIdeal_magma_repr, \ 1223 Ideal_generic ): 1224 """ 1225 An ideal of a multivariate polynomial ring. 1226 """ 1227 def __init__(self, ring, gens, coerce=True): 1228 """ 1229 Create an ideal in a multivariate polynomial ring. 1230 1231 EXAMPLES: 1232 sage: R.<x,y> = PolynomialRing(IntegerRing(), 2, order='lex') 1233 sage: R.ideal([x, y]) 1234 Ideal (x, y) of Multivariate Polynomial Ring in x, y over Integer Ring 1235 sage: R.<x0,x1> = GF(3)[] 1236 sage: R.ideal([x0^2, x1^3]) 1237 Ideal (x0^2, x1^3) of Multivariate Polynomial Ring in x0, x1 over Finite Field of size 3 1238 """ 1239 Ideal_generic.__init__(self, ring, gens, coerce=coerce) 1240 1241 def groebner_fan(self, is_groebner_basis=False, symmetry=None, verbose=False): 1242 r""" 1243 Return the Groebner fan of this ideal. 1244 1245 The base ring must be$\Q$or a finite field$\F_p$of with 1246$p \leq 32749$. 1247 1248 INPUT: 1249 is_groebner_basis -- bool (default False). if True, then I.gens() must be 1250 a Groebner basis with respect to the standard 1251 degree lexicographic term order. 1252 symmetry -- default: None; if not None, describes symmetries of the ideal 1253 verbose -- default: False; if True, printout useful info during computations 1254 """ 1255 import groebner_fan 1256 return groebner_fan.GroebnerFan(self, is_groebner_basis=is_groebner_basis, 1257 symmetry=symmetry, verbose=verbose) 1258 1259 def groebner_basis(self, algorithm=None): 1260 """ 1261 Return a Groebner basis of this ideal. 1262 1263 INPUT: 1264 algorithm -- determines the algorithm to use, available are: 1265 * None - autoselect (default) 1266 * 'singular:groebner' - Singular's groebner command 1267 * 'singular:std' - Singular's std command 1268 * 'singular:stdhilb' - Singular's stdhib command 1269 * 'singular:stdfglm' - Singular's stdfglm command 1270 * 'singular:slimgb' - Singular's slimgb command 1271 * 'libsingular:std' - libSINGULAR's std command 1272 * 'libsingular:slimgb' - libSINGULAR's slimgb command 1273 * 'toy:buchberger' - SAGE's toy/educational buchberger without strategy 1274 * 'toy:buchberger2' - SAGE's toy/educational buchberger with strategy 1275 * 'macaulay2:gb' (if available) - Macaulay2's gb command 1276 * 'magma:GroebnerBasis' (if available) - MAGMA's Groebnerbasis command 1277 1278 EXAMPLES: 1279 Consider Katsura-3 over QQ with term ordering 'degrevlex' 1280 1281 sage: P.<a,b,c> = PolynomialRing(QQ,3, order='lex') 1282 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1283 sage: I.groebner_basis() 1284 [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7] 1285 1286 1287 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1288 sage: I.groebner_basis('singular:groebner') 1289 [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7] 1290 1291 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1292 sage: I.groebner_basis('singular:std') 1293 [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7] 1294 1295 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1296 sage: I.groebner_basis('singular:stdhilb') 1297 [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7] 1298 1299 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1300 sage: I.groebner_basis('singular:stdfglm') 1301 [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7] 1302 1303 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1304 sage: I.groebner_basis('singular:slimgb') 1305 [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7] 1306 1307 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1308 sage: I.groebner_basis('toy:buchberger') 1309 [-30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c, -2*b^2 - b*c + 1/2*b, -7/125*b - 42/25*c^3 + 79/125*c^2 - 3/125*c, 1310 a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, -5*b*c + 1/2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b] 1311 1312 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1313 sage: I.groebner_basis('toy:buchberger2') 1314 [30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, a + 2*b + 2*c - 1, 1315 7/125*b + 42/25*c^3 - 79/125*c^2 + 3/125*c, a^2 - a + 2*b^2 + 2*c^2] 1316 1317 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1318 sage: I.groebner_basis('macaulay2:gb') # optional requires Macaulay2 1319 [84*c^4 - 40*c^3 + c^2 + c, 7*b + 210*c^3 - 79*c^2 + 3*c, 7*a - 420*c^3 + 158*c^2 + 8*c - 7] 1320 1321 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1322 sage: I.groebner_basis('magma:GroebnerBasis') # optional requires MAGMA 1323 [a - 60*c^3 + 158/7*c^2 + 8/7*c - 1, b + 30*c^3 - 79/7*c^2 + 3/7*c, c^4 - 10/21*c^3 + 1/84*c^2 + 1/84*c] 1324 1325 If Macaulay2 is installed, Groebner bases over ZZ can be computed. 1326 1327 sage: P.<a,b,c> = PolynomialRing(ZZ,3) 1328 sage: I = P * (a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, 2*a*b + 2*b*c - b) 1329 sage: I.groebner_basis() #optional requires Macaulay2 1330 [a + 2*b + 2*c - 1, 10*b*c + 12*c^2 - b - 4*c, 2*b^2 - 4*b*c - 6*c^2 + 2*c, 1331 42*c^3 + b^2 + 2*b*c - 14*c^2 + b, 2*b*c^2 - 6*c^3 + b^2 + 5*b*c + 8*c^2 - b - 2*c, 1332 b^3 + b*c^2 + 12*c^3 + b^2 + b*c - 4*c^2] 1333 1334 SAGE also supports local orderings (via SINGULAR): 1335 1336 sage: P.<x,y,z> = PolynomialRing(QQ,3,order='negdegrevlex') 1337 sage: I = P * ( x*y*z + z^5, 2*x^2 + y^3 + z^7, 3*z^5 +y ^5 ) 1338 sage: I.groebner_basis() 1339 [2*x^2 + y^3, x*y*z + z^5, y^5 + 3*z^5, y^4*z - 2*x*z^5, z^6] 1340 1341 ALGORITHM: Uses Singular, MAGMA (if available), Macaulay2 (if 1342 available), or toy implementation. 1343 1344 """ 1345 if algorithm is None: 1346 if self.ring().base_ring() == sage.rings.integer_ring.ZZ: 1347 return self._macaulay2_groebner_basis() 1348 else: 1349 return self._groebner_basis_using_singular("groebner") 1350 elif algorithm.startswith('singular:'): 1351 return self._groebner_basis_using_singular(algorithm[9:]) 1352 elif algorithm.startswith('libsingular:'): 1353 return self._groebner_basis_using_libsingular(algorithm[len('libsingular:'):]) 1354 elif algorithm == 'macaulay2:gb': 1355 return self._macaulay2_groebner_basis() 1356 elif algorithm == 'magma:GroebnerBasis': 1357 return self._magma_groebner_basis() 1358 elif algorithm == 'toy:buchberger': 1359 return toy_buchberger.buchberger(self) 1360 elif algorithm == 'toy:buchberger2': 1361 return toy_buchberger.buchberger_improved(self) 1362 else: 1363 raise TypeError, "algorithm '%s' unknown"%algorithm 1364 1365 1366 def change_ring(self, P): 1367 r""" 1368 Return the ideal$I$in$P$spanned by the generators$g_1,
1369        ..., g_n\$ of self as returned by self.gens().
1370
1371        INPUT:
1372            P -- a multivariate polynomial ring
1373
1374        EXAMPLE:
1375           sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex')
1376           sage: I = sage.rings.ideal.Cyclic(P)
1377           sage: I
1378           Ideal (x + y + z, x*y + x*z + y*z, x*y*z - 1) of Multivariate Polynomial Ring in x, y, z over Rational Field
1379           sage: I.groebner_basis()
1380           [z^3 - 1, y^2 + y*z + z^2, x + y + z]
1381
1382           sage: Q.<x,y,z> = P.new_ring(order='degrevlex'); Q
1383           Multivariate Polynomial Ring in x, y, z over Rational Field
1384           sage: Q.term_order()
1385           Degree reverse lexicographic term order
1386
1387           sage: J = I.change_ring(Q); J
1388           Ideal (x + y + z, x*y + x*z + y*z, x*y*z - 1) of Multivariate Polynomial Ring in x, y, z over Rational Field
1389           sage: J.groebner_basis()
1390           [x + y + z, y^2 + y*z + z^2, z^3 - 1]
1391        """
1392        return P.ideal([P(f) for f in self.gens()])
Note: See TracBrowser for help on using the repository browser.