Singular http://www.singular.unikl.de/forum/ 

Strange timing result... http://www.singular.unikl.de/forum/viewtopic.php?f=10&t=1291 
Page 1 of 1 
Author:  GertMartin Greuel [ Thu Aug 11, 2005 5:31 pm ] 
Post subject:  Strange timing result... 
>Dear Singular Team, >this run was under version 123 (February 1999), so the >info is out of date, but I'm curious about it nowand >will run it under v2.0 (Solaris) after we download and >install it. The following run took 4 days: > >ring rr = 0, (a,b,c,d,e,f,g,h,i,j,w,z), lp; >ideal i15 = 1  c*d + b*e,1  g*h + f*i, > (b*c*f*h) + b^2*g*h  c^2*h^2  b*e*f*i + b*d*g*i + > b*c*h*i  c*e*h*i + c*d*i^2 + w, > a + b*c*f^2  b^2*f*g + b*e*f*g  b*d*g^2 + c^2*f*h + > c*e*g*h  b*c*f*i  c*d*g*i, > (c*d*f*h) + b*d*g*h  c*e*h^2  d*e*f*i + d^2*g*i + > b*e*h*i  e^2*h*i + d*e*i^2, > 1 + c*d*f^2*w  b*d*f*g*w + d*e*f*g*w  d^2*g^2*w + > c*e*f*h*w + e^2*g*h*w  b*e*f*i*w  d*e*g*i*w, > a*w  j*z + j*w^2*z  a*w*z^2,d*j + b*z  b*f*z  c*h*z, > (b*g)  c*i  d*j^2  b*j*z + e*j*z + c*z^2, > d  d*f*z^2  e*h*z^2,(d*j) + e*z  d*g*z  e*i*z, > h*j + f*z  b*f^2*z  d*f*g*z  c*f*h*z  e*g*h*z, > (b*f*g)  d*g^2  c*f*i  e*g*i  h*j^2  f*j*z + > i*j*z + g*z^2,h  b*f*h*z^2  c*h^2*z^2  > d*f*i*z^2  e*h*i*z^2, > (h*j)  b*g*h*z + i*z  d*g*i*z  c*h*i*z  e*i^2*z; >option(prot); >option(redSB); >ideal gi15 = groebner(i15); >size(gi15); > >The 15 polynomials (from a knottheory problem) were >generated by Mathematica, hence the odd spacing and commas >in the midst of lines. >The first entry, w3z4w2z8+w2z6+w2z4+w2z2w2+wz8wz6wz4wz2+wz4, >gives the soughtfor relationship between z and w. >However, then I (i) first run this under "dp", and then >(ii), /fetch/ the resulting 452entry GB into the ring >under "lp" as above, the computation halts within 2 hours! >My surprise is that I had the impression that "groebner" >/always/ worked this way: first find a >basis under "dp" and then do linear transformations to get >one for the desired ordering. The only difference I see >is that in the latter run, I did not tell Singular that >the 452entry basis was a GB under "dp". > >I'll see if I can reproduce this disparity of timing >under version 2.0. Is the above difference expected >after all? Your example is quite interesting. Let me explain. 'groebner' is a command which chooses a strategy depending on the basering and on the input, which we think is the best in the majority of cases. In your example, Singular first homogenizes this ideal with an extra variable, computes the std with dp, computes the hilbert series and then takes the homogenized original ideal as input to compute std with lp but discarding critical pairs predicted by the hilbert series. Then the extra variable is set to 1 and the result is simplified. Although this is quite involved it has turned out to be superior in most of the cases we are interested in. There are exceptions as your example shows, the dpGB becomes very big and, apparently, the hilbert driven discarding does not happen in this case. This will not change in 2.0. The linear algebra method can be used with fglm or stdfglm. So, you did something completely different. It is well known, that different systems of generators of a given ideal can lead to very different timings, but usually the smaller are the better ones. This is also the case with your example.(There are very few exceptions). In addition, your example is one of the very few cases, where a lpGB is much easier to compute than a dpGB. Indeed, take your ring with lp and your ideal as they are and just do std(i15), but without option(redSB)!! The Groebner basis has then 37 elements and the first one is the one your are looking for. Singular 2.0 needs for this 6.13 sec (!) on AMD Athlon with 700 Mhz, Singular 1.2.0 needs about 270 sec for the same computation. I guess you want to eliminate the variables a ... j. An alternative is to use the elimination ordering ring rr = 0, (a,b,c,d,e,f,g,h,i,j,w,z),(dp(10),dp); which is usually faster than lp, or take any ordering and than the command ideal ei15 = eliminate(i15,abcdefghij); (which then also depends on the choosen ordering) For your example lp seems to be the fastest. GertMartin Greuel (Singular team) email: greuel@mathematik.unikl.de Posted in old Singular Forum on: 20010515 12:53:53+02 
Page 1 of 1  All times are UTC + 1 hour [ DST ] 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ 