Singular

>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.de
Posted in old Singular Forum on: 2001-05-15 12:53:53+02