Example usage of GroebnerBasis.jl

In [ ]:
import Pkg; Pkg.add("GroebnerBasis")
In [3]:
using GroebnerBasis

Once the package is loaded we can define a polynomial ring R and an ideal I in R. Here we use some predefined example included in GroebnerBasis.jl.

In [5]:
R,I = GroebnerBasis.cyclic_7(32003);

R is a Singular polynomial ring and I is a Singular ideal. GroebnerBasis.jl includes an interface to Singular such that the OSCAR user can easily use the fast Groebner basis algorithms together with the versatility of Singular.jl.

In [6]:
R
Out[6]:
Singular Polynomial Ring (ZZ/32003),(x1,x2,x3,x4,x5,x6,x7),(dp(7),C)
In [7]:
I
Out[7]:
Singular Ideal over Singular Polynomial Ring (ZZ/32003),(x1,x2,x3,x4,x5,x6,x7),(dp(7),C) with generators (x1+x2+x3+x4+x5+x6+x7, x1*x2+x2*x3+x3*x4+x4*x5+x5*x6+x1*x7+x6*x7, x1*x2*x3+x2*x3*x4+x3*x4*x5+x4*x5*x6+x1*x2*x7+x1*x6*x7+x5*x6*x7, x1*x2*x3*x4+x2*x3*x4*x5+x3*x4*x5*x6+x1*x2*x3*x7+x1*x2*x6*x7+x1*x5*x6*x7+x4*x5*x6*x7, x1*x2*x3*x4*x5+x2*x3*x4*x5*x6+x1*x2*x3*x4*x7+x1*x2*x3*x6*x7+x1*x2*x5*x6*x7+x1*x4*x5*x6*x7+x3*x4*x5*x6*x7, x1*x2*x3*x4*x5*x6+x1*x2*x3*x4*x5*x7+x1*x2*x3*x4*x6*x7+x1*x2*x3*x5*x6*x7+x1*x2*x4*x5*x6*x7+x1*x3*x4*x5*x6*x7+x2*x3*x4*x5*x6*x7, x1*x2*x3*x4*x5*x6*x7-1)

Next we can call the fast F4 Algorithm for computing a Groebner basis G of I in R w.r.t. the given monomial ordering.

In [8]:
G = GroebnerBasis.f4(I);

G is again a Singular object, thus we can directly use Singular functionality to further handle G. E.g. we let Singular tell us the number of elements in the Groebner basis G of I:

In [10]:
Singular.ngens(G)
Out[10]:
209

Or we could get the leading ideal of I:

In [12]:
Singular.lead(G)
Out[12]:
Singular Ideal over Singular Polynomial Ring (ZZ/32003),(x1,x2,x3,x4,x5,x6,x7),(dp(7),C) with generators (x1, x2^2, x2*x3^2, x2*x3*x4^2, x3^3*x4, x2*x3*x4*x5^2, x3^2*x4^2, x2*x4^2*x5^2, x3^2*x4*x5^2, x3*x4^3*x5, x3*x4^4, x2*x4*x5^2*x6, x3^2*x5^2*x6, x2*x3*x5^2*x6, x4^3*x5*x6, x3*x4^2*x5*x6, x2*x4^2*x5*x6, x3^2*x4*x5*x6, x2*x3*x4*x5*x6, x3^3*x5*x6, x4^4*x6, x3*x4^3*x6, x2*x4^3*x6, x3^4*x6, x5^5, x4*x5^4, x3*x5^4, x2*x5^4, x4^2*x5^3, x3*x4*x5^3, x2*x4*x5^3, x3^2*x5^3, x2*x3*x5^3, x4^3*x5^2, x3*x4^2*x5^2, x3^3*x5^2, x4^4*x5, x2*x4^3*x5, x3^4*x5, x4^5, x2*x4^4, x3^5, x6^6, x5*x6^5, x4*x6^5, x3*x6^5, x2*x6^5, x5^2*x6^4, x4*x5*x6^4, x3*x5*x6^4, x2*x5*x6^4, x4^2*x6^4, x3*x4*x6^4, x2*x4*x6^4, x3^2*x6^4, x2*x3*x6^4, x5^3*x6^3, x4*x5^2*x6^3, x3*x5^2*x6^3, x2*x5^2*x6^3, x4^2*x5*x6^3, x3*x4*x5*x6^3, x2*x4*x5*x6^3, x3^2*x5*x6^3, x2*x3*x5*x6^3, x4^3*x6^3, x3*x4^2*x6^3, x2*x4^2*x6^3, x3^2*x4*x6^3, x2*x3*x4*x6^3, x3^3*x6^3, x5^4*x6^2, x4*x5^3*x6^2, x3*x5^3*x6^2, x2*x5^3*x6^2, x4^2*x5^2*x6^2, x3*x4*x5^2*x6^2, x3*x4*x5^2*x6*x7^2, x5^4*x6*x7^3, x4*x5^3*x6*x7^3, x3*x5^3*x6*x7^3, x2*x5^3*x6*x7^3, x4^2*x5^2*x6*x7^3, x4*x5^2*x6^2*x7^4, x3*x5^2*x6^2*x7^4, x2*x5^2*x6^2*x7^4, x4^2*x5*x6^2*x7^4, x3*x4*x5*x6^2*x7^4, x2*x4*x5*x6^2*x7^4, x3^2*x5*x6^2*x7^4, x2*x3*x5*x6^2*x7^4, x4^3*x6^2*x7^4, x3*x4^2*x6^2*x7^4, x2*x4^2*x6^2*x7^4, x3^2*x4*x6^2*x7^4, x2*x3*x4*x6^2*x7^4, x3^3*x6^2*x7^4, x3*x4*x5^2*x7^6, x2*x4*x5^2*x7^6, x3^2*x5^2*x7^6, x2*x3*x5^2*x7^6, x4^3*x5*x7^6, x3*x4^2*x5*x7^6, x2*x4^2*x5*x7^6, x3^2*x4*x5*x7^6, x2*x3*x4*x5*x7^6, x3^3*x5*x7^6, x4^4*x7^6, x3*x4^3*x7^6, x2*x4^3*x7^6, x3^4*x7^6, x6^5*x7^5, x5*x6^4*x7^5, x4*x6^4*x7^5, x3*x6^4*x7^5, x2*x6^4*x7^5, x5^2*x6^3*x7^5, x4*x5*x6^3*x7^5, x3*x5*x6^3*x7^5, x2*x5*x6^3*x7^5, x4^2*x6^3*x7^5, x3*x4*x6^3*x7^5, x2*x4*x6^3*x7^5, x3^2*x6^3*x7^5, x2*x3*x6^3*x7^5, x5^3*x6^2*x7^5, x4*x5^2*x7^8, x3*x5^2*x7^8, x2*x5^2*x7^8, x4^2*x5*x7^8, x3*x4*x5*x7^8, x2*x4*x5*x7^8, x3^2*x5*x7^8, x2*x3*x5*x7^8, x4^3*x7^8, x3*x4^2*x7^8, x2*x4^2*x7^8, x3^2*x4*x7^8, x2*x3*x4*x7^8, x3^3*x7^8, x6^4*x7^7, x5*x6^3*x7^7, x4*x6^3*x7^7, x3*x6^3*x7^7, x2*x6^3*x7^7, x5^2*x6^2*x7^7, x4*x5*x6^2*x7^7, x3*x5*x6^2*x7^7, x2*x5*x6^2*x7^7, x4^2*x6^2*x7^7, x3*x4*x6^2*x7^7, x2*x4*x6^2*x7^7, x3^2*x6^2*x7^7, x2*x3*x6^2*x7^7, x5^3*x6*x7^7, x4*x5^2*x6*x7^7, x3*x5^2*x6*x7^7, x2*x5^2*x6*x7^7, x4^2*x5*x6*x7^7, x3*x4*x5*x6*x7^7, x2*x4*x5*x6*x7^7, x3^2*x5*x6*x7^7, x2*x3*x5*x6*x7^7, x4^3*x6*x7^7, x3*x4^2*x6*x7^7, x2*x4^2*x6*x7^7, x3^2*x4*x6*x7^7, x2*x3*x4*x6*x7^7, x3^3*x6*x7^7, x5^4*x7^7, x4*x5^3*x7^7, x3*x5^3*x7^7, x2*x5^3*x7^7, x4^2*x5^2*x7^7, x7^12, x6*x7^11, x5*x7^11, x4*x7^11, x3*x7^11, x2*x7^11, x6^2*x7^10, x5*x6*x7^10, x4*x6*x7^10, x3*x6*x7^10, x2*x6*x7^10, x5^2*x7^10, x4*x5*x7^10, x3*x5*x7^10, x2*x5*x7^10, x4^2*x7^10, x3*x4*x7^10, x2*x4*x7^10, x3^2*x7^10, x2*x3*x7^10, x6^3*x7^9, x5*x6^2*x7^9, x4*x6^2*x7^9, x3*x6^2*x7^9, x2*x6^2*x7^9, x5^2*x6*x7^9, x4*x5*x6*x7^9, x3*x5*x6*x7^9, x2*x5*x6*x7^9, x4^2*x6*x7^9, x3*x4*x6*x7^9, x2*x4*x6*x7^9, x3^2*x6*x7^9, x2*x3*x6*x7^9, x5^3*x7^9)

All functionality of GroebnerBasis.jl comes with a detailed documentation the user can easily access:

In [13]:
?GroebnerBasis.f4()
Out[13]:
f4(I[, hts::Int=17, nthrds::Int=1, maxpairs::Int=0, resetht::Int=0,
        laopt::Int=1, infolevel::Int=0, monorder::Symbol=:degrevlex])

Compute a Groebner basis of the given ideal I w.r.t. to the given monomial order using Faugere's F4 algorithm. The function takes a Singular ideal as input and returns a Singular ideal. At the moment only finite fields up to 31-bit and the rationals are supported as ground fields.

Arguments

  • I::Singular.sideal: ideal to compute a Groebner basis for.
  • hts::Int=17: hash table size log_2; default is 17, i.e. 2^17 as initial hash table size.
  • nthrds::Int=1: number of threads; default is 1.
  • maxpairs::Int=0: maximal number of pairs selected for one matrix; default is 0, i.e. no restriction. If matrices get too big or consume too much memory this is a good parameter to play with.
  • resetht::Int=0: Resets the hash table after resetht steps in the algorthm; default is 0, i.e. no resetting at all. Since we add monomials to the matrices which are only used for reduction purposes, but have no further meaning in the basis, this parameter might also help when memory get a problem.
  • laopt::Int=1: option for linear algebra to be used. there are different linear algebra routines implemented:

    • 1: exact sparse-dense computation (default),
    • 2: exact sparse computation,
    • 42: probabilistic sparse-dense computation,
    • 43: exact sparse then probabilistic dense computation,
    • 44: probabilistic sparse computation.
  • reducegb::Int=0: reduce final basis; default is 0. Note that for computations over Q we do not normalize the polynomials, the basis is only minimal and tailreduced. Normalize by hand if necessary.
  • pbmfiles::Int=0: option for generating pbm files of matrices:

    • 0: off (default),
    • 1: on.
  • infolevel::Int=0: info level for printout:

    • 0: no printout (default),
    • 1: a summary of the computational data is printed at the beginning and

    the end of the computation,

    • 2: also dynamical information for each round resp. matrix is printed.
  • monorder::Symbol=:degrevlex: monomial order w.r.t. which the computation is done;

    • degrevlex: the degree-reverse-lexicographical (DRL) order (default),
    • lex: the lexicographical order (LEX).

For example, we can set the infolevel argument to give detailed information of the computation:

In [14]:
G = GroebnerBasis.f4(I,infolevel=2);
--------------- INPUT DATA ---------------
#variables                       7
#equations                       7
field characteristic         32003
homogeneous input?               0
monomial order                 DRL
basis hash table resetting     OFF
linear algebra option            2
intial hash table size      131072 (2^17)
max pair selection             ALL
#threads                         1
info level                       2
generate pbm files               0
------------------------------------------

deg     sel   pairs        mat          density           new data             time(rd)
-----------------------------------------------------------------------------------------
  2       1       6       3 x 16        43.750%      1 new       0 zero        0.000 sec
  3       1       5       6 x 31        27.957%      1 new       0 zero        0.000 sec
  4       2       5      15 x 75        16.889%      2 new       0 zero        0.000 sec
  5       4       6      41 x 142       13.260%      3 new       1 zero        0.000 sec
  6       9      10      77 x 243       12.843%      7 new       2 zero        0.001 sec
  7      22      22     159 x 404       12.549%     13 new       9 zero        0.002 sec
  8      47      47     288 x 591       13.482%     24 new      23 zero        0.005 sec
  9      98      98     477 x 788       13.600%     39 new      59 zero        0.015 sec
 10     164     164     768 x 1012      12.678%     52 new     112 zero        0.048 sec
 11     229     229     925 x 1105      13.122%     62 new     167 zero        0.059 sec
  5       4     298      35 x 161       18.421%      4 new       0 zero        0.001 sec
  6      15     305     113 x 305       15.381%      8 new       7 zero        0.004 sec
  7      35     336     218 x 457       16.699%     15 new      20 zero        0.008 sec
  8      77     373     445 x 690       14.000%     20 new      57 zero        0.013 sec
  9     109     395     590 x 831       14.571%     23 new      86 zero        0.019 sec
 10     136     392     794 x 1025      12.999%     34 new     102 zero        0.041 sec
 11     196     319     808 x 916       15.836%     40 new     156 zero        0.061 sec
 12     313     313    1033 x 1040      14.528%     70 new     243 zero        0.084 sec
  6     114     409     329 x 382       24.167%     35 new      79 zero        0.015 sec
  7     159     512     517 x 491       21.197%      1 new     158 zero        0.015 sec
  8      30     359     497 x 604       15.658%      5 new      25 zero        0.007 sec
  9      63     357     831 x 914        9.907%     14 new      49 zero        0.014 sec
 10     118     328     567 x 610       16.990%     29 new      89 zero        0.018 sec
 11     210     251     685 x 655       16.481%     48 new     162 zero        0.037 sec
 12     279     279     536 x 424       27.707%     35 new     244 zero        0.034 sec
 13     175     175     440 x 397       27.801%      0 new     175 zero        0.017 sec
-----------------------------------------------------------------------------------------

---------------- TIMINGS ---------------
overall                0.523 sec
overall(cpu)           0.512 sec
select                 0.047 sec   9.0%
symbol                 0.043 sec   8.2%
update                 0.064 sec  12.2%
convert                0.014 sec   2.7%
la                     0.345 sec  66.1%
-----------------------------------------

---------- COMPUTATIONAL DATA -----------
size of basis            209
#terms in basis        26969
#pairs reduced          2610
#GM criterion         172311
#redundant               383
#reset bht                 0
#rows reduced           5220
#zero reductions        2025
maximal uht size           2^12
maximal sht size           2^12
maximal bht size           2^17
-----------------------------------------