Changeset 80cf34 in git
 Timestamp:
 Feb 2, 2007, 7:51:33 PM (16 years ago)
 Branches:
 (u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
 Children:
 83783ebb580d5bc290e32bc3e46524ca07777ce8
 Parents:
 80a5be143bbd0daeb5d5d2adf0825aa060b9c8d2
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/standard.lib
r80a5be r80cf34 1 1 ////////////////////////////////////////////////////////////////////////////// 2 version="$Id: standard.lib,v 1.84 20061201 16:04:56 Singular Exp $"; 2 //major revision Jan/Feb. 2007, GMG 3 ////////////////////////////////////////////////////////////////////////////// 4 version="$Id: standard.lib,v 1.85 20070202 18:51:33 Singular Exp $"; 3 5 category="Miscellaneous"; 4 6 info=" … … 7 9 PROCEDURES: 8 10 stdfglm(ideal[,ord]) standard basis of ideal via fglm [and ordering ord] 9 stdhilb(ideal[,h]) standard basis of ideal using the Hilbert function 10 groebner(ideal/module) standard basis using a heuristically chosen method 11 stdhilb(ideal[,h]) Hilbert driven Groebner basis of ideal 12 quotientList(L,...) a list, say L, s.t. ring(L) creates a correct qring 13 par2varRing([i]) create a ring with pars to vars together with i 14 hilbRing([i]) create a ring containing the homogenized i 15 qslimgb(i) computes a standard basis with slimgb in a qring 16 groebner(ideal,...) standard basis using a heuristically chosen method 11 17 res(ideal/module,[i]) free resolution of ideal or module 12 18 sprintf(fmt,...) returns fomatted string … … 16 22 "; 17 23 18 // hilbstd(ideal[,h]) standard basis using (weighted) Hilbert function19 24 ////////////////////////////////////////////////////////////////////////////// 20 25 … … 31 36 EXAMPLE: example stdfglm; shows an example" 32 37 { 33 string os; 34 def dr= basering; 35 if( (size(#)==0) or (typeof(#[1]) != "string") ) 36 { 37 os = "dp(" + string( nvars(dr) ) + ")"; 38 if ( (find( ordstr(dr), os ) != 0) and (find( ordstr(dr), "a") == 0) ) 39 { 40 os= "Dp"; 41 } 42 else 43 { 44 os= "dp"; 45 } 46 } 47 else { os = #[1]; } 48 execute("ring sr=("+charstr(dr)+"),("+varstr(dr)+"),"+os+";"); 49 ideal i= fetch(dr,i); 50 intvec opt= option(get); 51 option(redSB); 52 i=std(i); 53 option(set,opt); 54 setring dr; 55 return (fglm(sr,i)); 38 //### ev. erweitern: Gewichte von aussen setzen 39 string os; 40 int s = size(#); 41 def P= basering; 42 if( s==0 or (typeof(#[1]) != "string") ) 43 { 44 os = "dp(" + string( nvars(P) ) + ")"; 45 if ( (find( ordstr(P), os ) != 0) and (find( ordstr(P), "a") == 0) ) 46 { 47 os= "Dp"; 48 } 49 else 50 { 51 os= "dp"; 52 } 53 } 54 else { os = #[1]; } 55 56 list BRlist = ringlist(P); 57 int nvarP = nvars(P); 58 intvec w; //for ringweights of basering P 59 int k; 60 for(k=1; k<=nvarP; k++) 61 { 62 w[k]=deg(var(k)); 63 } 64 65 BRlist[3] = list(); 66 if( s==0 ) 67 { 68 if( w==1 ) 69 { 70 BRlist[3][1]=list("dp",w); 71 } 72 else 73 { 74 BRlist[3][1]=list("wp",w); 75 } 76 BRlist[3][2]=list("C",intvec(0)); 77 def Pfglm = ring(quotientList(BRlist)); 78 setring Pfglm; 79 } 80 else 81 { 82 ideal Qideal = ideal(P); 83 int sQ = size(Qideal); 84 int sM = size(minpoly); 85 if ( sM!=0 ) 86 { 87 string mpoly = string(minpoly); 88 } 89 if (sQ!=0 ) 90 { 91 execute("ring Rfglm=("+charstr(P)+"),("+varstr(P)+"),"+os+";"); 92 ideal Qideal = fetch(P,Qideal); 93 qring Pfglm = groebner(Qideal,"std","slimgb"); 94 } 95 else 96 { 97 execute("ring Pfglm=("+charstr(P)+"),("+varstr(P)+"),"+os+";"); 98 } 99 if ( sM!=0 ) 100 { 101 execute("minpoly="+mpoly+";"); 102 } 103 } 104 ideal i= fetch(P,i); 105 106 //save options: 107 int p_opt; 108 string s_opt = option(); 109 if (find(s_opt, "prot")) { p_opt = 1; } 110 intvec opt= option(get); 111 112 option(redSB); 113 //if(p_opt){"groebner in "+string(Pfglm);} 114 i = groebner(i,"std","slimgb"); 115 option(set,opt); 116 setring P; 117 return (fglm(Pfglm,i)); 56 118 } 57 119 example … … 59 121 ring r=0,(x,y,z),lp; 60 122 ideal i=y3+x2,x2y+x2,x3x2,z4x2y; 61 ideal i1=stdfglm(i); //uses fglm from "dp" to "lp" 62 i1; 63 ideal i2=stdfglm(i,"Dp"); //uses fglm from "Dp" to "lp" 64 i2; 65 } 123 stdfglm(i); //uses fglm from "dp" to "lp" 124 125 ring s = (0,x),(y,z,u,v),lp; 126 // qring qs = std(y2z3); ### Bug in fglm mit qring 127 minpoly = x2+1; 128 ideal i = y3+x2,u2y+u2,u3u2,z4u2y,v; 129 stdfglm(i,"Dp"); //uses fglm from "Dp" to "lp" 130 } 131 66 132 ///////////////////////////////////////////////////////////////////////////// 67 133 … … 69 135 "SYNTAX: @code{stdhilb (} ideal_expression @code{)} @* 70 136 @code{stdhilb (} ideal_expression@code{,} intvec_expression @code{)} 137 @code{stdhilb (} ideal_expression@code{,} list of string_expressions 138 and intvec_expressin @code{)} @* 71 139 TYPE: ideal 72 PURPOSE: computes the standard basis of the homogeneous ideal in the basering, 73 via a Hilbert driven standard basis computation.@* 74 An optional second argument will be used as 1st Hilbert function. 75 ASSUME: The optional second argument is the first Hilbert series as computed 76 by @code{hilb}. 77 SEE ALSO: stdfglm, std, groebner 140 PURPOSE: Compute a Groebner basis of the ideal in the basering by using the 141 Hilbert driven Groebner basis algorithm. 142 If an argument of type string @code{\"std\"} resp. @code{\"slimgb\"} 143 is given, the standard basis computation uses @code{std} or 144 @code{slimgb}, otherwise a heuristically chosen method (default) 145 THEORY: If the ideal is not homogeneous compute first a Groebner basis 146 of the homogenization of the ideal, then the Hilbert function and, 147 finally, a Groebner basis in the original ring by using the 148 computed Hilbert function.@* 149 If the ideal is homogeneous and a second argument of type intvec 150 is given it will be used as 1st Hilbert function in the Hilbert 151 driven algorithm. 152 NOTE: 'homogeneous' means weighted homogeneous with respect to the weights 153 w[i] of the variables var(i) of the basering. 154 ASSUME: The argument of type intvec is the 1st Hilbert series as computed 155 by @code{hilb} using an intvector w with w[i]=deg(var(i)). 156 SEE ALSO: stdfglm, std, slimgb, groebner 78 157 KEYWORDS: Hilbert function 79 158 EXAMPLE: example stdhilb; shows an example" 80 159 { 81 def R=basering; 82 83 if((homog(i)==1)(ordstr(basering)[1]=="d")) 84 { 85 if ((size(#)!=0)&&(homog(i)==1)) 86 { 87 return(std(i,#[1])); 88 } 89 return(std(i)); 90 } 91 92 execute("ring S = ("+charstr(R)+"),("+varstr(R)+",@t),dp;"); 93 ideal i=homog(imap(R,i),@t); 94 intvec v=hilb(std(i),1); 95 execute("ring T = ("+charstr(R)+"),("+varstr(R)+",@t),("+ordstr(R)+");"); 96 ideal i=fetch(S,i); 97 ideal a=std(i,v); 98 setring R; 99 map phi=T,maxideal(1),1; 100 ideal a=phi(a); 101 102 int k,j; 103 poly m; 104 int c=ncols(i); 105 106 for(j=1;j<c;j++) 107 { 108 if(deg(a[j])==0) 109 { 110 a=ideal(1); 111 attrib(a,"isSB",1); 112 return(a); 113 } 114 if(deg(a[j])>0) 115 { 116 m=lead(a[j]); 117 for(k=j+1;k<=c;k++) 160 161 // save data from basering  162 def P=basering; 163 ideal Qideal = ideal(P); //defining the quotient ideal if P is a qring 164 int was_qring; //remembers if basering was a qring 165 int is_homog = homog(Qideal); //remembers if Qideal was homog (homog(0)=1) 166 is_homog = is_homog*homog(i); //check for homogeneity of i and Qideal 167 if (size(Qideal) > 0) 168 { 169 was_qring = 1; 170 } 171 172 // save ordering of basering P for later use 173 list ord_P = ringlist(P)[3]; //ordering of basering in ringlist 174 string ordstr_P = ordstr(P); //ordering of basering as string 175 int nvarP = nvars(P); 176 intvec w; //for ringweights of basering P 177 int k,neg; 178 for(k=1; k<=nvarP; k++) 179 { 180 w[k]=deg(var(k)); 181 if(w[k] <= 0) 182 { 183 neg=1; 184 } 185 } 186 187 //save options: 188 int p_opt; 189 string s_opt = option(); 190 if (find(s_opt, "prot")) { p_opt = 1; } 191 192 // check the given method  193 string method; 194 list Method; 195 for (k=1; k<=size(#); k++) 196 { 197 if (typeof(#[k]) == "intvec") 198 { 199 intvec hi = #[k]; 200 } 201 if (typeof(#[k]) == "string") 202 { 203 method = method + "," + #[k]; 204 Method = Method + list(#[k]); 205 } 206 } 207 208 if (npars(P) > 0) //clear denominators of parameters 209 { 210 for( k=ncols(i); k>0; k ) 211 { 212 i[k]=cleardenom(i[k]); 213 } 214 } 215 216 // exclude cases to which stdhilb should no be applied  217 //Note that quotient ideal of qring must be homogeneous too 218 219 if( find(ordstr_P,"s")  find(ordstr_P,"M") 220  find(ordstr_P,"a")  (neg > 0) ) 221 { 222 if( defined(hi) && is_homog ) 223 { 224 if (p_opt){"std with given Hilbert function in basering";} 225 return( std(i,hi,w) ); 226 } 227 if (p_opt){"stdhilb not implemented, use std in basering";} 228 //if ( neg ) // std can handle local and mixed orderings 229 //{ 230 // "//*** WARNING: nonpositive ring weights, computation may not finish"; 231 //} 232 return( std(i) ); 233 } 234 235 // change to hilbRing  236 237 list hiRi = hilbRing(i); 238 intvec W = hiRi[2]; 239 def Philb = hiRi[1]; //note: Philb is no qring and the predefined 240 setring Philb; //ideal Id(1) in Philb is homogeneous 241 242 // compute Hilbert function of homogenized ideal in Philb  243 //Philb has only 1 block. There are three cases 244 245 string algorithm; //possibilities: std, slimgb, stdorslimgb 246 //define algorithm: 247 if( find(method,"std") && !find(method,"slimgb") ) 248 { 249 algorithm = "std"; 250 } 251 if( find(method,"slimgb") && !find(method,"std") ) 252 { 253 algorithm = "slimgb"; 254 } 255 if( find(method,"std") && find(method,"slimgb")  256 (!find(method,"std") && !find(method,"slimgb")) ) 257 { 258 algorithm = "stdorslimgb"; 259 } 260 261 if ( algorithm=="std"  ( algorithm=="stdorslimgb" && char(P)>0 ) ) 262 { 263 if (p_opt) {"std in ring " + string(Philb);} 264 intvec hi = hilb( std(Id(1)),1,W ); 265 } 266 if ( algorithm=="slimgb"  ( algorithm=="stdorslimgb" && char(P)==0 ) ) 267 { 268 intvec hi = hilb(qslimgb(Id(1)),1,W); 269 } 270 271 // case where we need another intermediate ring  272 //we add extra blocks for homogenizing variable @hilbRing@ 273 //and for converted parameters 274 275 list BRlist = ringlist(Philb); 276 BRlist[3] = list(); 277 int so = size(ord_P); 278 if( ord_P[so][1] =="c"  ord_P[so][1] =="C" ) 279 { 280 list moduleord = ord_P[so]; 281 so = so1; 282 } 283 for (k=1; k<=so; k++) 284 { 285 BRlist[3][k] = ord_P[k]; 286 } 287 288 BRlist[3][so+1] = list("dp",1); 289 w = w,1; 290 291 if( defined(moduleord) ) 292 { 293 BRlist[3][so+2] = moduleord; 294 } 295 296 // change to extended ring and compute std with hilbert series  297 def Phelp = ring(quotientList(BRlist)); 298 setring Phelp; 299 ideal i = imap(Philb, Id(1)); 300 kill Philb; 301 302 // compute std with Hilbert series 303 if (w ==1 ) 304 { 305 if (p_opt){ "std with hilb in " + string(Phelp);} 306 i = std(i, hi); 307 } 308 else 309 { 310 if(p_opt){"std with weighted hilb in "+string(Phelp);} 311 i = std(i, hi, w); 312 } 313 314 // go back to original ring  315 //The main computation is done. Do not forget to simplfy before maping. 316 317 // subst 1 for homogenizing var 318 if ( p_opt ) 319 { 320 "dehomogenization"; 321 } 322 i = subst(i, @hilbRing@, 1); 323 324 if (p_opt) 118 325 { 119 if(size(lead(a[k])/m)>0) 120 { 121 a[k]=0; 122 } 326 "simplification"; 123 327 } 124 } 125 } 126 a=simplify(a,2); 127 attrib(a,"isSB",1); 128 return(a); 328 i= simplify(i,34); 329 330 setring P; 331 if (p_opt) 332 { 333 "imap to ring "+string(P); 334 } 335 i = imap(Phelp,i); 336 kill Phelp; 337 i = simplify(i,34); 338 339 // compute reduces SB 340 if (find(s_opt, "redSB") > 0) 341 { 342 if (p_opt) 343 { 344 "interreduction"; 345 } 346 i=interred(i); 347 } 348 attrib(i, "isSB", 1); 349 return (i); 129 350 } 130 351 example 131 352 { "EXAMPLE:"; echo = 2; 132 ring r=0,(x,y,z),dp; 133 ideal i=y3+x2,x2y+x2,x3x2,z4x2y; 134 ideal i1=stdhilb(i); i1; 135 // the latter computation is equivalent to: 136 intvec v=hilb(i,1); 137 ideal i2=stdhilb(i,v); i2; 138 } 139 ////////////////////////////////////////////////////////////////////////// 140 141 proc hilbstd(ideal i,list #) 142 "SYNTAX: @code{stdhilb (} ideal_expression @code{)} @* 143 @code{stdhilb (} ideal_expression@code{,} intvec_expression @code{)} 144 TYPE: ideal 145 PURPOSE: Computes a Groebner basis of the homogeneous ideal in the basering. 146 THEORY: Compute first a standard basis of the (weighted) homogenization 147 of the ideal, then the (weighted) Hilbert function and finally 148 a Groebner basis in the original ring by using the computed Hilbert 149 function@* 150 An optional second argument will be used as 1st Hilbert function. 151 ASSUME: The optional second argument is the first Hilbert series as computed 152 by @code{hilb}. 153 NOTE: This procedure makes stdhilb obsolet since it is a generalization 154 to rings with some variables having weights >1. Parameters are kept. 155 SEE ALSO: stdfglm, std, groebner 156 KEYWORDS: Hilbert function 157 EXAMPLE: example hilbstd; shows an example" 158 { 159 def R=basering; 160 list lR = ringlist(R); 161 intvec v = size(lR[1..size(lR)]); //size of lists lR[i] in lR 162 int n = nvars(R); 163 intvec w; //ringweights 164 int ii, neg; 165 for(ii=1; ii<=n; ii++) 166 { 167 w[ii]=deg(var(ii)); 168 if(w[ii] <= 0) 169 {neg = 1;} 170 } 171 // exclude cases to which hilbstd should no be applied  172 if( homog(i)  find(ordstr(R),"s")  find(ordstr(R),"M") 173  find(ordstr(R),"a")  (neg > 0) ) 174 { 175 if((size(#)!=0) && homog(i)) 176 { 177 return(std(i,#[1])); 178 } 179 return(std(i)); 180 } 181 182 // create ring for fast computation of hilbert series  183 list lS=lR; 184 lS[2]=insert(lR[2],"@t",v[2]); 185 lS[3]=lR[3][1],lR[3][size(lR[3])]; 186 intvec ww=w,1; 187 if(w==1) 188 { 189 lS[3][1]=list("dp",ww); 190 } 191 else 192 { 193 lS[3][1]=list("wp",ww); 194 } 195 196 def S = ring(lS); //ring with one weighted block of variables 197 setring S; 198 ideal i = homog(imap(R,i),@t); //weighted homog of i 199 string s_opt = option(); 200 int p_opt=(find(s_opt, "prot")); 201 if (p_opt) {"std in " + string(S);} 202 intvec h = hilb(std(i),1); //compute weighted hilbert series of i 203 204 // use hilbert driven std with original ordering  205 setring R; //can access to lR only in R 206 lR[2]=lS[2]; 207 lR[3]=insert(lR[3],list("dp",1),v[3]1); 208 //insert a last block for homogenizing variabble 209 210 def T = ring(lR); //T = R with 1 homogenizing variable @t 211 setring T; //added to last block with weight 1 212 ideal i=fetch(S,i); //homogenized i in T 213 214 if (p_opt) {"std with hilb in " + string(T);} 215 ideal a=std(i,h,ww); //use h from S and Hilbert driven std in T 216 217 // dehomogenize and simplify  218 a=subst(a,@t,1); //dehomogenize in T (do not use map!) 219 a=simplify(a,34); //keep only a[j] with different leading terms 220 221 // back to original ring  222 setring R; 223 ideal a = fetch(T,a); 224 attrib(a,"isSB",1); 225 return(a); 353 ring r = 0,(x,y,z),lp; 354 ideal i = y3+x2,x2y+x2z2,x3z9,z4y2xz; 355 ideal j = stdhilb(i); j; 356 357 ring r1 = 0,(x,y,z),wp(3,2,1); 358 ideal i = y3+x2,x2y+x2z2,x3z9,z4y2xz; //ideal is homogeneous 359 ideal j = stdhilb(i,"std"); j; 360 //this is equivalent to: 361 intvec v = hilb(std(i),1); 362 ideal j1 = std(i,v,intvec(3,2,1)); j1; 363 size(NF(j,j1))+size(NF(j1,j)); //j and j1 define the same ideal 364 } 365 366 /////////////////////////////////////////////////////////////////////////////// 367 proc quotientList (list RL, list #) 368 "SYNTAX: @code{quotientList (} list_expression @code{)} @* 369 @code{quotientList (} list_expression @code{,} string_expression@code{)} 370 TYPE: list 371 PURPOSE: define a ringlist, say QL, of the first argument, say RL, which is 372 assumed to be the ringlist of a qring, but where the quotient ideal 373 RL[4] is not a standard basis with respect to the given monomial 374 order in RL[3]. Then QL will be obtained from RL just by replacing 375 RL[4] by a standard of it with respect to this order. RL itself 376 will be returnd if size(RL[4]) <= 1 (in which case it is known to be 377 a standard basis w.r.t. any ordering) or if a second argument 378 \"isSB\" of type string is given. 379 NOTE: the command ring(quotientList(RL)) defines a quotient ring correctly 380 and should be used instead of ring(RL) if the quotient ideal RL[4] 381 is not (or not known to be) a standard basis with respect to the 382 monomial ordering specified in RL[3]. 383 SEE ALSO: ringlist, ring 384 EXAMPLE: example quotientList; shows an example" 385 { 386 def P = basering; 387 if( size(#) > 0 ) 388 { 389 if ( #[1] == "isSB") 390 { 391 return (RL); 392 } 393 } 394 ideal Qideal = RL[4]; //##Achtung, nichtkommuatativem Fall behandeln 395 if( size(Qideal) <= 1) 396 { 397 return (RL); 398 } 399 400 RL[4] = ideal(0); 401 def Phelp = ring(RL); 402 setring Phelp; 403 ideal Qideal = groebner(fetch(P,Qideal)); 404 setring P; 405 RL[4]=fetch(Phelp,Qideal); 406 return (RL); 226 407 } 227 408 example 228 409 { "EXAMPLE:"; echo = 2; 229 ring r=0,(x,y,z),(wp(43),wp(49,56)); 230 ideal i=y3+x2,x2y+x2,x3x2,z4x2y; 231 ideal i1=hilbstd(i); i1; 232 // the latter computation is equivalent to: 233 ring r1=0,(x,y,z),wp(43,49,56); 234 ideal i = imap(r,i); 235 intvec v=hilb(std(i),1); 236 setring r; 237 ideal i2 = hilbstd(i,v); 238 } 239 ////////////////////////////////////////////////////////////////////////// 240 410 ring P = 0,(y,z,u,v),lp; 411 ideal i = y+u2+uv3, z+uv3; //i is an lpSB but not a dp_SB 412 qring Q = std(i); 413 list LQ = ringlist(Q); 414 LQ[3][1][1]="dp"; 415 def Q1 = ring(quotientList(LQ)); 416 setring Q1; 417 Q1; 418 419 setring Q; 420 ideal q1 = uv3+z, u2+yz, yv3zv3zu; //q1 is a dpstandard basis 421 LQ[4] = q1; 422 def Q2 = ring(quotientList(LQ,"isSB")); 423 setring Q2; 424 Q2; 425 } 426 427 /////////////////////////////////////////////////////////////////////////////// 428 proc par2varRing (list #) 429 "USAGE: par2varRing([l]); l list of ideals [default:l=empty list] 430 RETURN: list, say L, with L[1] a ring where the parameters of the 431 basering have been converted to an additional last block of 432 variables all of weight 1 and ordering dp. 433 If a list l with l[i] an ideal is given, then l[i]+minpoly is 434 mapped to an ideal in L[1] with name Id(i) 435 If the basering has no parameters then L[1] is the basering. 436 EXAMPLE: example par2varRing; shows an example" 437 { 438 def P = basering; 439 int npar = npars(P); //number of parameters 440 int s = size(#); 441 int ii; 442 if ( npar == 0) 443 { 444 dbprint(printlevelvoice+3,"// ** no parameters, ring was not changed"); 445 for( ii = 1; ii <= s; ii++) 446 { 447 ideal Id(ii) = #[ii]; 448 export (Id(ii)); 449 } 450 return(list(P)); 451 } 452 453 list rlist = ringlist(P); 454 list parlist = rlist[1]; 455 rlist[1] = parlist[1]; 456 poly Minpoly = minpoly; //check for minpoly: 457 458 //now create new ring 459 if ( size(Minpoly) == 0 ) 460 { 461 for( ii = 1; ii <= s; ii++) 462 { 463 ideal Id(ii) = #[ii]; 464 } 465 } 466 else 467 { 468 if( find(option(),"prot") ){"add minpoly to input";} 469 for( ii = 1; ii <= s; ii++) 470 { 471 ideal Id(ii) = #[ii]; 472 Id(ii)[ncols(Id(ii))+1]=Minpoly; 473 } 474 } 475 int nvar = size(rlist[2]); 476 int nblock = size(rlist[3]); 477 int k; 478 for (k=1; k<=npar; k++) 479 { 480 rlist[2][nvar+k] = parlist[2][k]; //change variable list 481 } 482 483 //converted parameters get one block dp. If module ordering was in front 484 //it stays in front, otherwise it will be moved to the end 485 intvec OW = 1; 486 for (k = 2; k <= npar; k++) 487 { 488 OW = OW,1; 489 } 490 if( rlist[3][nblock][1] =="c"  rlist[3][nblock][1] =="C" ) 491 { 492 rlist[3][nblock+1] = rlist[3][nblock]; 493 rlist[3][nblock] = list("dp",OW); 494 } 495 else 496 { 497 rlist[3][nblock+1] = list("dp",OW); 498 } 499 500 def Ppar2var = ring(quotientList(rlist)); 501 setring Ppar2var; 502 for( ii = 1; ii <= s; ii++) 503 { 504 def Id(ii) = imap(P,Id(ii)); 505 export (Id(ii)); 506 } 507 list Lpar2var = Ppar2var; 508 return(Lpar2var); 509 } 510 example 511 { "EXAMPLE:"; echo = 2; 512 ring R = (0,x),(y,z,u,v),lp; 513 minpoly = x2+1; 514 ideal i = x3,x2+y+z+u+v,xyzuv1; i; 515 def P = par2varRing(i)[1]; P; 516 setring(P); 517 Id(1); 518 } 519 520 ////////////////////////////////////////////////////////////////////////////// 521 proc hilbRing ( list # ) 522 "USAGE: hilbRing([l]); l list of ideals [default:l=empty list] 523 RETURN: list, say L: L[1] is a ring and L[2] an intvec 524 L[1] is a ring whith an extra homogenizing variable 525 @hilbRing@. The monomial ordering of L[1] is 1 block dp if the 526 weights of the variables of the basering, say R, are all 1, resp. 527 wp(w,1) wehre w is the intvec of weights of the variables of R. 528 If the basering is a quotient ring P/Q, then L[1] is not a quotient 529 ring but contains the ideal @Qidealhilb@, the homogenized ideal 530 Q of P. 531 If a list l is given with l[i] an ideal, then l[i] is 532 mapped to the homogenized ideal Id(i) in L[1]. 533 L[2] is the intvec (w,1) 534 PURPOSE: Prepare a ring for computing the (weighted) hilbert series of 535 an ideal with an easy monomial ordering. 536 EXAMPLE: example hilbRing; shows an example 537 " 538 { 539 def P = basering; 540 number Minpoly = minpoly; 541 //##kann entfallen, wenn minpoly richtig gemapt wird 542 543 if( size(Minpoly) > 0 ) //remember minpoly //## 544 { 545 int is_minpoly =1; 546 } 547 548 ideal Qideal = ideal(P); //defining the quotient ideal if P is a qring 549 if( size(Qideal) != 0 ) 550 { 551 int is_qring =1; 552 } 553 list BRlist = ringlist(P); 554 BRlist[4] = ideal(0); 555 556 int nvarP = nvars(P); 557 int s = size(#); 558 intvec w; //for ringweights of basering P 559 int k; 560 for(k=1; k<=nvarP; k++) 561 { 562 w[k]=deg(var(k)); 563 } 564 565 for(k = 1; k <= s; k++) 566 { 567 ideal Id(k) = #[k]; 568 } 569 570 // a homogenizing variable is added 571 BRlist[2][nvarP+1] = "@hilbRing@"; 572 w[nvarP +1]=1; 573 574 //ordering is set to (dp,C) if weights of all variables are 1 575 //resp. to (wp(w,1),C) where w are the ringweights of basering P 576 //homogenizing var gets weight 1: 577 578 BRlist[3] = list(); 579 if(w==1) 580 { 581 BRlist[3][1]=list("dp",w); 582 } 583 else 584 { 585 BRlist[3][1]=list("wp",w); 586 } 587 BRlist[3][2]=list("C",intvec(0)); 588 589 //change ring and get ideal from previous ring 590 //(imap converts parameters of P automatically to variables in Phelp) 591 if( defined(is_minpoly) ) //## 592 { 593 BRlist[1][4] = ideal(0); 594 } 595 596 def Philb = ring(quotientList(BRlist)); 597 kill BRlist; 598 setring Philb; 599 if( defined(is_minpoly) ) //## 600 { 601 minpoly = imap(P,Minpoly); 602 } 603 if( defined(is_qring) ) 604 { 605 ideal @Qidealhilb@ = homog( imap(P,Qideal), @hilbRing@ ); 606 export(@Qidealhilb@); 607 608 if( find(option(),"prot") ){"add quotient ideal to input";} 609 for(k = 1; k <= s; k++) 610 { //homogenize 611 ideal Id(k) = homog( imap(P,Id(k)), @hilbRing@ ), @Qidealhilb@ ; 612 export(Id(k)); 613 } 614 } 615 else 616 { 617 for(k = 1; k <= s; k++) 618 { //homogenize 619 ideal Id(k) = homog( imap(P,Id(k)), @hilbRing@ ); 620 export(Id(k)); 621 } 622 } 623 624 list Lhilb = Philb,w; 625 return(Lhilb); 626 } 627 example 628 { "EXAMPLE:"; echo = 2; 629 ring R = 0,(x,y,z,u,v),lp; 630 ideal i = x+y2+z3,xy+xv+yz+zu+uv,xyzuv1; 631 def P = hilbRing(i)[1]; P; 632 setring P; 633 Id(1); 634 hilb(std(Id(1)),1); 635 636 ring S = 0,(x,y,z,u,v),lp; 637 qring T = std(x+y2+z3); 638 ideal i = xy+xv+yz+zu+uv,xyzuvv5; 639 def Q = hilbRing(i)[1]; Q; 640 setring Q; 641 Id(1); 642 } 643 644 ////////////////////////////////////////////////////////////////////////////// 645 proc qslimgb (i) 646 "USAGE: qslimgb(i); i ideal 647 RETURN: ideal, a standard basis of i computed with slimgb 648 NOTE: As long as slimgb does not know qrings qslimgb should be used in case 649 the basering is (possibly) a quotient ring. The quotient ideal is 650 added to the input and slimgb is applied. 651 ** not yet implemented for modules 652 EXAMPLE: example qslimgb; shows an example" 653 { 654 def P = basering; 655 ideal Qideal = ideal(P); //defining the quotient ideal if P is a qring 656 int p_opt; 657 if( find(option(),"prot") ) 658 { 659 p_opt=1; 660 } 661 if (size(Qideal) == 0) 662 { 663 if (p_opt) 664 { 665 "slimgb in ring " + string(P); 666 } 667 return(slimgb(i)); 668 } 669 670 //case of a qring; since slimgb does not know qrings we 671 //delete the quotient ideal and add it to i 672 673 list BRlist = ringlist(P); 674 BRlist[4] = ideal(0); 675 def Phelp = ring(BRlist); 676 kill BRlist; 677 setring Phelp; 678 ideal iq = imap(P,i), imap(P,Qideal); 679 if (p_opt) 680 { 681 "slimgb in ring " + string(Phelp); 682 "(with quotient ideal added to input)"; 683 } 684 iq = slimgb(iq); 685 686 setring P; 687 if (p_opt) 688 { 689 "imap to original ring"; 690 } 691 i = imap(Phelp,iq); 692 kill Phelp; 693 694 if (find(option(),"redSB") > 0) 695 { 696 if (p_opt) 697 { 698 "interreduction"; 699 } 700 i=interred(i); 701 } 702 attrib(i, "isSB", 1); 703 return (i); 704 } 705 example 706 { "EXAMPLE:"; echo = 2; 707 ring R = (0,v),(x,y,z,u),dp; 708 qring Q = std(x2y3); 709 ideal i = x+y2,xy+yz+zu+u*v,xyzu*v1; 710 ideal j = qslimgb(i); 711 } 712 713 ////////////////////////////////////////////////////////////////////////////// 241 714 proc groebner(def i, list #) 242 715 "SYNTAX: @code{groebner (} ideal_expression @code{)} @* … … 244 717 @code{groebner (} ideal_expression@code{,} int_expression @code{)} @* 245 718 @code{groebner (} module_expression@code{,} int_expression @code{)} 719 @code{groebner (} ideal_expression@code{,} list of string_expressions 720 @code{)} @* 721 @code{groebner (} ideal_expression@code{,} list of string_expressions 722 and int_expression @code{)} @* 723 @code{groebner (} ideal_expression@code{,} int_expression @code{)} @* 246 724 TYPE: type of the first argument 247 PURPOSE: computes the standard basis of the first argument @code{I} 248 (ideal or module), by a heuristically chosen method: 249 possiblities are @code{std}, @code{slimgb} and/or conversions 250 based on @code{fglm}, @code{stdhilb} etc. 251 @code{option(prot)} tells about the chosen way. 252 NOTE: If a 2nd argument @code{wait} is given, then the computation proceeds 253 at most @code{wait} seconds. That is, if no result could be computed in 254 @code{wait} seconds, then the computation is interrupted, 0 is returned, 255 a warning message is displayed, and the global variable 256 @code{Standard::groebner_error} is defined. 257 SEE ALSO: stdhilb, stdfglm, std 725 PURPOSE: computes a standard basis of the first argument @code{I} 726 (ideal or module), by a heuristically chosen method (default) 727 or by a method specified by further arguments of type string. 728 Possible methods are: @* 729  the direct methods @code{\"std\"} or @code{\"slimgb\"} without 730 conversion @* 731  conversion methods @code{\"hilb\"} or @code{\"fglm\"} where 732 a Groebner basis is first computed with an \"easy\" ordering 733 and then converted to the ordering of the basering by the 734 Hilbert driven Groebner basis computation. 735 The actual computation of the Groebner basis can be 736 specified by @code{\"std\"} or by @code{\"slimgb\"} 737 (not implemented for all orderings) @* 738 A further string @code{\"par2var\"} converts parameters to an extra 739 block of variables before a Groebner basis computation (and 740 afterwards back). 741 @code{option(prot)} tells about the chosen method. 742 NOTE: If a further argument, say @code{wait}, of type int is given, 743 then the computation proceeds at most @code{wait} seconds. 744 That is, if no result could be computed in @code{wait} seconds, 745 then the computation is interrupted, 0 is returned, a warning 746 message is displayed, and the global variable 747 @code{Standard::groebner_error} is defined. 748 This feature uses MP and is hence only available on UNIX platforms. 749 HINT: Since there exists no uniform best method for computing standard 750 bases, and since the difference in performance of a method on 751 different examples can be huge, it is recommended to test, for hard 752 examples, first various methods on a simplified example (e.g. use 753 characteristic 32003 instead of 0 or substitute a subset of 754 parameters/variables by integers, etc.). @* 755 SEE ALSO: stdhilb, stdfglm, std, slimgb 258 756 KEYWORDS: time limit on computations; MP, groebner basis computations 259 757 EXAMPLE: example groebner; shows an example" 260 758 { 759 760 //Vorgabe einer Teilmenge aus {hilb,fglm,par2var,std,slimgb} 761 //Aktuelle Einstellungen (Jan 2007): 762 // 763 //0. Immer Aufruf von std unabhaengig von der Vorgabe: 764 // gemischte Ordnungen, extra Gewichtsvektor, Matrix Ordnungen, Moduln 765 766 //1. Keine Vorgabe: es wirkt die aktuelle Heuristk: 767 //  Char p: std 768 //  Char = 0: slimgb (im qring wird Quotientenideal zum Input addiert) 769 //  1BlockOrdnungen: direkt Aufruf von std oder slimgb 770 //  Komplizierte Ordnungen (lp oder > 1 Block): hilb 771 //  Parameter werden grundsaetzlich nicht in Variable umgewandelt 772 // ? alternativ: more than 1 parameter will be converted to ring variable ? 773 //  fglm is keine Heruristik, da sonst vorher dim==0 peprueft werden muss 774 775 //2. Vorgabe aus {std,slimgb}: es wird wo immer moeglich das angegebene 776 // gewaehlt (da slimgb keine Hilbertfunktion kennt, wird std verwendet). 777 // Bei slimgb im qring, wird das Quotientenideal zum Ideal addiert. 778 // Bei Angabe von std zusammen mit slimgb (aeuquivalent zur Angabe von 779 // keinem von beidem) wirkt obige Heuristik. 780 781 //3. Nichtleere Vorgabe aus {hilb,fglm,std,slimgb}: 782 // es wird nur das angegebene und moegliche sowie das notwendige verwendet 783 // und bei Wahlmoeglickeit je nach Heuristik. 784 // Z.B. Vorgabe von {hilb} ist aequivalent zu {hilb,std,slimgb} und es wird 785 // hilb und nach Heuristik std oder slimgb verwendet, aber nicht par2var; 786 // bei Vorgabe von {hilb,slimgb} wird hilb und wo moeglich slimgb verwendet. 787 788 //4. Bei Vorgabe von {par2var} wird par2var immer mit hilb und nach Heuristik 789 // std oder slimgb verwendet. Zu Variablen konvertierte Parameter haben 790 // extra letzten Block und Gewichte 1. 791 792 261 793 def P=basering; 262 263 // we have two arguments  try to use MPfork links 264 if (size(#) > 0) 265 { 266 if (system("with", "MP")) 267 { 268 if (typeof(#[1]) == "int") 269 { 270 int wait = #[1]; 794 // save the given method  795 string method; 796 list Method; 797 int k; 798 for (k=1; k<=size(#); k++) 799 { 800 if (typeof(#[k]) == "int") 801 { 802 if (defined(wait) != voice) 803 { 804 int wait = #[k]; 805 } 806 } 807 if (typeof(#[k]) == "string") 808 { 809 method = method + "," + #[k]; 810 Method = Method + list(#[k]); 811 } 812 } 813 814 //======= we have an argument of type int  try to use MPfork links ======= 815 if ( defined(wait) == voice ) 816 { 817 if ( system("with", "MP") ) 818 { 271 819 int j = 10; 272 820 … … 277 825 int pid = read(l_fork); 278 826 write(l_fork, quote(groebner(eval(i)))); 827 //### write(l_fork, quote(groebner(eval(i),Method))); 828 //Fehlermeldung: 829 // ***dError: undef. ringorder used 830 // occured at: 279 831 280 832 // sleep in small intervalls for appr. one second … … 324 876 } 325 877 return (result); 878 } 879 else 880 { 881 "** groebner with a time limit on computation is not supported 882 in this configuration"; 883 } 884 } 885 886 //=========== we are still here  do the actual computation ============= 887 888 // save data from basering  889 poly Minpoly = minpoly; //minimal polynomial 890 int was_minpoly; //remembers if there was a minpoly in P 891 if (size(Minpoly) > 0) 892 { 893 was_minpoly = 1; 894 } 895 896 ideal Qideal = ideal(P); //defining the quotient ideal if P is a qring 897 int was_qring; //remembers if basering was a qring 898 int is_homog = homog(Qideal); //remembers if Qideal was homog (homog(0)=1) 899 if (size(Qideal) > 0) 900 { 901 was_qring = 1; 902 } 903 list BRlist = ringlist(P); 904 905 // save ordering of basering P for later use 906 list ord_P = BRlist[3]; //should be available in all rings 907 string ordstr_P = ordstr(P); 908 int nvars_P = nvars(P); 909 int npars_P = npars(P); 910 intvec w; //for ringweights of basering P 911 int neg; 912 for(k=1; k<=nvars_P; k++) 913 { 914 w[k]=deg(var(k)); 915 if(w[k] <= 0) 916 { 917 neg=1; 918 } 919 } 920 921 //save options: 922 intvec opt=option(get); 923 string s_opt = option(); 924 int p_opt; 925 if (find(s_opt, "prot")) { p_opt = 1; } 926 927 // cases where std is always used  928 //If other methods are not implemented or do not make sense, i.e. for 929 //local or mixed orderings, matrix orderings, extra weight vector and modules 930 931 if( ( find(ordstr_P,"s") > 0 ) 932  ( find(ordstr_P,"M") > 0 ) 933  ( find(ordstr_P,"a") > 0 ) 934  ( nrows(i)>1 ) //module case, not yet handled by slimgb 935  ( neg>0 ) ) //***fuer Moduln slimgb zulassen, wenn implementiert 936 { 937 if (p_opt) { "std in basering"; } 938 //if ( neg > 0 ) // std can handle local and mixed orderings 939 //{ 940 // "*** WARNING: some weights are negative, computation may not finish"; 941 //} 942 i = std(i); 943 return(i); 944 } 945 946 //now we have: 947 //ideal, global ordering, no matrix ordering, no extra weight vector 948 //The interesting cases start now. 949 950 // classify the possible settings  951 string algorithm; //possibilities: std, slimgb, stdorslimgb 952 string conversion; //possibilities: hilb, fglm, hilborfglm, no 953 string partovar; //possibilities: yes, no 954 string order; //possibilities: simple, !simple 955 string direct; //possibilities: yes, no 956 957 //define algorithm: 958 if( find(method,"std") && !find(method,"slimgb") ) 959 { 960 algorithm = "std"; 961 } 962 if( find(method,"slimgb") && !find(method,"std") ) 963 { 964 algorithm = "slimgb"; 965 } 966 if( find(method,"std") && find(method,"slimgb")  967 (!find(method,"std") && !find(method,"slimgb")) ) 968 { 969 algorithm = "stdorslimgb"; 970 } 971 972 //define conversion: 973 if( find(method,"hilb") && !find(method,"fglm") ) 974 { 975 conversion = "hilb"; 976 } 977 if( find(method,"fglm") && !find(method,"hilb") ) 978 { 979 conversion = "fglm"; 980 } 981 if( find(method,"fglm") && find(method,"hilb") ) 982 { 983 conversion = "hilborfglm"; 984 } 985 if( !find(method,"fglm") && !find(method,"hilb") ) 986 { 987 conversion = "no"; 988 } 989 990 //define partovar: 991 if( find(method,"par2var") && npars_P > 0 ) 992 { 993 partovar = "yes"; 994 } 995 else 996 { 997 partovar = "no"; 998 } 999 1000 //define order: 1001 if (system("nblocks") <= 2) 1002 { 1003 if ( find(ordstr_P,"M")+find(ordstr_P,"lp")+find(ordstr_P,"rp") <= 0 ) 1004 { 1005 order = "simple"; 1006 } 1007 } 1008 1009 //define direct: 1010 if ( (order=="simple" && (size(method)==0 ))  1011 (order=="simple" && (method==",par2var" && npars_P==0 ))  1012 (conversion=="no" && partovar=="no" && 1013 (algorithm=="std"  algorithm=="slimgb"  1014 (find(method,"std") && find(method,"slimgb")) ) ) ) 1015 { 1016 direct = "yes"; 1017 } 1018 else 1019 { 1020 direct = "no"; 1021 } 1022 1023 //order=="simple" means that the ordering of the variables consists of one 1024 //block which is not a matrix ordering and not a lexicographical ordering. 1025 //(Note:Singular counts always least 2 blocks, one is for module component): 1026 //Call a method "direct" if conversion=="no" && partovar="no" which means 1027 //that we apply std or slimgb dircet in the basering (exception 1028 //as long as slimgb does not know qrings: in a qring of a ring P 1029 //the ideal Qideal is added to the ideal and slimgb is applied in P). 1030 //We apply a direct method if we have a simple monomial ordering, if no 1031 //conversion (fglm or hilb) is specified and if the parameters shall 1032 //not be made to variables 1033 1034 // direct methods  1035 if ( direct == "yes" ) 1036 { 1037 if ( algorithm=="std"  (algorithm=="stdorslimgb" && char(P)>0) ) 1038 { 1039 if (p_opt) { "std in " + string(P); } 1040 i = std(i); 1041 return(i); 1042 } 1043 if ( algorithm=="slimgb"  (algorithm=="stdorslimgb" && char(P)==0) ) 1044 { 1045 i = qslimgb(i); 1046 return(i); 1047 } 1048 } 1049 1050 // indirect methods  1051 //indirect methods are methods where a conversion is used with a ring change 1052 //We are in the following situation: 1053 //direct=="no" (i.e. "hilb" or "fglm" or "par2var" is given) 1054 //or no method is given and we have a complicated monomial ordering 1055 //Note thar "par2var" is not a default strategy, it must be explicitely 1056 //given in order to be performed. 1057 //## TODO: fglm has still to be implemented 1058 1059 // case where no parameters are made to variables  1060 if ( partovar == "no" && conversion == "hilb" 1061  (partovar == "no" && conversion == "fglm" ) 1062  (partovar == "no" && conversion == "hilborfglm" ) 1063  (partovar == "no" && conversion == "no" && direct == "no") ) 1064 //last case: heuristic 1065 { 1066 if ( conversion=="fglm" ) 1067 { 1068 return (stdfglm(i)); 1069 } 1070 if ( algorithm=="std"  (algorithm=="stdorslimgb" && char(P)>0) ) 1071 { 1072 return (stdhilb(i,"std")); 1073 } 1074 if ( algorithm=="slimgb"  (algorithm=="stdorslimgb" && char(P)==0) ) 1075 { 1076 return (stdhilb(i,"slimgb")); 1077 } 1078 } 1079 1080 // case where parameters are made to variables  1081 //define a ring Phelp via par2varRing in which the parameters are variables 1082 1083 else 1084 { 1085 // reset options 1086 option(none); 1087 // turn on options prot, mem, intStrategy if previously set 1088 if ( find(s_opt, "prot") ) 1089 { option(prot); } 1090 if ( find(s_opt, "mem") ) 1091 { option(mem); } 1092 if ( find(s_opt, "intStrategy") ) 1093 { option(intStrategy); } 1094 1095 is_homog = is_homog*homog(i); //check for homogeneity of i and Qideal 1096 1097 //first clear denominators of parameters 1098 if (npars_P > 0) 1099 { 1100 for( k=ncols(i); k>0; k ) 1101 { i[k]=cleardenom(i[k]); } 1102 } 1103 1104 def Phelp = par2varRing(i)[1]; //minpoly is mapped with i 1105 setring Phelp; 1106 ideal i = Id(1); 1107 is_homog = homog(i); 1108 1109 //If parameters are converted to ring variables, they appear in an extra 1110 //block. Therefore we use always hilb for this block ordering: 1111 if ( conversion=="fglm" ) 1112 { 1113 i = (stdfglm(i)); //only uesful for 1 parameter with minpoly 326 1114 } 327 1115 else 328 1116 { 329 "** groebner needs int as 2nd arg"; 330 } 331 } 332 else 333 { 334 "** groebner with two args is not supported in this configuration"; 335 } 336 } 337 338 // we are still here  do the actual computation 339 string ordstr_P = ordstr(P); 340 int nvarP = nvars(P); 341 intvec w; //ringweights 342 int neg,k; 343 for(k=1; k<=nvarP; k++) 344 { 345 w[k]=deg(var(k)); 346 if(w[k] <= 0) {neg=1;} 347 } 348 if ( ( find(ordstr_P,"s") > 0) 349 (find(ordstr_P,"M") > 0) 350 (find(ordstr_P,"a") > 0) 351 (neg>0) ) 352 { 353 //spaeter den lokalen fall ueber lp oder aehnlich behandeln 354 return(std(i)); 355 } 356 357 if (typeof(basering)=="ring") // slimgb does not know qrings 358 { 359 //if ordering is global, there are parameters and minpoly is 0 360 if (((npars(basering)>0) &&(minpoly==0))) 361 { return(slimgb(i)); } 362 // ordering dp, char 0 363 if((char(P)==0) && (system("nblocks") <= 2) && (find(ordstr_P,"dp")>0)) 364 { return(slimgb(i)); } 365 } 366 // for module case, not already hadled by slimgb: 367 if (nrows(i)>1) 368 { return(std(i)); } 369 int IsSimple_P; 370 if (system("nblocks") <= 2) 371 { 372 if (find(ordstr_P, "M") <= 0) 373 { 374 IsSimple_P = 1; 375 } 376 } 377 int npars_P = npars(P); 378 379 // return std if no parameters and (dp or wp) 380 if ((npars_P <= 1) && IsSimple_P) 381 { 382 if (find(ordstr_P, "d") > 0) 383 { 384 return (std(i)); 385 } 386 if (find(ordstr_P,"w") > 0) 387 { 388 return (std(i)); 389 } 390 } 391 392 // reset options 393 intvec opt=option(get); 394 int p_opt; 395 string s_opt = option(); 396 option(none); 397 // turn on option(prot) and/or option(mem), if previously set 398 if (find(s_opt, "prot")) 399 { 400 option(prot); 401 p_opt = 1; 402 } 403 if (find(s_opt, "mem")) 404 { option(mem); } 405 if (find(s_opt, "intStrategy")) 406 { option(intStrategy); } 407 408 // construct ring in which first std computation is done 409 // CL: 21/09/05 for Singular 30 with ringlists.... 410 411 list BRlist = ringlist(P); 412 int add_vars = 0; 413 ideal Qideal = ideal(P); 414 415 if (npars_P > 0) 416 { 417 for(k=ncols(i); k>0; k) { i[k]=cleardenom(i[k]); } 418 } 419 // more than one parameters are converted to ring variables 420 if (npars_P > 1) 421 { 422 for (k=1; k<=npars_P; k++) 423 { 424 BRlist[2][nvarP+k] = BRlist[1][2][k]; 425 } 426 BRlist[1]=BRlist[1][1]; 427 add_vars = npars_P; 428 } 429 430 431 // for Hilbert driven approach, Qring structure is removed (defining ideal 432 // will be added to the ideal under consideration in the process). 433 if (size(BRlist[4])>0) 434 { 435 int was_qring = 1; 436 BRlist[4] = ideal(0); 437 } 438 439 // a homogenizing variable is added, if necessary 440 int is_homog = (homog(i) && (npars_P <= 1)); 441 if (! is_homog) 442 { 443 add_vars = add_vars + 1; 444 BRlist[2][nvarP+add_vars] = "@t@"; 445 } 446 // save ordering for later use 447 list ord_P = BRlist[3]; // should be ring independent 448 449 //ordering is set to (wp(w,1..1), C) where w are the ringweights 450 intvec weight_wp = w; 451 for(k=nvarP+1; k<=nvarP+add_vars; k++) 452 { 453 weight_wp[k]=1; 454 } 455 456 BRlist[3] = list(); 457 if(weight_wp==1) 458 { 459 BRlist[3][1]=list("dp",weight_wp); 460 } 461 else 462 { 463 BRlist[3][1]=list("wp",weight_wp); 464 } 465 BRlist[3][2]=list("C",intvec(0)); 466 467 // change the ring 468 def Phelp = ring(BRlist); 469 kill BRlist; 470 setring Phelp; 471 472 // get ideal from previous ring 473 if (is_homog) 474 { 475 ideal qh = imap(P, i), imap(P,Qideal); 476 } 477 else 478 { 479 // and homogenize 480 ideal qh = homog(imap(P,i),@t@), homog(imap(P,Qideal),@t@); 481 } 482 483 // compute std and hilbert series 484 if (p_opt) 485 { 486 "std in " + string(Phelp); 487 } 488 intvec hi=hilb(std(qh),1); 489 490 if (add_vars == 0) 491 { 492 // no additional variables were introduced 493 setring P; // can immediately change to original ring 494 // simply compute std with hilbert series in original ring 495 if (p_opt) 496 { 497 "std with hilb in basering"; 498 } 499 if ( w==1 ) { i = std(i,hi); } 500 else { i = std(i,hi,w); } 501 502 } 503 else 504 { 505 // additional variables were introduced 506 // need another intermediate ring 507 list BRlist = ringlist(Phelp); 508 BRlist[3] = list(); 509 for (k=1; k<=size(ord_P)1; k++) 510 { 511 BRlist[3][k] = ord_P[k]; 512 } 513 514 if( IsSimple_P && (add_vars==1) && (size(ord_P)==2) && (ord_P[1][1]=="lp")) 515 { 516 // for lp with at most one parameter, we do not need a block ordering 517 intvec OW = BRlist[3][1][2]; 518 OW = OW,1; 519 BRlist[3][1][2] = OW; // extend block1 by 1 520 BRlist[3][2]=ord_P[2]; // copy block 2 521 } 522 else 523 { 524 if( IsSimple_P && (add_vars==1) && (size(ord_P)==2)&&(ord_P[2][1]=="lp")) 525 { 526 // for lp with at most one parameter, we do not need a block ordering 527 intvec OW = ord_P[2][2]; 528 OW = OW,1; 529 BRlist[3][2]=ord_P[2]; 530 BRlist[3][2][2] = OW; // extend block 2 by 1 531 } 532 else 533 { 534 intvec OW = 1; 535 for (k=2; k<=add_vars; k++) { OW = OW,1; } 536 BRlist[3][size(ord_P)] = list("dp",OW); 537 BRlist[3][size(BRlist[3])+1]=ord_P[size(ord_P)]; 538 } 539 } 540 // change to intermediate ring 541 def Phelp1 = ring(BRlist); 542 setring Phelp1; 543 544 ideal qh = imap(Phelp, qh); 545 kill Phelp; 546 if (p_opt) 547 { 548 "std with hilb in " + string(Phelp1);; 549 } 550 // compute std with Hilbert series 551 if (weight_wp==1) { qh = std(qh, hi);} 552 else { qh = std(qh, hi, weight_wp);} 553 554 // subst 1 for homogenizing var 555 if (!is_homog) 556 { 557 if (p_opt) 558 { 559 "dehomogenization"; 560 } 561 qh = subst(qh, @t@, 1); 562 } 563 564 // go back to original ring 565 setring P; 566 // get ideal, delete zeros and clean SB 567 if (p_opt) 568 { 569 "imap to original ring"; 570 } 571 i = imap(Phelp1,qh); 572 if (p_opt) 573 { 574 "simplification"; 575 } 576 i = simplify(i, 34); 577 kill Phelp1; 578 } 579 580 // cleanup time 581 option(set, opt); 582 if (find(s_opt, "redSB") > 0) 583 { 584 if (p_opt) 585 { 586 "interreduction"; 587 } 588 i=interred(i); 589 } 590 attrib(i, "isSB", 1); 591 return (i); 1117 if ( algorithm=="std"  (algorithm=="stdorslimgb" && char(P)>0) ) 1118 { 1119 i = stdhilb(i,"std"); 1120 } 1121 if ( algorithm=="slimgb"  (algorithm=="stdorslimgb" && char(P)==0) ) 1122 { 1123 i = stdhilb(i,"slimgb"); 1124 } 1125 } 1126 } 1127 1128 // go back to original ring  1129 //The main computation is done. However, the SB coming from a ring with 1130 //extra variables is in general too big. We simplify it befor mapping it 1131 //to the basering. 1132 1133 if (p_opt) 1134 { 1135 "simplification"; 1136 } 1137 1138 if (was_minpoly) 1139 { 1140 ideal Minpoly = imap(P,Minpoly); 1141 attrib(Minpoly,"isSB",1); 1142 i = simplify(NF(i,Minpoly),2); 1143 } 1144 1145 ideal Li = lead(i); 1146 setring P; 1147 ideal Li = imap(Phelp,Li); 1148 Li = simplify(Li,32); 1149 intvec vi; 1150 for (k=1; k<=ncols(Li); k++) 1151 { 1152 vi[k] = Li[k]==0; 1153 } 1154 1155 setring Phelp; 1156 for (k=1; k<=size(i) ;k++) 1157 { 1158 if(vi[k]==1) 1159 { 1160 i[k]=0; 1161 } 1162 } 1163 i = simplify(i,2); 1164 1165 setring P; 1166 if (p_opt) 1167 { 1168 "imap to original ring"; 1169 } 1170 i = imap(Phelp,i); 1171 kill Phelp; 1172 i = simplify(i,34); 1173 1174 // cleanup time 1175 option(set, opt); 1176 if (find(s_opt, "redSB") > 0) 1177 { 1178 if (p_opt) 1179 { 1180 "interreduction"; 1181 } 1182 i=interred(i); 1183 } 1184 attrib(i, "isSB", 1); 1185 return (i); 592 1186 } 593 1187 example 594 { "EXAMPLE: "; echo=2; // LIB "./standard.lib";595 ring r=0,(a,b,c,d),lp;1188 { "EXAMPLE: "; echo=2; 1189 intvec opt = option(get); 596 1190 option(prot); 597 ideal i=a+b+c+d,ab+ad+bc+cd,abc+abd+acd+bcd,abcd1; // cyclic 4 1191 ring r = 0,(a,b,c,d),dp; 1192 ideal i = a+b+c+d,ab+ad+bc+cd,abc+abd+acd+bcd,abcd1; 598 1193 groebner(i); 599 ring rp=(0,a,b),(c,d), lp; 600 ideal i=imap(r,i); 601 groebner(i); 602 option(noprot); 1194 1195 ring s = 0,(a,b,c,d),lp; 1196 ideal i = imap(r,i); 1197 groebner(i,"hilb"); 1198 1199 ring R = (0,a),(b,c,d),lp; 1200 minpoly = a2+1; 1201 ideal i = a+b+c+d,ab+ad+bc+cd,abc+abd+acd+bcd,d2c2b2; 1202 groebner(i,"par2var","slimgb"); 1203 1204 groebner(i,"fglm"); //computes a reduced standard basis 1205 603 1206 if (system("with","MP")) {groebner(i,0);} 604 1207 defined(Standard::groebner_error); 1208 option(set,opt); 605 1209 } 606 1210 … … 1240 1844 list_expression @code{)} 1241 1845 RETURN: the same as the input type of the first argument 1242 PURPOSE: computes the part of a vector space basis of the quotient 1243 defined by the first argument with weighted degree of the monomials 1244 equal to the second argument. The last 1245 argument contains the information about the weights as a list of intvec: 1846 PURPOSE: If @code{I,d,wim} denotes the three arguments then weightKB 1847 computes the weighted degree @code{d} part of a vector space basis 1848 (consisting of monomials) of the quotient ring, resp. of the 1849 quotient module, modulo @code{I} w.r.t. weights given by @code{wim} 1850 The information about the weights is given as a list of two intvec: 1246 1851 @code{wim[1]} weights for all variables (positive), 1247 1852 @code{wim[2]} weights for the module generators. 1248 NOTE: This is a generalisation for the command @code{kbase} with the same first1249 two arguments.1853 NOTE: This is a generalisation for the command @code{kbase} with the same 1854 first two arguments. 1250 1855 SEE ALSO: kbase 1251 1856 EXAMPLE: example weightKB; shows an example … … 1426 2031 weightKB(i, 12, list(w)); 1427 2032 } 2033 ////////////////////////////////////////////////////////////////////////////// 2034 2035 /* 1428 2036 /////////////////////////////////////////////////////////////////////////////// 1429 2037 proc downsizeSB (I, list #) 2038 "USAGE: downsizeSB(I [,l]); I ideal, l list of integers [default: l=0] 2039 RETURN: intvec, say v, with v[j] either 1 or 0. We have v[j]=1 if 2040 leadmonom(I[j]) is divisible by some leadmonom(I[k]) or if 2041 leadmonom(i[j]) == leadmonom(i[k]) and l[j] >= l[k], with k!=j. 2042 PURPOSE: The procedure is applied in a situation where the standard basis 2043 computation in the basering R is done via a conversion through an 2044 overring Phelp with additional variables and where a direct 2045 imap from Phelp to R is too expensive. 2046 Assume Phelp is created by the procedure @code{par2varRing} or 2047 @code{hilbRing} and IPhelp is a SB in Phelp [ with l[j]= 2048 length(IPhelp(j)) or any other integer reflecting the complexity 2049 of a IPhelp[j] ]. Let I = lead(IPhelp) mapped to R and compute 2050 v = downsizeSB(imap(Phelp,I),l) in R. Then, if Ihelp[j] is deleted 2051 for all j with v[j]=1, we can apply imap to the remaining generators 2052 of Ihelp and still get SB in R (in general not minimal). 2053 EXAMPLE: example downsizeSB; shows an example" 2054 { 2055 int k,j; 2056 intvec v,l; 2057 poly M,N,W; 2058 int c=size(I); 2059 if( size(#) != 0 ) 2060 { 2061 if ( typeof(#[1]) == "intvec" ) 2062 { 2063 l = #[1]; 2064 } 2065 else 2066 { 2067 ERROR("2nd argument must be an intvec"); 2068 } 2069 } 2070 2071 l[c+1]=0; 2072 v[c]=0; 2073 2074 j=0; 2075 while(j<c1) 2076 { 2077 j++; 2078 M = leadmonom(I[j]); 2079 if( M != 0 ) 2080 { 2081 for( k=j+1; k<=c; k++ ) 2082 { 2083 N = leadmonom(I[k]); 2084 if( N != 0 ) 2085 { 2086 if( (M==N) && (l[j]>l[k]) ) 2087 { 2088 I[j]=0; 2089 v[j]=1; 2090 break; 2091 } 2092 if( (M==N) && (l[j]<=l[k])  N/M != 0 ) 2093 { 2094 I[k]=0; 2095 v[k]=1; 2096 } 2097 } 2098 } 2099 } 2100 } 2101 return(v); 2102 } 2103 example 2104 { "EXAMPLE:"; echo = 2; 2105 ring r = 0,(x,y,z,t),(dp(3),dp); 2106 ideal i = x+y+z+t,xy+yz+xt+zt,xyz+xyt+xzt+yzt,xyztt4; 2107 ideal Id = std(i); 2108 ideal I = lead(Id); I; 2109 ring S = (0,t),(x,y,z),dp; 2110 downsizeSB(imap(r,I)); 2111 //Id[5] can be deleted, we still have a SB of i in the ring S 2112 2113 ring R = (0,x),(y,z,u),lp; 2114 ideal i = x+y+z+u,xy+xu+yz+zu,xyz+xyu+xzu+yzu,xyzu1; 2115 def Phelp = par2varRing()[1]; 2116 setring Phelp; 2117 ideal IPhelp = std(imap(R,i)); 2118 ideal I = lead(IPhelp); 2119 setring R; 2120 ideal I = imap(Phelp,I); I; 2121 intvec v = downsizeSB(I); v; 2122 } 2123 /////////////////////////////////////////////////////////////////////////// 2124 // PROBLEM: Die Prozedur funktioniert nur fuer Ringe die global bekannt 2125 // sind, also interaktiv, aber nicht aus einer Prozedur. 2126 // Z.B. funktioniert example imapDownsize; nicht 2127 2128 proc imapDownsize (string R, string I) 2129 "SYNTAX: @code{imapDownsize (} string @code{,} string @code{)} *@ 2130 First string must be the string of the name of a ring, second 2131 string must be the string of the name of an object in the ring. 2132 TYPE: same type as the object with name the second string 2133 PURPOSE: maps the object given by the second string to the basering. 2134 If R resp. I are the first resp. second string, then 2135 imapDownsize(R,I) is equivalent to simplify(imap(`R`,`I`),34). 2136 NOTE: imapDownsize is usually faster than imap if `I` is large and if 2137 simplify has a great effect, since the procedure maps only those 2138 generators from `I` which are not killed by simplify(  ,34). 2139 This is useful if `I` is a standard bases for a block ordering of 2140 `R` and if some variables from the last block in `R` are mapped 2141 to parameters. Then the returned result is a standard basis in 2142 the basering. 2143 SEE ALSO: imap, fetch, map 2144 EXAMPLE: example imapDownsize; shows an example" 2145 { 2146 def BR = basering; 2147 int k; 2148 2149 setring `R`; 2150 def @leadI@ = lead(`I`); 2151 int s = ncols(@leadI@); 2152 setring BR; 2153 ideal @leadI@ = simplify(imap(`R`,@leadI@),32); 2154 intvec vi; 2155 for (k=1; k<=s; k++) 2156 { 2157 vi[k] = @leadI@[k]==0; 2158 } 2159 kill @leadI@; 2160 2161 setring `R`; 2162 kill @leadI@; 2163 for (k=1; k<=s; k++) 2164 { 2165 if( vi[k]==1 ) 2166 { 2167 `I`[k]=0; 2168 } 2169 } 2170 `I` = simplify(`I`,2); 2171 2172 setring BR; 2173 return(imap(`R`,`I`)); 2174 } 2175 example 2176 { "EXAMPLE:"; echo = 2; 2177 ring r = 0,(x,y,z,t),(dp(3),dp); 2178 ideal i = x+y+z+t,xy+yz+xt+zt,xyz+xyt+xzt+yzt,xyzt1; 2179 i = std(i); i; 2180 2181 ring s = (0,t),(x,y,z),dp; 2182 imapDownsize("r","i"); //i[5] is omitted since lead(i[2])  lead(i[5]) 2183 } 2184 /////////////////////////////////////////////////////////////////////////////// 2185 //die folgende proc war fuer groebner mit fglm vorgesehen 2186 //um die projektive Dimension korrekt zu berechnen, muss man aber 2187 //voerher ein SB bzgl. einer Gradordnung berechnen und dann homogenisieren. 2188 //Sonst koennen hoeherdimensionale Komponenten in Unendlich entstehen 2189 2190 proc projInvariants(ideal i,list #) 2191 "SYNTAX: @code{projInvariants (} ideal_expression @code{)} @* 2192 @code{projInvariants (} ideal_expression@code{,} list of string_expres sions@code{)} 2193 TYPE: list, say L, with L[1] and L[2] of type int and L[3] of type intvec 2194 PURPOSE: Computes the (projective) dimension (L[1]), degree (L[2]) and the 2195 first Hilbert series (L[3], as intvec) of the homogenized ideal 2196 in the ring given by the procedure @code{hilbRing} with global 2197 ordering dp (resp. wp if the variables have weights >1) 2198 If an argument of type string @code{\"std\"} resp. @code{\"slimgb\"} 2199 is given, the standard basis computatuion uses @code{std} or 2200 @code{slimgb}, otherwise a heuristically chosen method (default) 2201 NOTE: Homogenized means weighted homogenized with respect to the weights 2202 w[i] of the variables var(i) of the basering. The returned dimension, 2203 degree and Hilbertseries are the respective invariants of the 2204 projective variety defined by the homogenized ideal. The dimension 2205 is equal to the (affine) dimension of the ideal in the basering 2206 (degree and Hilbert series make only sense for homogeneous ideals). 2207 SEE ALSO: dim, dmult, hilb 2208 KEYWORDS: dimension, degree, Hilbert function 2209 EXAMPLE: example projInvariants; shows an example" 2210 { 2211 def P = basering; 2212 int p_opt; 2213 string s_opt = option(); 2214 if (find(option(), "prot")) { p_opt = 1; } 2215 2216 // check method and clear denomintors  2217 int k; 2218 string method; 2219 for (k=1; k<=size(#); k++) 2220 { 2221 if (typeof(#[k]) == "string") 2222 { 2223 method = method + "," + #[k]; 2224 } 2225 } 2226 2227 if (npars(P) > 0) //clear denominators of parameters 2228 { 2229 for( k=ncols(i); k>0; k ) 2230 { 2231 i[k]=cleardenom(i[k]); 2232 } 2233 } 2234 2235 // change to hilbRing  2236 list hiRi = hilbRing(i); 2237 intvec W = hiRi[2]; 2238 def Philb = hiRi[1]; //note: Philb is no qring and the predefined 2239 setring Philb; //ideal Id(1) in Philb is homogeneous 2240 int di, de; //for dimension, degree 2241 intvec hi; //for hilbert series 2242 2243 // compute Hilbert function of homogenized ideal in Philb  2244 //Philb has only 1 block. There are three cases 2245 2246 string algorithm; //possibilities: std, slimgb, stdorslimgb 2247 //define algorithm: 2248 if( find(method,"std") && !find(method,"slimgb") ) 2249 { 2250 algorithm = "std"; 2251 } 2252 if( find(method,"slimgb") && !find(method,"std") ) 2253 { 2254 algorithm = "slimgb"; 2255 } 2256 if( find(method,"std") && find(method,"slimgb")  2257 (!find(method,"std") && !find(method,"slimgb")) ) 2258 { 2259 algorithm = "stdorslimgb"; 2260 } 2261 2262 if ( algorithm=="std"  ( algorithm=="stdorslimgb" && char(P)>0 ) ) 2263 { 2264 if (p_opt) {"std in ring " + string(Philb);} 2265 Id(1) = std(Id(1)); 2266 di = dim(Id(1))1; 2267 de = mult(Id(1)); 2268 hi = hilb( Id(1),1,W ); 2269 } 2270 if ( algorithm=="slimgb"  ( algorithm=="stdorslimgb" && char(P)==0 ) ) 2271 { 2272 if (p_opt) {"slimgb in ring " + string(Philb);} 2273 Id(1) = slimgb(Id(1)); 2274 di = dim( Id(1) ); 2275 if (di > 1) 2276 { 2277 di = di1; 2278 } 2279 de = mult( Id(1) ); 2280 hi = hilb( Id(1),1,W ); 2281 } 2282 kill Philb; 2283 list L = di,de,hi; 2284 return(L); 2285 } 2286 example 2287 { "EXAMPLE:"; echo = 2; 2288 ring r = 32003,(x,y,z),lp; 2289 ideal i = y2xz,x2z; 2290 projInvariants(i); 2291 2292 ring R = (0),(x,y,z,u,v),lp; 2293 //minpoly = x2+1; 2294 ideal i = x2+1,x2+y+z+u+v,xyzuv1; 2295 projInvariants(i); 2296 qring S =std(x2+1); 2297 ideal i = imap(R,i); 2298 projInvariants(i); 2299 } 2300 2301 */
Note: See TracChangeset
for help on using the changeset viewer.