Changeset 9050ca in git
- Timestamp:
- Jul 26, 1999, 3:41:33 PM (25 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- 58e9e019da7b571ce9d96e5da7f9b760e9a799aa
- Parents:
- de63d0a0a404b70806e92102e65c5461a0914009
- Location:
- Singular/LIB
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/algebra.lib
rde63d0 r9050ca 1 1 /////////////////////////////////////////////////////////////////////////////// 2 version="$Id: algebra.lib,v 1. 1 1999-07-19 14:54:07 obachmanExp $";2 version="$Id: algebra.lib,v 1.2 1999-07-26 13:41:33 Singular Exp $"; 3 3 info=" 4 4 LIBRARY: algebra.lib PROCEDURES FOR COMPUTING WITH ALGBRAS AND MAPS 5 AUTHORS: Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de 6 Agnes Eileen Heydtmann, email:agnes@math.uni-sb.de 5 AUTHORS: Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de, 6 Agnes Eileen Heydtmann, email:agnes@math.uni-sb.de, 7 7 Gerhard Pfister, email: pfister@mathematik.uni-kl.de 8 8 … … 11 11 module_containment(); query of module containment over a subalgebra 12 12 inSubring(p,I); test whether poly p is in subring generated by I 13 algDependen ce(I);computes algebraic relations between generators of I14 alg_kernel(phi); 13 algDependent(I); computes algebraic relations between generators of I 14 alg_kernel(phi); computes the kernel of the ringmap phi 15 15 is_injective(phi); test for injectivity of ringmap phi 16 16 is_surjective(phi); test for surjectivity of ringmap phi 17 17 is_bijective(phi); test for bijectivity of ring map phi 18 noetherNormal(id); noether normalization of ideal id 19 mapIsFinite(R,phi,I); query for finiteness of map phi:R --> basering/I 20 finitenessTest(i,z); find variables which occur as pure power in lead(i) 18 21 "; 19 22 20 23 LIB "inout.lib"; 21 24 LIB "elim.lib"; 25 LIB "ring.lib"; 26 LIB "matrix.lib"; 22 27 23 28 /////////////////////////////////////////////////////////////////////////////// … … 28 33 RETURN: - k=0 (or if k is not given) an integer: 29 34 1 : if p is contained in the subalgebra K[A[1],...,A[m]] 30 0 : if p is not contained in K[A[1],...,A[m]] 35 0 : if p is not contained in K[A[1],...,A[m]] 31 36 - k=1: a list, say l, of size 2, l[1] integer, l[2] ring, satisfying 32 37 l[1]=1 if p is in the subalgebra K[A[1],...,A[m]] and then the ring 33 l[2] contains thepoly check = h(y(1),...,y(m)) if p=h(A[1],...,A[m])38 l[2] contains poly check = h(y(1),...,y(m)) if p=h(A[1],...,A[m]) 34 39 l[1]=0 if p is in not the subalgebra K[A[1],...,A[m]] and then 35 l[2] contains the poly check = h(x,y(1),...,y(m)) if p satisfies 40 l[2] contains the poly check = h(x,y(1),...,y(m)) if p satisfies 36 41 the nonlinear relation p = h(x,A[1],...,A[m]) where 37 42 x = x(1),...,x(n) denote the variables of the basering 38 43 DISPLAY: if k=0, polynomial h(y(1),...,y(m)) if p=h(A[1],...,A[m]) is contained 39 44 in the subalgebra, provided printlevel >= voice+1 (default) 40 NOTE: The proc inSubring uses adifferent algorithm which is sometimes faster45 NOTE: The proc inSubring uses different algorithm which is sometimes faster 41 46 THEORY: The ideal of algebraic relations of the algebra generators A[1],..., 42 47 A[m] is computed introducing new variables y(i) and the product … … 47 52 " 48 53 { int DEGB = degBound; 49 degBound = 0; 54 degBound = 0; 50 55 if (size(#)==0) 51 56 { #[1] = 0; 52 } 57 } 53 58 def br=basering; 54 59 int n = nvars(br); … … 68 73 A=std(A); 69 74 check=reduce(check,A); 70 /*alternatively we could use reduce(check,A,1) which is a little faster 75 /*alternatively we could use reduce(check,A,1) which is a little faster 71 76 but result is bigger since it is not tail-reduced 72 77 */ … … 74 79 // if so, then the sum of the first n leading exponents is 0, hence i=1 75 80 // use i also to control the display 76 i = (sum(leadexp(check),1..n)==0); 81 i = (sum(leadexp(check),1..n)==0); 77 82 degBound = DEGB; 78 83 if( #[1] == 0 ) … … 83 88 { list l = i,R; 84 89 kill A,vars,emb; 85 export check; 90 export check; 86 91 dbprint(printlevel-voice+3," 87 // 'algebra_containment' created a ring as 2nd element of the list. 92 // 'algebra_containment' created a ring as 2nd element of the list. 88 93 // This ring contains the poly check which defines the algebraic relation. 89 94 // To access to the ring and see check you must give the ring a name, e.g.: 90 95 def S = l[2]; setring S; check; 91 96 "); 92 97 return(l); 93 98 } … … 98 103 ring R = 0,(x,y,z),dp; 99 104 ideal A=x2+y2,z2,x4+y4,1,x2z-1y2z,xyz,x3y-1xy3; 100 poly p1=z; 105 poly p1=z; 101 106 poly p2=x10z3-x8y2z3+2x6y4z3-2x4y6z3+x2y8z3-y10z3+x6z4+3x4y2z4+3x2y4z4+y6z4; 102 107 103 108 algebra_containment(p1,A); 104 109 algebra_containment(p2,A); 105 110 list L = algebra_containment(p2,A,1); 106 111 L[1]; 107 def S = L[2]; setring S; 112 def S = L[2]; setring S; 108 113 check; 109 114 printlevel = p; … … 113 118 proc module_containment(poly p, ideal P, ideal S, list #) 114 119 "USAGE: module_containment(p,P,M[,k]); p poly, P ideal, M ideal, k int 115 P = P[1],...,P[n] generators of a subalgebra of the basering, 120 P = P[1],...,P[n] generators of a subalgebra of the basering, 116 121 M = M[1],...,M[m] generators of a module over the subalgebra K[P] 117 122 ASSUME: ncols(P) = nvars(basering), the P[i] are algebraically independent … … 121 126 - k=1, a list, say l, of size 2, l[1] integer, l[2] ring: 122 127 l[1]=1 : if p is in <M[1],...,M[m]> and then the ring l[2] contains 123 the polynomial check = h(y(1),...,y(m),z(1),...,z(n)) if 128 the polynomial check = h(y(1),...,y(m),z(1),...,z(n)) if 124 129 p = h(M[1],...,M[m],P[1],...,P[n]) 125 l[1]=0 : if p is in not in <M[1],...,M[m]> andthen l[2] contains the126 poly nomial check = h(x,y(1),...,y(m),z(1),...,z(n)) if p satisfies130 l[1]=0 : if p is in not in <M[1],...,M[m]>, then l[2] contains the 131 poly check = h(x,y(1),...,y(m),z(1),...,z(n)) if p satisfies 127 132 the nonlinear relation p = h(x,M[1],...,M[m],P[1],...,P[n]) where 128 133 x = x(1),...,x(n) denote the variables of the basering … … 150 155 string mp=string(minpoly); 151 156 // ---------- create new ring with extra variables -------------------- 152 execute 157 execute 153 158 ("ring R=("+charstr(br)+"),(x(1..n),y(1..m),z(1..n)),(lp(n),dp(m),lp(n));"); 154 159 execute ("minpoly=number("+mp+");"); … … 169 174 //--- checking whether all variables from old ring have disappeared ------ 170 175 // if so, then the sum of the first n leading exponents is 0 171 i = (sum(leadexp(check),1..n)==0); 176 i = (sum(leadexp(check),1..n)==0); 172 177 if( #[1] == 0 ) 173 178 { dbprint(i*(printlevel-voice+3),"// "+string(check)); … … 177 182 { list l = i,R; 178 183 kill I,vars,emb,P,S; 179 export check; 184 export check; 180 185 dbprint(printlevel-voice+3," 181 // 'module_containment' created a ring as 2nd element of the list. 182 // This ring contains the poly check which defines the algebraic relation for p .186 // 'module_containment' created a ring as 2nd element of the list. 187 // This ring contains the poly check which defines the algebraic relation for p 183 188 // To access to the ring and see check you must give the ring a name, e.g.: 184 189 def S = l[2]; setring S; check; … … 211 216 "USAGE: inSubring(p,i); p poly, i ideal 212 217 RETURN: a list, say l,of size 2, l[1] integer, l[2] string 213 l[1]=1 iff p is in the subring generated by i=i[1],...,i[k], 214 and then l[2] = y(0)-h(y(1),...,y(k)) if p = h(i[1],...,i[k]) 215 l[1]=0 iff p is in not the subring generated by i, 218 l[1]=1 iff p is in the subring generated by i=i[1],...,i[k], 219 and then l[2] = y(0)-h(y(1),...,y(k)) if p = h(i[1],...,i[k]) 220 l[1]=0 iff p is in not the subring generated by i, 216 221 and then l[2] = h(y(0),y(1),...,y(k) where p satisfies the 217 222 nonlinear relation h(p,i[1],...,i[k])=0. … … 265 270 ////////////////////////////////////////////////////////////////////////////// 266 271 267 proc algDependen ce( ideal A, list # )268 "USAGE: algDependen ce(f[,c]); f ideal (say, f = f1,...,fm), c integer272 proc algDependent( ideal A, list # ) 273 "USAGE: algDependent(f[,c]); f ideal (say, f = f1,...,fm), c integer 269 274 RETURN: a list, say l, of size 2, l[1] integer, l[2] ring: 270 275 l[1] = 1 if f1,...,fm are algebraic dependent, 0 if not 271 l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 272 basering has n variables. It contains the ideal 'ker', depending 273 onIy on the y(i) and generating the algebraic relations between the 276 l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 277 basering has n variables. It contains the ideal 'ker', depending 278 onIy on the y(i) and generating the algebraic relations between the 274 279 f[i], i.e. substituting y(i) by f[i] yields 0. 275 Three differnt algorithms are used depending on c = 1,2,3. 280 Three differnt algorithms are used depending on c = 1,2,3. 276 281 If c is not given or c=0, a heuristically best method is choosen. 277 282 The basering may be a quotient ring. 278 283 To access to the ring l[2] and see ker you must give the ring a name, 279 e.g. def S=l[2]; setring S; ker; 284 e.g. def S=l[2]; setring S; ker; 280 285 DISPLAY: The above comment is displayed if printlevel >= 0 (default). 281 EXAMPLE: example algDependen ce; shows an example282 " 283 { 286 EXAMPLE: example algDependent; shows an example 287 " 288 { 284 289 int bestoption = 3; 285 290 // bestoption is the default algorithm, it may be set to 1,2 or 3; 286 291 // it should be changed, if another algorithm turns out to be faster 287 292 // in general. Is perhaps dependent on the input (# vars, size ...) 288 int tt; 293 int tt; 289 294 if( size(#) > 0 ) 290 295 { if( typeof(#[1]) == "int" ) … … 294 299 if( size(#) == 0 or tt == 0 ) 295 300 { tt = bestoption; 296 } 301 } 297 302 def br=basering; 298 303 int n = nvars(br); … … 303 308 string mp = string(minpoly); 304 309 // --------------------- 1st variant of algorithm ---------------------- 310 // use internal preimage command (should be equivalent to 2nd variant) 305 311 if ( tt == 1 ) 306 { 312 { 307 313 execute ("ring R1=("+charstr(br)+"),y(1..m),dp;"); 308 execute ("minpoly=number("+mp+");"); 309 setring br; 314 execute ("minpoly=number("+mp+");"); 315 setring br; 310 316 map phi = R1,A; 311 317 setring R1; 312 ideal ker = preimage(br,phi,B); 318 ideal ker = preimage(br,phi,B); 313 319 } 314 320 // ---------- create new ring with extra variables -------------------- 315 execute ("ring R2=("+charstr(br)+"),(x(1..n),y(1..m)),(dp);"); 321 execute ("ring R2=("+charstr(br)+"),(x(1..n),y(1..m)),(dp);"); 316 322 execute ("minpoly=number("+mp+");"); 317 323 if( tt == 1 ) 318 324 { 319 ideal ker = imap(R1,ker); 325 ideal ker = imap(R1,ker); 320 326 } 321 327 else … … 323 329 ideal vars = x(1..n); 324 330 map emb = br,vars; 325 ideal A = emb(A); 331 ideal A = emb(A); 326 332 for (i=1; i<=m; i=i+1) 327 333 { A[i] = A[i]-y(i); 328 334 } 329 335 // --------------------- 2nd variant of algorithm ---------------------- 330 // eliminate does not work in qrings 336 // use internal eliminate for eliminating m variables x(i) from 337 // ideal A[i] - y(i) (uses extra eliminating 'first row', a-order) 331 338 if ( s == 0 and tt == 2 ) 332 339 { ideal ker = eliminate(A,product(vars)); 333 340 } 334 341 else 342 // eliminate does not work in qrings 335 343 // --------------------- 3rd variant of algorithm ---------------------- 336 { execute ("ring R3=("+charstr(br)+"),(x(1..n),y(1..m)),(dp(n),dp(m));"); 344 // eliminate m variables x(i) from ideal A[i] - y(i) by choosing product 345 // order 346 {execute ("ring R3=("+charstr(br)+"),(x(1..n),y(1..m)),(dp(n),dp(m));"); 337 347 execute ("minpoly=number("+mp+");"); 338 348 if ( s != 0 ) … … 344 354 } 345 355 ideal A = imap(R2,A); 346 A =std(A);356 A = std(A); 347 357 ideal ker = nselect(A,1,n); 348 358 setring R2; … … 357 367 } 358 368 // --------------------------- return ---------------------------------- 359 s = size(ker); 369 s = size(ker); 360 370 list L = (s!=0), R2; 361 371 export(ker); … … 363 373 // The 2nd element of the list, say l, is a ring with variables x(1),...,x(n), 364 374 // y(1),...,y(m) if the basering has n variables and the ideal is f[1],...,f[m] 365 // It contains the ideal ker only depending on the y(i) and generating the 375 // It contains the ideal ker only depending on the y(i) and generating the 366 376 // relations between the f[i], i.e. substituting y(i) by f[i] yields 0. 367 377 // To access to the ring and see ker you must give the ring a name, e.g.: 368 378 def S = l[2]; setring S; ker; 369 379 "); 370 380 return (L); 371 381 } … … 376 386 ideal I = xyzu2w-1yzu2w2+u4w2-1xu2vw+u2vw2+xyz-1yzw+2u2w-1xv+vw+2, 377 387 x-w, u2w+1, yz-v; 378 list l = algDependen ce(I);388 list l = algDependent(I); 379 389 l[1]; 380 390 def S = l[2]; setring S; … … 384 394 ////////////////////////////////////////////////////////////////////////////// 385 395 proc alg_kernel( map phi, pr, list #) 386 "USAGE: alg_kernel(phi,pr[,s,c]); phi map to basering, pr preimage ring, 396 "USAGE: alg_kernel(phi,pr[,s,c]); phi map to basering, pr preimage ring, 387 397 s string (name of kernel in pr), c integer 388 398 RETURN: a string, the kernel of phi as string 389 If, moreover, a string s is given, the algorithm creates, in pr, 399 If, moreover, a string s is given, the algorithm creates, in pr, 390 400 the kernel of phi with name equal to s. 391 Three differnt algorithms are used depending on c = 1,2,3. 401 Three differnt algorithms are used depending on c = 1,2,3. 392 402 If c is not given or c=0, a heuristically best method is choosen. 393 403 (alogrithm 1 uses the preimage command) 394 404 NOTE: The basering may be a quotient ring. 395 EXAMPLE: example kernel; shows an example396 " 397 { int tt; 405 EXAMPLE: example alg_kernel; shows an example 406 " 407 { int tt; 398 408 if( size(#) >0 ) 399 409 { if( typeof(#[1]) == "int") … … 423 433 A=A,j; 424 434 A=A[1..m]; 425 list L = algDependen ce(A,tt);426 // algDependen ceis called with "bestoption" if tt = 0435 list L = algDependent(A,tt); 436 // algDependent is called with "bestoption" if tt = 0 427 437 def S = L[2]; 428 438 execute ("ring R=("+charstr(basering)+"),(@(1..n),"+varstr(pr)+"),(dp);"); … … 443 453 ideal I = x-w,u2w+1,yz-v; 444 454 map phi = r,I; // a map from r to s: 445 alg_kernel(phi,r); 446 455 alg_kernel(phi,r); // a,b,c ---> x-w,u2w+1,yz-v 456 447 457 ring S = 0,(a,b,c),ds; 448 458 ring R = 0,(x,y,z),dp; … … 450 460 ideal i = x, y, x2-y3; 451 461 map phi = S,i; // a map to a quotient ring 452 alg_kernel(phi,S,"ker",3); 462 alg_kernel(phi,S,"ker",3); // uses algorithm 3 453 463 setring S; // you have access to kernel in preimage 454 464 // setring preimage(phi); ## wenn realisiert ## … … 459 469 proc is_injective( map phi, pr,list #) 460 470 "USAGE: is_injective(phi[,c,s]); phi map, pr reimage ring, c int, s string 461 RETURN: - 1 (type int) if phi is injective, 0 if not (if s is not given). 471 RETURN: - 1 (type int) if phi is injective, 0 if not (if s is not given). 462 472 - If s is given, return a list, say l, of size 2, l[1] int, l[2] ring: 463 473 l[1] = 1 if phi is injective, 0 if not 464 l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 465 basering has n variables and the map m components, it contains the 474 l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the 475 basering has n variables and the map m components, it contains the 466 476 ideal 'ker', depending only on the y(i), the kernel of the given map 467 Three differnt algorithms are used depending on c = 1,2,3. 477 Three differnt algorithms are used depending on c = 1,2,3. 468 478 If c is not given or c=0, a heuristically best method is choosen. 469 NOTE: The basering may be a quotient ring. 479 NOTE: The basering may be a quotient ring. However, if the preimage ring is 480 a quotient ring, say pr = P/I, consider phi as a map from P and then 481 the algorithm returns 1 if the kernel of phi is 0 mod I. 470 482 To access to the ring l[2] and see ker you must give the ring a name, 471 e.g. def S=l[2]; setring S; ker; 483 e.g. def S=l[2]; setring S; ker; 472 484 DISPLAY: The above comment is displayed if printlevel >= 0 (default). 473 485 EXAMPLE: example is_injective; shows an example 474 486 " 475 { def bsr = basering; 476 int tt; 487 { def bsr = basering; 488 int tt; 477 489 if( size(#) >0 ) 478 490 { if( typeof(#[1]) == "int") … … 502 514 A=A,j; 503 515 A=A[1..m]; 504 list L = algDependen ce(A,tt);516 list L = algDependent(A,tt); 505 517 L[1] = L[1]==0; 506 518 // the preimage ring may be a quotient ring, we still have to check whether … … 510 522 { def S = L[2]; 511 523 ideal proj; 512 proj [n+1.. m] = maxideal(1);524 proj [n+1..n+m] = maxideal(1); 513 525 map psi = S,proj; 514 526 L[1] = size(NF(psi(ker),std(0))) == 0; … … 518 530 } 519 531 else 520 { 532 { 521 533 dbprint(printlevel-voice+3," 522 534 // The 2nd element of the list is a ring with variables x(1),...,x(n),y(1), … … 525 537 // To access to the ring and see ker you must give the ring a name, e.g.: 526 538 def S = l[2]; setring S; ker; 527 539 "); 528 540 return(L); 529 541 } … … 544 556 def S = l[2]; setring S; 545 557 ker; 546 558 547 559 printlevel = p; 548 560 } … … 552 564 "USAGE: is_surjective(phi); phi map to basering, or ideal defining it 553 565 RETURN: an integer, 1 if phi is surjective, 0 if not 554 NOTE: The algorithm returns 1 iff all the variables of the basering are 566 NOTE: The algorithm returns 1 iff all the variables of the basering are 555 567 contained in the polynomial subalgebra generated by the polynomials 556 defining phi. Hence, if the basering has local or mixed ordering then 557 the return value 1 means surjectivity in this sense. 568 defining phi. Hence, if the basering has local or mixed ordering 569 or if the preimage ring is a quotient ring (in which case the map 570 may not be well defined) then the return value 1 means 571 \"surjectivity\" in this sense. 558 572 EXAMPLE: example is_surjective; shows an example 559 573 " … … 584 598 } 585 599 A=std(A); 586 // ------------- check whether the x(i) are in the image ----------------- 600 // ------------- check whether the x(i) are in the image ----------------- 587 601 poly check; 588 602 for (ii=1; ii<=n; ii++ ) … … 618 632 RETURN: an integer, 1 if phi is bijective, 0 if not 619 633 NOTE: The algorithm checks first injectivity and then surjectivity 620 To interprete this for local or mixed orderings, type621 help is_surjective;634 To interprete this for local/mixed orderings, or for quotient rings 635 type help is_surjective; and help is_injective; 622 636 DISPLAY: Comment if printlevel >= voice-1 (default) 623 637 EXAMPLE: example is_bijective; shows an example … … 656 670 A=std(A); 657 671 def bsr = basering; 658 659 672 // ------- checking whether phi is injective by computing the kernel ------- 660 673 ideal ker = nselect(A,1,n); … … 662 675 setring pr; 663 676 if ( size(ideal(pr)) != 0 ) 664 { 677 { 665 678 ideal proj; 666 proj [n+1..m] = maxideal(1);679 proj[n+1..n+m] = maxideal(1); 667 680 map psi = bsr,proj; 668 t = size(NF(psi(ker),std(0))) == 0;681 t = size(NF(psi(ker),std(0))); 669 682 } 670 683 if ( t != 0 ) … … 688 701 if ( t == 0 ) 689 702 { dbprint(printlevel-voice+3,"// map injective, but not surjective" ); 690 } 703 } 691 704 return(t); 692 705 } … … 701 714 qring Q = std(z-x2+y3); 702 715 is_bijective(ideal(x,y,x2-y3),Q); 703 716 704 717 ring S = 0,(a,b,c,d),dp; 705 718 map psi = R,ideal(a,a+b,c-a2+b3,0); // a map from R to S, … … 708 721 map chi = Q,a,b,a2-b3; // amap between two quotient rings 709 722 is_bijective(chi,Q); 710 723 711 724 printlevel = p; 712 725 } 713 714 726 /////////////////////////////////////////////////////////////////////////////// 727 728 proc noetherNormal(ideal i, list #) 729 "USAGE: noetherNormal(id[,p]); id ideal, p integer 730 RETURN: a list of two ideals, say I,J: I is generated by a subset of the 731 variables with size(I) = dim(id) and J defines a map (coordinate 732 change in the basering), such that, if we define map phi=basering,J; 733 then k[var(1),...,var(n)]/phi(id) is finite over k[I] 734 If p is given, 0<=p<=100, a sparse coordinate change with p percent 735 of the matrix entries being 0 (default: p=0 i.e. dense) 736 NOTE: designed for characteristic 0, works also in char k > 0 if it 737 terminates, may result in an infinite loop in small characteristic 738 EXAMPLE: example noetherNormal; shows an example 739 " 740 { 741 int p; 742 if( size(#) != 0 ) 743 { 744 p = #[1]; 745 } 746 def r = basering; 747 int n = nvars(r); 748 list good; 749 // ------------------------ change of ordering --------------------------- 750 //a procedure from ring.lib changing the order to dp creating a new 751 //basering @R in order to compute the dimension d of i 752 changeord("@R","dp"); 753 ideal i = imap(r,i); 754 list j = mstd(i); 755 i = j[2]; 756 int d = dim(j[1]); 757 if ( d == 0) 758 { 759 setring r; 760 list l = ideal(0),maxideal(1); 761 return( l ); 762 } 763 // ------------------------ change of ordering --------------------------- 764 //Now change the order to (dp(n-d),lp) creating a new basering @S 765 string s ="dp("+string(n-d)+"),lp"; 766 changeord("@S",s); 767 ideal m; 768 769 // ----------------- sparse-random coordinate change -------------------- 770 //creating lower triangular random generators for the maximal ideal 771 //a procedure from random.lib, as sparse as possible 772 if( char(@S) > 0 ) 773 { 774 m=ideal(sparsetriag(n,n,p,char(@S)+1)*transpose(maxideal(1))); 775 } 776 if( char(@S) == 0 ) 777 { 778 if ( voice <= 6 ) 779 { 780 m=ideal(sparsetriag(n,n,p,10)*transpose(maxideal(1))); 781 } 782 if( voice > 6 and voice <= 11) 783 { 784 m=ideal(sparsetriag(n,n,p,100)*transpose(maxideal(1))); 785 } 786 if ( voice > 11 ) 787 { 788 m=ideal(sparsetriag(n,n,p,30000)*transpose(maxideal(1))); 789 } 790 } 791 792 map phi=r,m; 793 //map phi=@R,m; 794 ideal i=std(phi(i)); 795 796 // ----------------------- test for finiteness --------------------------- 797 //We need a test whether the coordinate change was random enough, if yes 798 //we are ready, else call noetherNormal again 799 list l=finitenessTest(i); 800 801 setring r; 802 list l=imap(@S,l); 803 804 if(size(l[3]) == d) //the generic case 805 { 806 good = fetch(@S,m),l[3]; 807 kill @S,@R; 808 return(good); 809 } 810 else //the bad case 811 { kill @S,@R; 812 if ( voice >= 21 ) 813 { 814 "// WARNING: In case of a finite ground field"; 815 "// the characteristic may be too small."; 816 "// This could result in an infinte loop."; 817 "// Loop in noetherNormal, voice:";, voice;""; 818 } 819 if ( voice >= 16 ) 820 { 821 "// Switch to dense coordinate change";""; 822 return(noetherNormal(i)); 823 } 824 return(noetherNormal(i,p)); 825 } 826 } 827 example 828 { "EXAMPLE:"; echo = 2; 829 ring r=0,(x,y,z),dp; 830 ideal i= xy,xz; 831 noetherNormal(i); 832 } 833 /////////////////////////////////////////////////////////////////////////////// 834 835 proc finitenessTest(ideal i,list #) 836 "USAGE: finitenessTest(J[,v]); J ideal, v intvec (say v1,...,vr) 837 RETURN: a list, say l, with l[1] integer, l[2], l[3] ideals 838 l[1] = 1 if var(v1),...,var(vr) are in l[2] and 0 else 839 l[2] (resp. l[3]) contains those variables which occur, (resp. occur 840 not) as pure power in the leading term of one of the generators of J 841 (default: v = [1,2,..,nvars(basering)]) 842 THEORY: If J is a standard basis of an ideal generated by x_1 - f_1(y),..., 843 x_n - f_n with y_j ordered lexicographically and y_j >> x_i, then, 844 if y_i appears as pure power in the leading term of J[k], J[k] defines 845 an integral relation for y_i over the y_(i+1),... and the f's. 846 Moreover, in this situation, if l[2] = y_1,...,y_r, then K[y_1,...y_r] 847 is finite over K[f_1..f_n]. If J contains furthermore polynomials 848 h_j(y), then K[y_1,...y_z]/<h_j> is finite over K[f_1..f_n]. 849 EXAMPLE: example finitenessTest; shows an example 850 " 851 { intvec V = 1..nvars(basering); 852 if (size(#) != 0 ) 853 { 854 V = #[1]; 855 } 856 intvec v,w; 857 int j,z; 858 // ---------------------- check leading exponents ------------------------- 859 for(j=1;j<=ncols(i);j++) 860 { 861 w=leadexp(i[j]); 862 if(size(ideal(w))==1) //the leading term of i[j] is a 863 { //pure power of some variable 864 v=v+w; 865 } 866 } 867 // ----------------- pick the corresponding variables --------------------- 868 //the nonzero entries of v correspond to variables which occur as 869 //pure power in the leading term of some polynomial in i 870 ideal zero, nonzero; 871 for(j=1; j<=size(v); j++) 872 { 873 if(v[j]==0) 874 { 875 zero[size(zero)+1]=var(j); 876 } 877 else 878 { 879 nonzero[size(nonzero)+1]=var(j); 880 } 881 } 882 // ---------------- do we have all pure powers we want? ------------------- 883 // test this by dividing the product of corresponding variables 884 ideal max = maxideal(1); 885 max = max[V]; 886 z = (product(nonzero)/product(max) != 0); 887 return(list(z,nonzero,zero)); 888 } 889 example 890 { "EXAMPLE:"; echo = 2; 891 ring s = 0,(x,y,z,a,b,c),(lp(3),dp); 892 ideal i= a -(xy)^3+x2-z, b -y2-1, c -z3; 893 ideal j = a -(xy)^3+x2-z, b -y2-1, c -z3, xy; 894 finitenessTest(std(i),1..3); 895 finitenessTest(std(j),1..3); 896 } 897 /////////////////////////////////////////////////////////////////////////////// 898 899 proc mapIsFinite(map phi, R, list #) 900 "USAGE: mapIsFinite(phi,R[,J]); R a ring, phi: R ---> basering a map 901 [J an ideal in the basering, J = 0 if not given] 902 RETURN: 1 if R ---> basering/J is finite and 0 else 903 EXAMPLE: example mapIsFinite; shows an example 904 " 905 { 906 def bsr = basering; 907 ideal J; 908 if( size(#) != 0 ) 909 { 910 J = #[1]; 911 } 912 string os = ordstr(bsr); 913 int m = nvars(bsr); 914 int n = nvars(R); 915 ideal PHI = ideal(phi); 916 if ( ncols(PHI) < n ) 917 { PHI[n]=0; 918 } 919 // --------------------- change of variable names ------------------------- 920 execute("ring @bsr = ("+charstr(bsr)+"),y(1..m),("+os+");"); 921 ideal J = fetch(bsr,J); 922 ideal PHI = fetch(bsr,PHI); 923 924 // --------------------------- enlarging ring ----------------------------- 925 execute("ring @rr = ("+charstr(bsr)+"),(y(1..m),x(1..n)),(lp(m),dp);"); 926 ideal J = imap(@bsr,J); 927 ideal PHI = imap(@bsr,PHI); 928 ideal M; 929 int i; 930 931 for(i=1;i<=n;i++) 932 { 933 M[i]=x(i)-PHI[i]; 934 } 935 M=std(M+J); 936 // ----------------------- test for finiteness --------------------------- 937 list l = finitenessTest(M,1..m); 938 return(l[1]); 939 } 940 example 941 { "EXAMPLE:"; echo = 2; 942 ring r = 0,(a,b,c),dp; 943 ring s = 0,(x,y,z),dp; 944 ideal i= xy; 945 map phi= r,(xy)^3+x2+z,y2-1,z3; 946 mapIsFinite(phi,r,i); 947 } 948 ////////////////////////////////////////////////////////////////////////////// 949 -
Singular/LIB/primdec.lib
rde63d0 r9050ca 1 // $Id: primdec.lib,v 1. 39 1999-07-07 14:39:12 obachmanExp $1 // $Id: primdec.lib,v 1.40 1999-07-26 13:37:49 Singular Exp $ 2 2 //////////////////////////////////////////////////////////////////////////////// 3 3 // primdec.lib // … … 11 11 //////////////////////////////////////////////////////////////////////////////// 12 12 13 version="$Id: primdec.lib,v 1. 39 1999-07-07 14:39:12 obachmanExp $";13 version="$Id: primdec.lib,v 1.40 1999-07-26 13:37:49 Singular Exp $"; 14 14 info=" 15 LIBRARY: primdec.lib PROCEDURE FOR PRIMARY DECOMPOSITION 16 17 AUTHORS: Gerhard Pfister, Wolfram Decker, Hans Schoenemann 15 LIBRARY: primdec.lib PROCEDURES FOR PRIMARY DECOMPOSITION 16 AUTHORS: Gerhard Pfister, email: pfister@mathematik.uni-kl.de (GTZ) 17 Wolfram Decker, email: decker@math.uni-sb.de (SY) 18 Hans Schoenemann, email: hannes@mathematik.uni-kl.de (SY) 18 19 19 20 PROCEDURES: 20 minAssGTZ(I); computes the minimal associated primes 21 via Gianni,Trager,Zacharias 22 minAssChar(I); computes the minimal associated primes 23 using characteristic sets 24 primdecGTZ(I); computes a complete primary decomposition 25 via Gianni,Trager,Zacharias 26 primdecSY(I); computes a complete primary decomposition 27 via Shimoyama-Yokoyama 28 testPrimary(L,k); tests whether the result of the primary 29 decomposition is correct 21 primdecGTZ(I); complete primary decomposition via Gianni,Trager,Zacharias 22 primdecSY(I); complete primary decomposition via Shimoyama-Yokoyama 23 minAssGTZ(I); the minimal associated primes via Gianni,Trager,Zacharias 24 minAssChar(I); the minimal associated primes using characteristic sets 25 testPrimary(L,k); tests the result of the primary decomposition 30 26 radical(I); computes the radical of the ideal I 31 equiRadical(I); computes the radical of the equidimensional part 32 of the ideal I 33 prepareAss(I); computes the radicals of the equidimensional parts of I 27 equiRadical(I); the radical of the equidimensional part of the ideal I 28 prepareAss(I); list of radicals of the equidimensional components of I 34 29 35 30 REMARK: … … 468 463 i[m]=poly(e)^e*leadcoef(i[m])^(e-1)*i[m]; 469 464 470 if( i[m]==0)465 if((i[m]==0)&&(voice>=15)) 471 466 { 472 467 "Warning: The characteristic ist too small to use"; 473 468 "the Algorithm of Gianni/Trager/Zacharias."; 474 469 "This may result in an infinte loop"; 470 " current nesting level in primaryTest",voice; 475 471 } 476 472 if (reduce(i[m]-t^e,prm,1) !=0) … … 777 773 } 778 774 779 //with ethe factors new ideals (hopefully the primary decomposition)775 //with the factors new ideals (hopefully the primary decomposition) 780 776 //are created 781 777 … … 1528 1524 minAssPrimes(i,1); i ideal (to use also the factorizing Groebner) 1529 1525 RETURN: list = the minimal associated prime ideals of i 1530 NOTE:1531 1526 EXAMPLE: example minAssPrimes; shows an example 1532 1527 " … … 1650 1645 list pr= minAssPrimes(i); 1651 1646 pr; 1652 pr=minAssPrimes(i,1);1647 minAssPrimes(i,1); 1653 1648 } 1654 1649 … … 1947 1942 //look for subring such that the intersection with the ideal is zero 1948 1943 //j intersected with K[var(indep[3]+1),...,var(nvar] is zero, 1949 //indep[1] is the new varstring and indep[2] the string for theblock-ordering1944 //indep[1] is the new varstring and indep[2] the string for block-ordering 1950 1945 //------------------------------------------------------------------ 1951 1946 … … 2057 2052 //leading coefficients of the polynomials there (polynomials in 2058 2053 //K[var(nnp+1),..,var(nva)]) are collected in the list h, 2059 //we need their ggt, gh, because of the following: 2060 // let(j:gh^n)=(j:gh^infinity) then j*K(var(nnp+1),..,var(nva))[..the rest..]2054 //we need their ggt, gh, because of the following: let 2055 //(j:gh^n)=(j:gh^infinity) then j*K(var(nnp+1),..,var(nva))[..the rest..] 2061 2056 //intersected with K[var(1),...,var(nva)] is (j:gh^n) 2062 2057 //on the other hand j=(j,gh^n) intersected with (j:gh^n) … … 2064 2059 //------------------------------------------------------------------------------------ 2065 2060 2066 // the arrangement for the quotientring K(var(nnp+1),..,var(nva))[..the rest..]2067 // and the map phi:K[var(1),...,var(nva)] ----->K(var(nnpr+1),..,var(nva))[..therest..]2061 //arrangement for quotientring K(var(nnp+1),..,var(nva))[..the rest..] and 2062 //map phi:K[var(1),...,var(nva)] -->K(var(nnpr+1),..,var(nva))[..rest..] 2068 2063 //------------------------------------------------------------------------------------- 2069 2064 … … 2112 2107 //but fi polynomials, then the intersection of q with the polynomialring 2113 2108 //is the saturation of the ideal generated by f1,...,fr with respect to 2114 //h which is the lcm of the leading coefficients of the fi considered in the2115 // quotientring: this is coded in saturn2109 //h which is the lcm of the leading coefficients of the fi considered 2110 //in the quotientring: this is coded in saturn 2116 2111 2117 2112 list saturn; … … 4008 4003 proc primdecGTZ(ideal i) 4009 4004 "USAGE: primdecGTZ(i); i ideal 4010 RETURN: list = list of primary ideals4011 and their associated primes4005 RETURN: a list, say pr, of primary ideals and their associated primes 4006 pr[i][1], resp. pr[i][2] is the i-th primary resp. prime component 4012 4007 NOTE: Algorithm of Gianni, Traeger, Zacharias 4013 designed for characteristic 0, works also in char k > >0,4008 designed for characteristic 0, works also in char k > 0, 4014 4009 may result in an infinite loop in small characteristic 4015 4010 EXAMPLE: example primdecGTZ; shows an example … … 4031 4026 proc primdecSY(ideal i) 4032 4027 "USAGE: primdecSY(i); i ideal 4033 RETURN: list = list of primary ideals4034 and their associated primes4028 RETURN: a list, say pr, of primary ideals and their associated primes 4029 pr[i][1], resp. pr[i][2] is the i-th primary resp. prime component 4035 4030 NOTE: Algorithm of Shimoyama-Yokoyama 4036 implemented for characteristic 0, works also in char k > >0,4037 the result may be not compl tely decomposed in small characteristic4031 implemented for characteristic 0, works also in char k > 0, 4032 the result may be not completely decomposed in small characteristic 4038 4033 EXAMPLE: example primdecSY; shows an example 4039 4034 " … … 4054 4049 "USAGE: minAssGTZ(i); i ideal 4055 4050 RETURN: list = the minimal associated prime ideals of i 4056 NOTE: designed for characteristic 0, works also in char k >> 0, 4051 NOTE: designed for characteristic 0, works also in char k > 0 4052 if it terminates, 4057 4053 may result in an infinite loop in small characteristic 4058 4054 EXAMPLE: example minAssGTZ; shows an example … … 4075 4071 "USAGE: minAssChar(i); i ideal 4076 4072 RETURN: list = the minimal associated prime ideals of i 4077 NOTE: implemented for characteristic 0, works also in char k > >0,4078 the result may be not compl tely decomposed in small characteristic4079 EXAMPLE: example primdecSY; shows an example4073 NOTE: implemented for characteristic 0, works also in char k > 0, 4074 the result may be not completely decomposed in small characteristic 4075 EXAMPLE: example minAssChar; shows an example 4080 4076 " 4081 4077 { … … 4094 4090 proc equiRadical(ideal i) 4095 4091 "USAGE: equiRadical(i); i ideal 4096 RETURN: ideal = the intersection of associated primes4097 of i of dimension of i 4098 NOTE: designed for characteristic 0, works also in char k >> 0,4092 RETURN: ideal, intersection of associated primes of i of maximal dimension 4093 NOTE: designed for characteristic 0, works also in char k > 0 4094 if it terminates, 4099 4095 may result in an infinite loop in small characteristic 4100 4096 EXAMPLE: example equiRadical; shows an example … … 4118 4114 NOTE: a combination of the algorithms of Krick/Logar 4119 4115 and Eisenbud/Huneke/Vasconcelos 4120 designed for characteristic 0, works also in char k >> 0, 4116 designed for characteristic 0, works also in char k > 0 4117 if it termintes, 4121 4118 may result in an infinite loop in small characteristic 4122 4119 EXAMPLE: example radical; shows an example … … 4213 4210 proc prepareAss(ideal i) 4214 4211 "USAGE: prepareAss(i); i ideal 4215 RETURN: list = the radicals of the equidimensional parts of i4216 NOTE: algorithm of Eisenbud,Huneke and Vasconcelos4212 RETURN: list = the radicals of the maximal dimensional components of i 4213 NOTE: uses algorithm of Eisenbud,Huneke and Vasconcelos 4217 4214 EXAMPLE: example prepareAss; shows an example 4218 4215 " … … 4254 4251 4255 4252 proc testPrimary(list pr, ideal k) 4256 "USAGE: testPrimary(pr,k) pr=primdecGTZ(k) or primdecSY(k) 4257 RETURN: int = 1, if the intersection of the primary ideals 4258 in pr is k, 0 if not 4259 NOTE: 4253 "USAGE: testPrimary(pr,k); pr a list, result of primdecGTZ(k) or primdecSY(k) 4254 RETURN: int = 1, if intersection of the primary ideals in pr is k, 0 if not 4260 4255 EXAMPLE: example testPrimary ; shows an example 4261 4256 "
Note: See TracChangeset
for help on using the changeset viewer.