Slug #1049
GroebnerFan: slow examples
Description
Possibly not too relevant to CoCoA(Lib), but I wanted to collect some challenging GFAN examples.
Related issues
History
#1 Updated by John Abbott almost 7 years ago
Here are some GroebnerFanIdeals
examples which take a long time:
use QQ[x,y,z]; I := ideal(y^3*z -2*x^2*z +2*y^2, y^4 -2*z^4 -x*y*z); --> more than 7200s I := ideal(x*y*z^2 -y^2*z^2 -z^4 +2*x^3, -2*z^4 +2*x*y^2 +2*x*y*z +y); --> about 11000s, maybe 625 cones I := ideal(-2*z^4 +2*x*z^2 +2*z^3, -2*y^5 -2*x^4*z -2*y^2*z^3); --> > 860s I := ideal(x^5 +y^5 -y^2*z^2, 2*x^5 +x^3*y*z -2*x*z); --> >680 cones, long time (>7000s)
Some smaller examples:
I := ideal(2*x^3 +8*y^3 -y^2*z -6*z^3, y^3 -5*x*z^2 +6*y*z +4*y); --> 1580s I := ideal(-5*x^2*y -2*y^2*z +7*x*z +3, 5*x^3 -7*y^3 -5*y^2*z -7*x*y); --> 177 cones, 9s I := ideal(2*x^3 +3*y^2*z +3*y -6, 9*x*y^2 +5*y^3 +x*z^2 -7*x^2); --> 129 cones, 170s I := ideal(-2*y^3 -z^3 +4*z^2, x*y*z +8*z^3 +7*x); --> 73 cones I := ideal(4*x^3 -3*y^2*z +2*y, 6*x^2*y +5*y^3 +z^2); --> 76 cones I := ideal(-6*y^2*z +9*z^3 +6*x^2, -9*y^3 +8*x*z^2 +8*z); --> 76 cones
#2 Updated by Anna Maria Bigatti almost 7 years ago
- Related to Slug #1047: NewPolyRing with user defined ordering is slower than CoCoALib added
#3 Updated by Anna Maria Bigatti almost 7 years ago
- Related to Feature #780: GroebnerFan/ExternalLib-GFan: improve package added
#4 Updated by John Abbott almost 7 years ago
The following example fails:
GroebnerFanIdeals(ideal(x*y,y^3+x,y^3)); --> ERROR: MinBy: list is empty --> WHERE: at line 283 (column 18) of list.cpkg5 --> if L = [] then error("MinBy: list is empty"); endif; --> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ CONTEXT: function MinBy at line 283 of list.cpkg5 CALLED BY: function OutEdge at line 165 of GroebnerFan.cpkg5 CALLED BY: function recursive at line 182 of GroebnerFan.cpkg5 CALLED BY: function GroebnerFanIdeals at line 228 of GroebnerFan.cpkg5
NOTE: this really ought to be a new issue... but hopefully Anna will fix it in a flash!
Another example:
GroebnerFanIdeals(ideal(y^2+y*z+1,y*z+z^2));
#5 Updated by Anna Maria Bigatti almost 7 years ago
John Abbott wrote:
NOTE: this really ought to be a new issue... but hopefully Anna will fix it in a flash!
Embarassing error in ReducedGBasis: I'll investigate.
(continuing this on #780)
#6 Updated by Anna Maria Bigatti almost 7 years ago
- Subject changed from GFAN: slow examples to GroebnerFan: slow examples
#7 Updated by John Abbott almost 7 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
Here is a strange example:
use QQ[x,y,z]; I := ideal(-2*x*y^2 +y^3 +3*y^2*z -z, 2*y*z^2 +3*x^2 +x*z -2*x, -2*x^2*z +x*z^2 +z^3 +3*z^2); GFAN := GroebnerFanIdeals(I);
It computes 41 ideals then seems to get "stuck" for a long time (but does proceed slowly, using lots of RAM).
UPDATE it finished after about 13400s, and the fan contains 204 cones.
#8 Updated by John Abbott almost 7 years ago
Here are some examples with binomial ideals:
use QQ[x,y,z]; I := ideal(-4*x*y+10, 9*y^3+4*z^3, -8*x^3-2*y*z^2); --> 65 cones, 0.4s I := ideal(-3*x^3 +4*y^3, -3*x*y*z +4*y, -3*x*y^2 -4*z^3); --> 67 cones, 0.4s I := ideal(-2*x^3 -3*y*z^2, -4*y^3 -3*z^3, -5*x^2*y +3); --> 67 cones, 0.4s I := ideal(5*x^2*z -5, -3*z^3 +5*x*y, y^3 -3*x^2); --> 67 cones 0.4s
I do not have much "feel" for Groebner fans, but it did surprise me to find that even a binomial ideal can have such a large Gfan.
UPDATE
I ran a longer search and the computer produced these examples (1 trinomial and 2 binomials of degree 3)
Fan size: 473 3 ideals with big GFAN: [ ideal(65*y^2*z +81*z^2 +23, 63*x^3 +69*y^3, 78*x^2*y +21*z^3), ideal(30*x^2*z +91*z^2 +10, 8*x*y^2 +48*z^3, 41*x^3 +40*y^3), ideal(76*x*y^2 +42*x^2 +47, 53*x^3 +41*y*z^2, 91*y^3 +63*z^3) ] Times taken were ["13.496", "13.946", "14.488"] Slowest took 138.48 Slowest example: ideal(73*x*y^2 +53*z^3 +77*x*y, 90*x^3 +44*y*z, 6*y^3 +89*x)
As always, I suspect that the coeffs can be replaced by smaller ones.
#9 Updated by John Abbott almost 7 years ago
Here are some binomial examples of deg 4:
Fan size: 182 3 ideals with big GFAN: [ ideal(-34*z^4 -80*x*y, 52*y^4 -32*x^3, -88*x^3*z +22), ideal(20*z^4 +43*y^3, -33*x^4 +80*y*z, -88*x*y^3 +81), ideal(8*y^4 +26*x*z, 39*x^4 +39*z^3, -40*y*z^3 -98) ] Times taken were ["1.2748", "1.2624", "1.2772"]
Probably the coeffs can be replaced by much smaller values (so long as the supports remain the same).
#10 Updated by John Abbott almost 7 years ago
Here are two deg 5 binomial examples:
Fan size: 338 1 ideals with big GFAN: [ ideal(60*x^2*y*z -96*x^2, 69*x^3*y^2 +52*z^5, 35*x^5 +3*x*y^4) ] Times taken were ["2.9786"] Fan size: 336 1 ideals with big GFAN: [ ideal(860*x^2*z^3 -453*x*z^2, 758*y^5 -356*x*z^4, 640*x^5 +802*y^2*z^3) ] Times taken were ["3.1647"]
Again I believe only the supports are important; the coeffs can almost certainly be replaced by smaller ones.
An example in deg=7:
Fan size: 696 1 ideals with big GFAN: [ ideal(644*x^4*y^3 -519*x*z^6, -260*y^7 -553*x^4*z, 117*x^2*y*z^2 +24*x*y*z) ] Times taken were ["7.1751"]
Here is a silly example (deg=9):
time 23.682 ideal(13*x^9 -88*z^4, -97*x^4*y^4*z -41*x^4*y^3, 81*x^2*z^7 +10*y^5) GFAN size 1826
#11 Updated by Anna Maria Bigatti almost 7 years ago
- Related to Slug #1057: Slug: Polynomial ring contructor slow with (big) matrix ordering added
#12 Updated by John Abbott almost 7 years ago
- Related to Bug #1069: GroebnerFan: ERROR: Matrix must be invertible added
#13 Updated by John Abbott almost 7 years ago
Fan size: 634 1 ideals with big GFAN: [ ideal(80*x^3 +9*x*y^2 +10, 49*x^3 +32*y^2*z +36*z^2, 45*y^3 +85*z^3 +41) ] Times taken were ["44.498"]
#14 Updated by John Abbott almost 7 years ago
Having 4 indets makes it easy to find "big" examples:
use QQ[x,y,z,t]; I := ideal(x*z^2+x*y+z, z^3+y^2*t, x^2*y+z*t^2, y*z^2+x); --> Time 800s, UnivDenom = 2*10^13090, NumCones = 6194 I := ideal(y^2*z +t^3 +z*t, z*t^2 +z, x*z^2 +y*z*t, y*z^2 +x^2); --> Time 95200s, UniDenom = 1.4*10^19, NumCones = 820, MaxDenom = 1280 I := ideal(x^2*z +y*z +t, y^3 +x, x^3 +z^3, x^2*t +t^3); --> ERROR in ctor for MatrixOrdering after 158000s (about 44hrs) I := ideal(x*y*z +y*z*t +y, z^3 +x^2, y^2*z +t^3, x^3 +y^3); --> time 11800s, UnivDenom=2.5*10^379530, NumCones=36928 GF := GroebnerFanIdeals(I); len(GF);
Even in deg 2 there are some hard examples:
I := ideal(x^2 +x*y +y*t, t^2 +z, z^2 +1, y^2 +t); --> UnivDenom = 2.7006*10^114, NumCones = 179, time = 7.7s I := ideal(x^2+x*z+z*t, y^2+t, z^2+y, t^2+1); --> UnivDenom = 2*10^104, time = 8.9s, NumCones = 198 I := ideal(z^2+y*t+x, t^2+y, x^2+z*t, y^2+1); --> UnivDenom = 8*10^80, NumCones = 232
#15 Updated by Anna Maria Bigatti 18 days ago
I := ideal(-5*x^2*y -2*y^2*z +7*x*z +3, 5*x^3 -7*y^3 -5*y^2*z -7*x*y); --> 177 cones, 9s t0 := CpuTime(); GFAN := GroebnerFanIdeals(I); TimeFrom(t0);
It is 20s on my computer. Maybe for a change I made in reduction/sugar?
#16 Updated by John Abbott 18 days ago
- Related to Design #984: GroebnerFanIdeals: order matrices sometimes have "large" entries added