>Dear Singular Team,

>this run was under version 1-2-3 (February 1999), so the

>info is out of date, but I'm curious about it now---and

>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 knot-theory problem) were

>generated by Mathematica, hence the odd spacing and commas

>in the midst of lines.

>The first entry, w3z4-w2z8+w2z6+w2z4+w2z2-w2+wz8-wz6-wz4-wz2+w-z4,

>gives the sought-for relationship between z and w.

>However, then I (i) first run this under "dp", and then

>(ii), /fetch/ the resulting 452-entry 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 452-entry 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 dp-GB

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 lp-GB is much easier to compute than a dp-GB.

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.

Gert-Martin Greuel (Singular team)

email:

greuel@mathematik.uni-kl.dePosted in old Singular Forum on: 2001-05-15 12:53:53+02