Slug #1025
Example of slow LEX GBasis computation
Description
I am putting this example here just not to lose it:
use QQ[x,y,z],lex; //use ZZ/(32003)[x,y,z],lex; SetVerbosityLevel(2000); I := ideal(-x^2*y -x +z^3, -x^2*y +x^2*z +y^2, x^3 +y^3); // --> 78s t0 := CpuTime(); RGB := ReducedGBasis(I); println "RGB time: ", TimeFrom(t0); indent(RGB);
The final RGB is not too bad, but one of the polys produced during the computation has coeffs almost 300000 digits long! The computation mod p is instant.
History
#1
Updated by John Abbott about 7 years ago
Updated by Send the output to a file! (over 40Mbytes)
Biggest coeffs are from the 3rd last polynomial; but several others are large too.
#2
Updated by John Abbott about 7 years ago
Here are some simple-looking ideals whose lex GBs cannot be computed (in reasonable time) by CoCoA-5.1.5:
use QQ[x,y,z],lex; I := ideal(2*x*y^2 +x +z^3, 2*x^2 +x*y -y^3, 2*x^3 -x*z +2*y); // --> > 5400 s and >3.3Gbyte I := ideal(-x^4 +x^2*y -y^2*z^2, -x^3*y +x*y*z -z^4, x^3*y -x^2 -y*z^2); // --> > 1800s almost 1Gbyte I := ideal(-x^2*y^2 -x*z^2 -z^4, -x^4 +x*y +y, x^2*z -x*y*z^2 -y^3); // --> > 600s I := ideal(-x^2 -x*z +y^3, -x^2*y -x -z, x^2 +x*y*z -x*z); // --> > 10000s and > 5.0Gbyte
I'm putting them here just not to lose them. They were found using a randomized search, so do not have any particular significance (that I know of).
#3
Updated by John Abbott about 7 years ago
Here are some more slow examples:
ideal(-2*x^3 -2*x*z^2 +z^2, x^2*y +2*x^2*z +x*y, -2*x^2*y -2*x*z^2 +2*y^3); --> > 100s ideal(x^3 +x*y*z -z^2, -x^2 +x*z +y*z, -x^2*z +x*y -y^3); --> > 90s ideal(x^2 +x*z^2 -y*z^2, -x^2*z -x*y -y^3, x^3 -x^2 -z^2); --> > 130s ideal(-x^3 +y*z^2 +z^3, x^2*y +x*y^2 -y*z^2, x^2 -x*z^2 -y^3); --> > 160s ideal(-x^3 -x*y -y^3, x^3 +y^2 +z^2, -x^2 -x*z -z^3); --> > 130s ideal(x*y^2 +x -y^2*z, x^3 +y^3 -z^3, -x^3 +x^2*y -y); --> > 130s
#4
Updated by John Abbott about 7 years ago
More examples: these all have support a 3-subset of supp((x+y+z)^3+x) and coeffs +1 or -1
ideal(x^3 -x^2*y +z^3, x^3 -x +y*z^2, x^3 -x*z^2 -y^3); --> > 110s ideal(x^3 -y*z^2 -z^3, x^2*y +x +y^3, -x^2*y +x^2*z +x); --> > 340s ideal(-x^2*z +x -y^3, x^3 +x*y^2 +x*y*z, -x^2*y -x*z^2 +z^3); --> > 450s ideal(x^2*y +x +z^3, x^2*y -x*z^2 -y^2*z, -x^3 -x^2*y -y^3); --> > 540s ideal(x^2*z -x -y^3, -x^3 +x*y^2 +z^3, -x^2*y -x*z^2 -z^3); --> > 200s ideal(x^2*y +x +z^3, x^2*y +x^2*z +y^3, x^3 +x*z^2 +y^3); --> > 360s ideal(x^2*z +x +y^3, x^2*y +x*z^2 +y^2*z, x^3 +x^2*z +z^3); --> > 900s
I tried also in degree 2, but the random search found no "very slow" examples.
I also tried 1 or 2 gens with degree 3 and the rest of degree 2, but again there were no "very slow" examples.
Here "very slow" means longer than 10 seconds.
#5
Updated by John Abbott about 7 years ago
This is really unrelated: it is an ideal with a surprisingly "large" DegRevLex RGBasis
use QQ[x,y,z]; I := ideal(-y^2*z^2 -x*z^3 +z^4, -x*y^3 +y^3 +z, x^3*y -x +1); indent(ReducedGBasis(I));
Putting it here just not to lose it.
#6
Updated by John Abbott over 6 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
Here is a zero-dim ideal with simple DegRevLex RGB
L:=[x^3 -x, y^3 +x^2 +y*z, z^3 +x*y -x*z];
CoCoA takes about 130s to compute the lex-RGB; the basis itself looks fairly simple.
NOTE with verbosity at 100 I noticed that it spent a long time in Final clean up