Groebner basis evaluation time is different

jocaps
Messages : 118
Inscription : lun. avr. 17, 2017 4:32 pm

Groebner basis evaluation time is different

Message par jocaps » sam. avr. 13, 2019 10:05 am

I made a code for Katsura 9 Groebner basis benchmark as follows:

Code : Tout sélectionner

from giacpy import giac, gbasis
from time import clock, time

#katsura n, change n as pleased..
n=9

x=[]
ideal=[]
for i in xrange(n+1):
  s= "x" + str(i)
  x.append(giac(s))

# x_0 + 2\sum_{i=1}^n x_i = 1
f=x[0]
for i in xrange(1,n+1):
  f += 2*x[i]
ideal.append(f-1)

# \sum_{j=-n}^{n-i} x_{|j|}x_{|j+i|} = x_{i} \qquad i=0,\dots,n-1
for i in xrange(n):
  f=-x[i]
  for j in xrange(-n,n-i+1):
    f += x[abs(j)]*x[abs(j+i)]
  ideal.append(f.regroup())

print ideal 

"""
For katsura 9, ideal = 
[x0+2*x1+2*x2+2*x3+2*x4+2*x5+2*x6+2*x7+2*x8+2*x9-1, x0**2+2*x1**2+2*x2**2+2*x3**2+2*x4**2+2*x5**2+2*x6**2+2*x7**2+2*x8**2+2*x9**2-x0, 2*x0*x1+2*x1*x2+2*x2*x3+2*x3*x4+2*x4*x5+2*x5*x6+2*x6*x7+2*x7*x8+2*x8*x9-x1, x1**2+2*x0*x2+2*x1*x3+2*x2*x4+2*x3*x5+2*x4*x6+2*x5*x7+2*x6*x8+2*x7*x9-x2, 2*x0*x3+2*x1*x2+2*x1*x4+2*x2*x5+2*x3*x6+2*x4*x7+2*x5*x8+2*x6*x9-x3, x2**2+2*x0*x4+2*x1*x3+2*x1*x5+2*x2*x6+2*x3*x7+2*x4*x8+2*x5*x9-x4, 2*x0*x5+2*x1*x4+2*x1*x6+2*x2*x3+2*x2*x7+2*x3*x8+2*x4*x9-x5, x3**2+2*x0*x6+2*x1*x5+2*x1*x7+2*x2*x4+2*x2*x8+2*x3*x9-x6, 2*x0*x7+2*x1*x6+2*x1*x8+2*x2*x5+2*x2*x9+2*x3*x4-x7, x4**2+2*x0*x8+2*x1*x7+2*x1*x9+2*x2*x6+2*x3*x5-x8]
"""

#start = clock() #for windows
start = time() # for linux
gbasis(ideal,x)
#print clock()-start, "seconds used"
print time()-start, "seconds used"

In my Linux system using time.clock seems to give me the wall clock (i.e. groeber basis computation is feels much faster than what I get as output) so I used time.time there (in my windows system it's reversed). You may laugh, but I even counted the time using a stopwatch and time.time seems to be appropriate for my Linux system. In any case, this is the output I get from my machine:

Code : Tout sélectionner

Running a probabilistic check for the reconstructed Groebner basis. If successfull, error probability is less than 1e-15 and is estimated to be less than 10^-147. Use proba_epsilon:=0 to certify (this takes more time).
// Groebner basis computation time 9.77126 Memory 122.604M

Evaluation time: 9.91
3.29461288452 seconds used
I noticed that the time parsed by giac itself (9.91 seconds) is exactly the time when I use time.clock in linux (which is wrong in my opinion). I did the same test in Singular 3.1.0 and the computation felt much longer (at least twice as long) but Singular tells me that it needed 7 seconds though I am very certain that Singular took longer to compute than giac (using stopwatch). Any explanation for this?

It does help to understand this, because I am trying to make a modern Benchmark for Groebner basis with different computer algebra systems and I am very confident that giac has one of the top Groebner engine (at least for Katsura 9).

Jose

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Groebner basis evaluation time is different

Message par parisse » sam. avr. 13, 2019 12:41 pm

Your timing commands probably take in account only the current process, and this includes GB computation time for giac (since giacpy is a Python module) but perhaps not for Singular. Evaluation time returned by giac is CPU time, i.e. addition of the time required by all threads. If you call time(gbasis(...)) in giac you will get 2 times: CPU time and real time (stopwatch time). Real time should be less if you have more than 1 CPU.
Katsura9 is a little too small example to see the full power of giac. Cyclic>=8 or Katsura>=11 would be better (calling modstd in Singular, otherwise it will be too long).

jocaps
Messages : 118
Inscription : lun. avr. 17, 2017 4:32 pm

Re: Groebner basis evaluation time is different

Message par jocaps » lun. avr. 15, 2019 11:09 am

As always, thanks for this enlightening explanation Bernard!

Yes, I will try to do benchmark of more polynomial systems (not just katsura9, as you say katsura>11 if this will show the power of giac!) to show the full power of giac.

Anyway, now at least I understand. It seems though that in poly.lib (package of singular) it insists on using katsura (and its definition of katsura is rather conflicting to the usual one we know) with with some base field of characteristic 32023 and it insists on grevlex ordering. Some people tell me that this is fine and even better. Since I am inexperienced I will go with this for now. But my question (I never tried), how do you ask giac (or giacpy) to compute gbasis over fields of non-zero characteristics? Can we? If not then I will be forced to show my benchmarks only over the rationals and just manually define katsura in singular.

Jose

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Groebner basis evaluation time is different

Message par parisse » lun. avr. 15, 2019 6:24 pm

Yes, you can run gbasis in Z/pZ (for p at most 31 bits). Add mod p after the list of polynomials. The source code tarball of giac has some benchmark files ready to run, in examples/groebner.

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: Groebner basis evaluation time is different

Message par frederic han » jeu. avr. 18, 2019 6:19 am

You should also consider the giacsettings.threads value and also giacsettings.proba_epsilon (if probalistic algorithm are disabled it is much slower). In ipython %time gives both times:

(cpu time is less with 1 thread but wall time is longer)

Code : Tout sélectionner

In [5]: import giacpy

In [7]: giacpy.giacsettings.threads
Out[7]: 4

In [9]: %time gb=gbasis(ideal,x)


Running a probabilistic check for the reconstructed Groebner basis. If successfull, error probability is less than 1e-15 and is estimated to be less than 10^-147. Use proba_epsilon:=0 to certify (this takes more time).
// Groebner basis computation time 7.79965 Memory 0.122628M

Evaluation time: 7.96
CPU times: user 7.62 s, sys: 342 ms, total: 7.96 s
Wall time: 3.91 s

In [10]: giacpy.giacsettings.threads=1

In [11]: %time gb=gbasis(ideal,x)


Running a probabilistic check for the reconstructed Groebner basis. If successfull, error probability is less than 1e-15 and is estimated to be less than 10^-147. Use proba_epsilon:=0 to certify (this takes more time).
// Groebner basis computation time 5.28427 Memory 0.149756M

Evaluation time: 5.47
CPU times: user 5.46 s, sys: 33.8 ms, total: 5.49 s
Wall time: 5.52 s

In [12]: giacpy.giacsettings.threads=2

In [13]: %time gb=gbasis(ideal,x)


Running a probabilistic check for the reconstructed Groebner basis. If successfull, error probability is less than 1e-15 and is estimated to be less than 10^-147. Use proba_epsilon:=0 to certify (this takes more time).
// Groebner basis computation time 5.74521 Memory 0.157848M

Evaluation time: 5.92
CPU times: user 5.86 s, sys: 97.4 ms, total: 5.96 s
Wall time: 4.08 s

In [14]: giacpy.giacsettings.proba_epsilon=0

In [15]: %time gb=gbasis(ideal,x)

^CCtrl-C pressed (pid 7983)
Degree too large for compressed monomials. Using uncompressed monomials instead.

Evaluation time: 83.68
CPU times: user 1min 23s, sys: 373 ms, total: 1min 23s
Wall time: 1min 22s

In [16]: ideal101=giac(ideal) % 101

In [17]: ideal101
Out[17]: [(x0+2*x1+2*x2+2*x3+2*x4+2*x5+2*x6+2*x7+2*x8+2*x9-1)*(1 % 101),(x0**2+2*x1**2+2*x2**2+2*x3**2+2*x4**2+2*x5**2+2*x6**2+2*x7**2+2*x8**2+2*x9**2-x0)*(1 % 101),(2*x0*x1+2*x1*x2+2*x2*x3+2*x3*x4+2*x4*x5+2*x5*x6+2*x6*x7+2*x7*x8+2*x8*x9-x1)*(1 % 101),(x1**2+2*x0*x2+2*x1*x3+2*x2*x4+2*x3*x5+2*x4*x6+2*x5*x7+2*x6*x8+2*x7*x9-x2)*(1 % 101),(2*x0*x3+2*x1*x2+2*x1*x4+2*x2*x5+2*x3*x6+2*x4*x7+2*x5*x8+2*x6*x9-x3)*(1 % 101),(x2**2+2*x0*x4+2*x1*x3+2*x1*x5+2*x2*x6+2*x3*x7+2*x4*x8+2*x5*x9-x4)*(1 % 101),(2*x0*x5+2*x1*x4+2*x1*x6+2*x2*x3+2*x2*x7+2*x3*x8+2*x4*x9-x5)*(1 % 101),(x3**2+2*x0*x6+2*x1*x5+2*x1*x7+2*x2*x4+2*x2*x8+2*x3*x9-x6)*(1 % 101),(2*x0*x7+2*x1*x6+2*x1*x8+2*x2*x5+2*x2*x9+2*x3*x4-x7)*(1 % 101),(x4**2+2*x0*x8+2*x1*x7+2*x1*x9+2*x2*x6+2*x3*x5-x8)*(1 % 101)]

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: Groebner basis evaluation time is different

Message par frederic han » jeu. avr. 18, 2019 6:42 am

jocaps a écrit :
lun. avr. 15, 2019 11:09 am
As always, thanks for this enlightening explanation Bernard!

Yes, I will try to do benchmark of more polynomial systems (not just katsura9, as you say katsura>11 if this will show the power of giac!) to show the full power of giac.

Anyway, now at least I understand. It seems though that in poly.lib (package of singular) it insists on using katsura (and its definition of katsura is rather conflicting to the usual one we know) with with some base field of characteristic 32023 and it insists on grevlex ordering. Some people tell me that this is fine and even better. Since I am inexperienced I will go with this for now. But my question (I never tried), how do you ask giac (or giacpy) to compute gbasis over fields of non-zero characteristics? Can we? If not then I will be forced to show my benchmarks only over the rationals and just manually define katsura in singular.

Jose
didn't you mean 32003 because 32023 is not prime?
NB: in sage there is an instruction that uses giacpy_sage + convert from sage/libsingular to giacpy_sage and back to sage. it gives the following comparison:

Code : Tout sélectionner

age: from giacpy_sage import libgiac,giacsettings
// Giac share root-directory:/home/fred-dev/sage/develop/sage.develop/local/share/giac/
// Giac share root-directory:/home/fred-dev/sage/develop/sage.develop/local/share/giac/
Help file /home/fred-dev/sage/develop/sage.develop/local/share/giac/doc/fr/aide_cas not found
Added 0 synonyms
sage: giacsettings.threads=4
sage: P=PolynomialRing(GF(32003),9,'x')
sage: I=sage.rings.ideal.Katsura(P)
sage: %time gb1=I.groebner_basis()
CPU times: user 866 ms, sys: 912 µs, total: 867 ms
Wall time: 869 ms
sage: %time gb2=I.groebner_basis('giac')
// Groebner basis computation time 0.139633 Memory 0.238264M
CPU times: user 398 ms, sys: 12.8 ms, total: 411 ms
Wall time: 399 ms
sage: P=PolynomialRing(GF(32003),10,'x')
sage: I=sage.rings.ideal.Katsura(P)
sage: %time gb1=I.groebner_basis()
CPU times: user 7.5 s, sys: 1.37 ms, total: 7.5 s
Wall time: 7.52 s
sage: %time gb2=I.groebner_basis('giac')
// Groebner basis computation time 0.900647 Memory 0.264072M
CPU times: user 2.02 s, sys: 38.2 ms, total: 2.06 s
Wall time: 1.75 s


Répondre