Project

General

Profile

Slug #1049

GroebnerFan: slow examples

Added by John Abbott almost 7 years ago. Updated 18 days ago.

Status:
In Progress
Priority:
Low
Assignee:
-
Category:
Various
Target version:
Start date:
19 Apr 2017
Due date:
% Done:

10%

Estimated time:
Spent time:

Description

Possibly not too relevant to CoCoA(Lib), but I wanted to collect some challenging GFAN examples.


Related issues

Related to CoCoA-5 - Slug #1047: NewPolyRing with user defined ordering is slower than CoCoALibClosed2017-04-18

Related to CoCoALib - Feature #780: GroebnerFan/ExternalLib-GFan: improve packageIn Progress2015-09-24

Related to CoCoALib - Slug #1057: Slug: Polynomial ring contructor slow with (big) matrix orderingIn Progress2017-05-04

Related to CoCoALib - Bug #1069: GroebnerFan: ERROR: Matrix must be invertibleIn Progress2017-05-17

Related to CoCoA-5 - Design #984: GroebnerFanIdeals: order matrices sometimes have "large" entriesNew2016-11-26

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

Also available in: Atom PDF