CoCoA » CoCoA-5

Here is Mario's first example: I have used coeffs in ZZ/(101) but the original was over QQ

use ZZ/(101)[c[0..23]];
NumVars := 24;
L := [
c[0] +c[1]*c[11] -c[1]*c[21] -c[2]*c[17] -c[3]*c[9] +c[5]*c[10] +c[9]^2,
-c[1]*c[22] +c[2]*c[11] -c[2]*c[18] -c[3]*c[10] +c[6]*c[10] +c[9]*c[10],
-c[1]*c[23] -c[2]*c[19] +c[7]*c[10] -c[8] +c[9]*c[11],
c[0]*c[11] -c[1]*c[20] -c[2]*c[16] -c[3]*c[8] +c[4]*c[10] +c[8]*c[9],
c[1]*c[7] -c[1]*c[17] -c[2]*c[13] -c[3]*c[5] +c[5]*c[6] +c[5]*c[9],
c[0] -c[1]*c[18] +c[2]*c[7] -c[2]*c[14] -c[3]*c[6] +c[5]*c[10] +c[6]^2,
-c[1]*c[19] -c[2]*c[15] -c[4] +c[5]*c[11] +c[6]*c[7],
c[0]*c[7] -c[1]*c[16] -c[2]*c[12] -c[3]*c[4] +c[4]*c[6] +c[5]*c[8],
c[1]*c[19] +c[4] +c[5]*c[18] -c[5]*c[21] -c[6]*c[17] -c[7]*c[9] +c[9]*c[17],
c[2]*c[19] -c[5]*c[22] -c[7]*c[10] +c[10]*c[17],
c[3]*c[19] -c[5]*c[23] -c[6]*c[19] -c[7]*c[11] +c[7]*c[18] +c[11]*c[17] -c[16],
c[0]*c[19] +c[4]*c[18] -c[5]*c[20] -c[6]*c[16] -c[7]*c[8] +c[8]*c[17],
c[1]*c[15] -c[5]*c[7] +c[5]*c[14] -c[5]*c[17] -c[6]*c[13] +c[9]*c[13],
c[2]*c[15] +c[4] -c[5]*c[18] -c[6]*c[7] +c[10]*c[13],
c[3]*c[15] -c[5]*c[19] -c[6]*c[15] -c[7]^2 +c[7]*c[14] +c[11]*c[13] -c[12],
c[0]*c[15] -c[4]*c[7] +c[4]*c[14] -c[5]*c[16] -c[6]*c[12] +c[8]*c[13],
c[1]*c[23] +c[5]*c[22] +c[8] -c[9]*c[11] -c[10]*c[17],
c[2]*c[23] +c[6]*c[22] -c[9]*c[22] -c[10]*c[11] -c[10]*c[18] +c[10]*c[21],
c[3]*c[23] +c[7]*c[22] -c[9]*c[23] -c[10]*c[19] -c[11]^2 +c[11]*c[21] -c[20],
c[0]*c[23] +c[4]*c[22] -c[8]*c[11] +c[8]*c[21] -c[9]*c[20] -c[10]*c[16],
c[1]*c[19] -c[5]*c[11] +c[5]*c[18] -c[10]*c[13],
c[2]*c[19] -c[6]*c[11] +c[6]*c[18] +c[8] -c[9]*c[18] -c[10]*c[14] +c[10]*c[17],
c[3]*c[19] -c[7]*c[11] +c[7]*c[18] -c[9]*c[19] -c[10]*c[15] +c[11]*c[17] -c[16],
c[0]*c[19] -c[4]*c[11] +c[4]*c[18] +c[8]*c[17] -c[9]*c[16] -c[10]*c[12],
c[5]*c[19] -c[9]*c[15] +c[12] +c[13]*c[18] -c[13]*c[21] -c[14]*c[17] +c[17]^2,
c[6]*c[19] -c[10]*c[15] -c[13]*c[22] -c[16] +c[17]*c[18],
c[7]*c[19] -c[11]*c[15] -c[13]*c[23] -c[14]*c[19] +c[15]*c[18] +c[17]*c[19],
c[4]*c[19] -c[8]*c[15] +c[12]*c[18] -c[13]*c[20] -c[14]*c[16] +c[16]*c[17],
c[5]*c[23] -c[9]*c[19] +c[13]*c[22] +c[16] -c[17]*c[18],
c[6]*c[23] -c[10]*c[19] +c[14]*c[22] -c[17]*c[22] -c[18]^2 +c[18]*c[21] -c[20],
c[7]*c[23] -c[11]*c[19] +c[15]*c[22] -c[17]*c[23] -c[18]*c[19] +c[19]*c[21],
c[4]*c[23] -c[8]*c[19] +c[12]*c[22] -c[16]*c[18] +c[16]*c[21] -c[17]*c[20]
];
I := ideal(L);

t0 := CpuTime();
J := radical(I);
println "radical time: ", TimeFrom(t0);

NOTE: computing GBasis over ZZ/(101) took about 3.9s on Kassel Linux box; over QQ it took about 7.8s

Here is Mario's second example: I have chosen ZZ/(101) for the coeffs, but the original was over QQ

use ZZ/(101)[c[0..15]];
NumVars := 16;
L := [
-c[1]*c[5]*c[7]^2 +c[1]*c[5]*c[11] +2*c[1]*c[6]*c[7] -c[1]*c[7]^2*c[15] -c[1]*c[7]*c[9] +c[1]*c[10] -c[1]*c[11]*c[15],
-c[1]*c[4] -c[1]*c[5]^2*c[7] +c[1]*c[5]*c[6] -c[1]*c[7]^2*c[13] -c[1]*c[11]*c[13],
c[1]*c[4]*c[7] -c[1]*c[5]*c[6]*c[7] +c[1]*c[5]*c[10] +c[1]*c[6]^2 -c[1]*c[6]*c[9] -c[1]*c[7]^2*c[14] +c[1]*c[8] -c[1]*c[11]*c[14],
-c[1]*c[4]*c[5]*c[7] +c[1]*c[4]*c[6] -c[1]*c[4]*c[9] +c[1]*c[5]*c[8] -c[1]*c[7]^2*c[12] -c[1]*c[11]*c[12],
c[5]*c[7]^2 -c[5]*c[11] -2*c[6]*c[7] +c[7]^2*c[15] +c[7]*c[9] -c[10] +c[11]*c[15],
c[4] +c[5]^2*c[7] -c[5]*c[6] +c[7]^2*c[13] +c[11]*c[13],
-c[4]*c[7] +c[5]*c[6]*c[7] -c[5]*c[10] -c[6]^2 +c[6]*c[9] +c[7]^2*c[14] -c[8] +c[11]*c[14],
c[4]*c[5]*c[7] -c[4]*c[6] +c[4]*c[9] -c[5]*c[8] +c[7]^2*c[12] +c[11]*c[12],
c[1]*c[4] +c[1]*c[5]^2*c[7] -c[1]*c[5]*c[6] +c[1]*c[7]^2*c[13] +c[1]*c[11]*c[13],
c[1]*c[5]^3 -c[1]*c[5]^2*c[15] +2*c[1]*c[5]*c[7]*c[13] +c[1]*c[5]*c[14] -c[1]*c[6]*c[13] +c[1]*c[9]*c[13] -c[1]*c[12],
-c[1]*c[4]*c[5] +c[1]*c[4]*c[15] +c[1]*c[5]^2*c[6] -c[1]*c[5]*c[6]*c[15] +c[1]*c[5]*c[7]*c[14] +c[1]*c[6]*c[7]*c[13] -c[1]*c[7]*c[12] +c[1]*c[10]*c[13],
c[1]*c[4]*c[5]^2 -c[1]*c[4]*c[5]*c[15] +c[1]*c[4]*c[7]*c[13] +c[1]*c[4]*c[14] +c[1]*c[5]*c[7]*c[12] -c[1]*c[6]*c[12] +c[1]*c[8]*c[13],
-c[4] -c[5]^2*c[7] +c[5]*c[6] -c[7]^2*c[13] -c[11]*c[13],
-c[5]^3 +c[5]^2*c[15] -2*c[5]*c[7]*c[13] -c[5]*c[14] +c[6]*c[13] -c[9]*c[13] +c[12],
c[4]*c[5] -c[4]*c[15] -c[5]^2*c[6] +c[5]*c[6]*c[15] -c[5]*c[7]*c[14] -c[6]*c[7]*c[13] +c[7]*c[12] -c[10]*c[13],
-c[4]*c[5]^2 +c[4]*c[5]*c[15] -c[4]*c[7]*c[13] -c[4]*c[14] -c[5]*c[7]*c[12] +c[6]*c[12] -c[8]*c[13]];
I := ideal(L);
t0 := CpuTime();
J := radical(I);
println "radical time: ", TimeFrom(t0);

Note: GBasis(I) took about 0.86s on my fixed Linux box; GBasis over QQ took about 1.9s, printed GBasis is about 1.3Mbyte

I've just added a first check if the ideal is zero-dimensional.
Thanks to our new MinPoly that is much faster.
This can probably be applied in the recursion (when the ideal gets 0-dimensional wrt the indets involved)... but, er, ehm, touching that code requires courage.

The first example (with 24 indets) was consuming over 7Gbytes of RAM after 15 hours of CPU, so I killed the process (my computer was practically unusuable this morning).

Mario reports that Singular managed to compute the answer in about 15 hours without consuming too much memory.

Here is another example: CoCoA-5 took about 760s, while Singular took about 0.6s (more than 1000 times faster).

use QQ[c[0..19]];
L :=[
c[1]*c[6]*c[13] +c[1]*c[8]*c[11] -c[1]*c[8]*c[13]*c[18] -c[1]*c[9]*c[13]^2 -c[1]*c[12] -c[1]*c[13]*c[19] +c[1]*c[14]*c[18] +c[1]*c[16] -c[1]*c[18]^2 +c[3]*c[6]*c[11] -c[3]*c[6]*c[13]*c[18] -c[3]*c[7]*c[13]^2 -c[3]*c[8]*c[11]*c[18] +c[3]*c[8]*c[13]^2*c[19] -c[3]*c[8]*c[13]*c[16] +c[3]*c[8]*c[13]*c[18]^2 -2*c[3]*c[9]*c[11]*c[13] +c[3]*c[9]*c[13]^2*c[14] +c[3]*c[9]*c[13]^2*c[18] -c[3]*c[10] -c[3]*c[11]*c[19] +c[3]*c[12]*c[18] -c[3]*c[13]*c[17] +2*c[3]*c[13]*c[18]*c[19] +c[3]*c[14]*c[16] -c[3]*c[14]*c[18]^2 -2*c[3]*c[16]*c[18] +c[3]*c[18]^3,
c[1]*c[7]*c[13] -c[1]*c[8]*c[13]*c[19] +c[1]*c[9]*c[11] -c[1]*c[9]*c[13]*c[14] +c[1]*c[17] -c[1]*c[18]*c[19] +c[3]*c[5]*c[13] -c[3]*c[6]*c[13]*c[19] +c[3]*c[7]*c[11] -c[3]*c[7]*c[13]*c[14] -c[3]*c[8]*c[11]*c[19] +c[3]*c[8]*c[13]*c[14]*c[19] -c[3]*c[8]*c[13]*c[17] +c[3]*c[8]*c[13]*c[18]*c[19] -c[3]*c[9]*c[11]*c[14] -c[3]*c[9]*c[12]*c[13] +c[3]*c[9]*c[13]^2*c[19] +c[3]*c[9]*c[13]*c[14]^2 +c[3]*c[13]*c[19]^2 +c[3]*c[15] -c[3]*c[16]*c[19] -c[3]*c[17]*c[18] +c[3]*c[18]^2*c[19],
c[1]*c[6]*c[11] -c[1]*c[8]*c[13]*c[16] -c[1]*c[9]*c[11]*c[13] -c[1]*c[10] -c[1]*c[11]*c[19] +c[1]*c[14]*c[16] -c[1]*c[16]*c[18] -c[3]*c[6]*c[13]*c[16] -c[3]*c[7]*c[11]*c[13] +c[3]*c[8]*c[11]*c[13]*c[19] -c[3]*c[8]*c[11]*c[16] +c[3]*c[8]*c[13]*c[16]*c[18] -c[3]*c[9]*c[11]^2 +c[3]*c[9]*c[11]*c[13]*c[14] +c[3]*c[9]*c[13]^2*c[16] -c[3]*c[11]*c[17] +c[3]*c[11]*c[18]*c[19] +c[3]*c[12]*c[16] +c[3]*c[13]*c[16]*c[19] -c[3]*c[14]*c[16]*c[18] -c[3]*c[16]^2 +c[3]*c[16]*c[18]^2,
c[1]*c[5]*c[13] +c[1]*c[7]*c[11] -c[1]*c[8]*c[13]*c[17] -c[1]*c[9]*c[12]*c[13] -c[1]*c[12]*c[19] +c[1]*c[14]*c[17] +c[1]*c[15] -c[1]*c[17]*c[18] +c[3]*c[5]*c[11] -c[3]*c[6]*c[13]*c[17] -c[3]*c[7]*c[12]*c[13] -c[3]*c[8]*c[11]*c[17] +c[3]*c[8]*c[12]*c[13]*c[19] -c[3]*c[8]*c[13]*c[15] +c[3]*c[8]*c[13]*c[17]*c[18] -c[3]*c[9]*c[10]*c[13] -c[3]*c[9]*c[11]*c[12] +c[3]*c[9]*c[12]*c[13]*c[14] +c[3]*c[9]*c[13]^2*c[17] -c[3]*c[10]*c[19] +c[3]*c[12]*c[18]*c[19] +c[3]*c[13]*c[17]*c[19] +c[3]*c[14]*c[15] -c[3]*c[14]*c[17]*c[18] -c[3]*c[15]*c[18] -c[3]*c[16]*c[17] +c[3]*c[17]*c[18]^2,
c[1]*c[5]*c[11] -c[1]*c[8]*c[13]*c[15] -c[1]*c[9]*c[10]*c[13] -c[1]*c[10]*c[19] +c[1]*c[14]*c[15] -c[1]*c[15]*c[18] -c[3]*c[6]*c[13]*c[15] -c[3]*c[7]*c[10]*c[13] +c[3]*c[8]*c[10]*c[13]*c[19] -c[3]*c[8]*c[11]*c[15] +c[3]*c[8]*c[13]*c[15]*c[18] -c[3]*c[9]*c[10]*c[11] +c[3]*c[9]*c[10]*c[13]*c[14] +c[3]*c[9]*c[13]^2*c[15] -c[3]*c[10]*c[17] +c[3]*c[10]*c[18]*c[19] +c[3]*c[12]*c[15] +c[3]*c[13]*c[15]*c[19] -c[3]*c[14]*c[15]*c[18] -c[3]*c[15]*c[16] +c[3]*c[15]*c[18]^2,
-c[6]*c[13] -c[8]*c[11] +c[8]*c[13]*c[18] +c[9]*c[13]^2 +c[12] +c[13]*c[19] -c[14]*c[18] -c[16] +c[18]^2,
-c[7]*c[13] +c[8]*c[13]*c[19] -c[9]*c[11] +c[9]*c[13]*c[14] -c[17] +c[18]*c[19],
-c[6]*c[11] +c[8]*c[13]*c[16] +c[9]*c[11]*c[13] +c[10] +c[11]*c[19] -c[14]*c[16] +c[16]*c[18],
-c[5]*c[13] -c[7]*c[11] +c[8]*c[13]*c[17] +c[9]*c[12]*c[13] +c[12]*c[19] -c[14]*c[17] -c[15] +c[17]*c[18],
-c[5]*c[11] +c[8]*c[13]*c[15] +c[9]*c[10]*c[13] +c[10]*c[19] -c[14]*c[15] +c[15]*c[18],
-c[1]*c[7]*c[13] +c[1]*c[8]*c[13]*c[19] -c[1]*c[9]*c[11] +c[1]*c[9]*c[13]*c[14] -c[1]*c[17] +c[1]*c[18]*c[19] -c[3]*c[5]*c[13] +c[3]*c[6]*c[13]*c[19] -c[3]*c[7]*c[11] +c[3]*c[7]*c[13]*c[14] +c[3]*c[8]*c[11]*c[19] -c[3]*c[8]*c[13]*c[14]*c[19] +c[3]*c[8]*c[13]*c[17] -c[3]*c[8]*c[13]*c[18]*c[19] +c[3]*c[9]*c[11]*c[14] +c[3]*c[9]*c[12]*c[13] -c[3]*c[9]*c[13]^2*c[19] -c[3]*c[9]*c[13]*c[14]^2 -c[3]*c[13]*c[19]^2 -c[3]*c[15] +c[3]*c[16]*c[19] +c[3]*c[17]*c[18] -c[3]*c[18]^2*c[19],
c[1]*c[5] -c[1]*c[6]*c[19] -c[1]*c[7]*c[14] +c[1]*c[7]*c[18] +c[1]*c[8]*c[14]*c[19] -c[1]*c[8]*c[17] -c[1]*c[9]*c[12] +c[1]*c[9]*c[13]*c[19] +c[1]*c[9]*c[14]^2 -c[1]*c[9]*c[14]*c[18] +c[1]*c[9]*c[16] +c[1]*c[19]^2 -c[3]*c[5]*c[14] +c[3]*c[5]*c[18] +c[3]*c[6]*c[14]*c[19] -c[3]*c[6]*c[17] -c[3]*c[7]*c[12] +c[3]*c[7]*c[13]*c[19] +c[3]*c[7]*c[14]^2 -c[3]*c[7]*c[14]*c[18] +c[3]*c[7]*c[16] +c[3]*c[8]*c[12]*c[19] -c[3]*c[8]*c[13]*c[19]^2 -c[3]*c[8]*c[14]^2*c[19] +c[3]*c[8]*c[14]*c[17] -c[3]*c[8]*c[15] -c[3]*c[9]*c[10] +c[3]*c[9]*c[11]*c[19] +2*c[3]*c[9]*c[12]*c[14] -c[3]*c[9]*c[12]*c[18] -2*c[3]*c[9]*c[13]*c[14]*c[19] +c[3]*c[9]*c[13]*c[17] -c[3]*c[9]*c[14]^3 +c[3]*c[9]*c[14]^2*c[18] -c[3]*c[9]*c[14]*c[16] -c[3]*c[14]*c[19]^2 +2*c[3]*c[17]*c[19] -c[3]*c[18]*c[19]^2,
-c[1]*c[7]*c[11] +c[1]*c[8]*c[11]*c[19] +c[1]*c[9]*c[11]*c[14] -c[1]*c[9]*c[11]*c[18] +c[1]*c[9]*c[13]*c[16] -c[1]*c[15] +c[1]*c[16]*c[19] -c[3]*c[5]*c[11] +c[3]*c[6]*c[11]*c[19] +c[3]*c[7]*c[11]*c[14] -c[3]*c[7]*c[11]*c[18] +c[3]*c[7]*c[13]*c[16] -c[3]*c[8]*c[11]*c[14]*c[19] +c[3]*c[8]*c[11]*c[17] -c[3]*c[8]*c[13]*c[16]*c[19] +c[3]*c[9]*c[11]*c[12] -c[3]*c[9]*c[11]*c[13]*c[19] -c[3]*c[9]*c[11]*c[14]^2 +c[3]*c[9]*c[11]*c[14]*c[18] -c[3]*c[9]*c[13]*c[14]*c[16] -c[3]*c[11]*c[19]^2 +c[3]*c[16]*c[17] -c[3]*c[16]*c[18]*c[19],
c[1]*c[5]*c[18] -c[1]*c[6]*c[17] -c[1]*c[7]*c[12] +c[1]*c[7]*c[16] +c[1]*c[8]*c[12]*c[19] -c[1]*c[8]*c[15] -c[1]*c[9]*c[10] +c[1]*c[9]*c[12]*c[14] -c[1]*c[9]*c[12]*c[18] +c[1]*c[9]*c[13]*c[17] +c[1]*c[17]*c[19] -c[3]*c[5]*c[12] +c[3]*c[5]*c[16] +c[3]*c[6]*c[12]*c[19] -c[3]*c[6]*c[15] -c[3]*c[7]*c[10] +c[3]*c[7]*c[12]*c[14] -c[3]*c[7]*c[12]*c[18] +c[3]*c[7]*c[13]*c[17] +c[3]*c[8]*c[10]*c[19] -c[3]*c[8]*c[12]*c[14]*c[19] +c[3]*c[8]*c[12]*c[17] -c[3]*c[8]*c[13]*c[17]*c[19] +c[3]*c[9]*c[10]*c[14] -c[3]*c[9]*c[10]*c[18] +c[3]*c[9]*c[11]*c[17] +c[3]*c[9]*c[12]^2 -c[3]*c[9]*c[12]*c[13]*c[19] -c[3]*c[9]*c[12]*c[14]^2 +c[3]*c[9]*c[12]*c[14]*c[18] -c[3]*c[9]*c[12]*c[16] -c[3]*c[9]*c[13]*c[14]*c[17] +c[3]*c[9]*c[13]*c[15] -c[3]*c[12]*c[19]^2 +c[3]*c[15]*c[19] +c[3]*c[17]^2 -c[3]*c[17]*c[18]*c[19],
c[1]*c[5]*c[16] -c[1]*c[6]*c[15] -c[1]*c[7]*c[10] +c[1]*c[8]*c[10]*c[19] +c[1]*c[9]*c[10]*c[14] -c[1]*c[9]*c[10]*c[18] +c[1]*c[9]*c[13]*c[15] +c[1]*c[15]*c[19] -c[3]*c[5]*c[10] +c[3]*c[6]*c[10]*c[19] +c[3]*c[7]*c[10]*c[14] -c[3]*c[7]*c[10]*c[18] +c[3]*c[7]*c[13]*c[15] -c[3]*c[8]*c[10]*c[14]*c[19] +c[3]*c[8]*c[10]*c[17] -c[3]*c[8]*c[13]*c[15]*c[19] +c[3]*c[9]*c[10]*c[12] -c[3]*c[9]*c[10]*c[13]*c[19] -c[3]*c[9]*c[10]*c[14]^2 +c[3]*c[9]*c[10]*c[14]*c[18] -c[3]*c[9]*c[10]*c[16] +c[3]*c[9]*c[11]*c[15] -c[3]*c[9]*c[13]*c[14]*c[15] -c[3]*c[10]*c[19]^2 +c[3]*c[15]*c[17] -c[3]*c[15]*c[18]*c[19],
c[7]*c[13] -c[8]*c[13]*c[19] +c[9]*c[11] -c[9]*c[13]*c[14] +c[17] -c[18]*c[19],
-c[5] +c[6]*c[19] +c[7]*c[14] -c[7]*c[18] -c[8]*c[14]*c[19] +c[8]*c[17] +c[9]*c[12] -c[9]*c[13]*c[19] -c[9]*c[14]^2 +c[9]*c[14]*c[18] -c[9]*c[16] -c[19]^2,
c[7]*c[11] -c[8]*c[11]*c[19] -c[9]*c[11]*c[14] +c[9]*c[11]*c[18] -c[9]*c[13]*c[16] +c[15] -c[16]*c[19],
-c[5]*c[18] +c[6]*c[17] +c[7]*c[12] -c[7]*c[16] -c[8]*c[12]*c[19] +c[8]*c[15] +c[9]*c[10] -c[9]*c[12]*c[14] +c[9]*c[12]*c[18] -c[9]*c[13]*c[17] -c[17]*c[19],
     -c[5]*c[16] +c[6]*c[15] +c[7]*c[10] -c[8]*c[10]*c[19] -c[9]*c[10]*c[14] +c[9]*c[10]*c[18] -c[9]*c[13]*c[15] -c[15]*c[19]];

I := ideal(L);
t0 := CpuTime();
GB := GBasis(I);
println "GBasis time: ", TimeFrom(t0);

t0 := CpuTime();
$radical.RADICAL_OUT:=true; // activate some VERBOSE logs
radI := radical(I);
println "radical time: ", TimeFrom(t0);

I have found the (a?) slow step: there is a call to saturate(I, ideal(RingElem(RingOf(G),G1))) taking a long time.

I have just tried the last example (916s) from the comment above modulo 32003 and modulo 29641. The computation was almost instant. Can't we just compute the whole radical modulo p (and then lift to QQ)? How to detect/handle bad primes?

Here is another slow example: (about 450s on my computer)

I := ideal(x^5 +y^5 +x*y^2*z^2 +x*y^2,  x^3*y^2 +y^4*z +x^2*y*z^2 +y^4,  z^5 +x^2*y^2 +y^2*z^2 +x*y^2);

And the one below took almost 1800s on my computer:

I = ideal(z^5 +x^3*z +x^2*y*z,  x^5 +x^2*y*z^2 +y^4,  x^5 +y^5 +y^4*z)
LT(radI) = ideal(y^3*z,  x^2*y*z,  x^3*z,  y^4,  x*y^3,  x^2*y^2,  x^3*y,  y^2*z^3,  x*z^4,  y*z^4,  z^5,  x*y^2*z,  x^5,  x^2*z^2,  x*y*z^2)
time = 1786.6
size = 285

I have noticed that when I interrupt the very long radical computations the interpreter indicates that it was computing the multiplicity (which involves computing a GBasis). A quick check suggests that this happens for all these examples.

This may help us design a (practically) faster algorithm.

-----------------------------
>>>  CoCoA-5 interrupted  <<<
-----------------------------

--> WHERE: at line 191 (column 26) of maximal.cpkg5
-->       d := multiplicity(P/J);
-->                          ^

Singular appears not to compute a GBasis for the radical.

For instance, in the first example in comment 11, Singular gives an answer in about 0.15s: it adjoins two generators to the ideal. Asking Singular to compute the GBasis of that ideal (using the command groebner) took about 11mins. CoCoA obtains the GBasis for the radical in about 7mins; so if you want a GBasis for the radical CoCoA is actually faster.

(just to know, when testing)
All these examples in "c" have positive dimension.
All these examples in "x" are 0-dimensional.

We have another funny problem: MinPoly is too fast ;-)
The timeout for GBasis depends only on the time spent in MinPoly, so this superquick example

/**/  use R ::= QQ[x,y];
/**/  I := ideal(x-1, y)^3;
/**/  radical(I);
ideal(x^3 -3*x^2 +3*x -1,  x^2*y -2*x*y +y,  x^2*y -2*x*y +y,  x*y^2 -y^2,  x^2*y -2*x*y +y,  x*y^2 -y^2,  x*y^2 -y^2,  y^3,  y,  x -1)

I have just tried modifying the code, but it does not work as expected.

In SparsePolyOps-Ideal0Dim.C around line 367, there is if (i==0) break; // Seidenberg
This seems to prevent computation of the final GBasis, even if I set large (0.1s) timeout.

The formula for timeout_GB on line looks far too complicated (KISS?)
My simple idea was just to add say 0.1 to the actual measured time: if minpoly is fast,
this gives a small amount of time for GB to finish; if minpoly is not fast, then it makes
little difference.

ADDENDUM I tried commenting out the "Seidenberg" line, but it made no difference (even with timeout of 10s). There must be a bug!

John Abbott wrote:

My simple idea was just to add say 0.1 to the actual measured time: if minpoly is fast,
this gives a small amount of time for GB to finish; if minpoly is not fast, then it makes
little difference.

Done it, added 0.1s.
I also modified the code so that the generators are taken for the GBases effectively computed.
Last one (the one in x) is not computed because adding x-1 guarantees the output to be radical.

ideal(y,  x^3 -3*x^2 +3*x -1,  x -1)

Anna Maria Bigatti wrote:

John Abbott wrote:

My simple idea was just to add say 0.1 to the actual measured time: if minpoly is fast,
this gives a small amount of time for GB to finish; if minpoly is not fast, then it makes
little difference.

Done it, added 0.1s.
I also modified the code so that the generators are taken for the GBases effectively computed.
Last one (the one in x) is not computed because adding x-1 guarantees the output to be radical.
[...]

Now the value is 0.5s, 0.1 was too little (see Slug #1375)

After the change mentioned in issue #1375, the examples in comment 13 are now satisfactorily quick. The example in comment 21 is fine now.

• (1) is still slow: radical is fast-ish, but ReducedGBasis slow. Gets slower: I stopped RGB computation after 575s :-(
• (2) now reasonably fast
• (3) now reasonably fast
• (4) now reasonably fast

As reported in the previous comment, example 1 was still a problem. I increased the extra time (to 2.5s), then the computation became fast: radical (0.8s) and RGB (instant). Presumably increasing to just 0.8s would have been sufficient.

What is the correct way to handle this situation?

The examples in comment 13 are now reasonably quick.
The one in comment 2 is still slow -- cause is trouble with multivariate GCD over finite field (see issue #1581).

When I interrupt the computation after about a minute this is what I get:

-----------------------------
>>>  CoCoA-5 interrupted  <<<
-----------------------------

--> WHERE: at line 152 (column 48) of radical.cpkg5
--> ... ideal([rad(K) | K In gens(I)]) + ideal([rad(K) | K In GBasis(I)]);
-->                                             ^^^^^^