{"cells":[{"metadata":{},"cell_type":"markdown","source":"## Example usage of GroebnerBasis.jl"},{"metadata":{"trusted":true},"cell_type":"code","source":"import Pkg; Pkg.add(\"GroebnerBasis\")","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"using GroebnerBasis","execution_count":3,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Once the package is loaded we can define a polynomial ring R and an ideal I in R.\nHere we use some predefined example included in GroebnerBasis.jl."},{"metadata":{"trusted":true},"cell_type":"code","source":"R,I = GroebnerBasis.cyclic_7(32003);","execution_count":5,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"R is a Singular polynomial ring and I is a Singular ideal. GroebnerBasis.jl includes an interface to Singular such that\nthe OSCAR user can easily use the fast Groebner basis algorithms together with the versatility of Singular.jl."},{"metadata":{"trusted":true},"cell_type":"code","source":"R","execution_count":6,"outputs":[{"output_type":"execute_result","execution_count":6,"data":{"text/plain":"Singular Polynomial Ring (ZZ/32003),(x1,x2,x3,x4,x5,x6,x7),(dp(7),C)"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"I","execution_count":7,"outputs":[{"output_type":"execute_result","execution_count":7,"data":{"text/plain":"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)"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"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."},{"metadata":{"trusted":true},"cell_type":"code","source":"G = GroebnerBasis.f4(I);","execution_count":8,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"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:"},{"metadata":{"trusted":true},"cell_type":"code","source":"Singular.ngens(G)","execution_count":10,"outputs":[{"output_type":"execute_result","execution_count":10,"data":{"text/plain":"209"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"Or we could get the leading ideal of I:"},{"metadata":{"trusted":true},"cell_type":"code","source":"Singular.lead(G)","execution_count":12,"outputs":[{"output_type":"execute_result","execution_count":12,"data":{"text/plain":"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)"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"All functionality of GroebnerBasis.jl comes with a detailed documentation the user can easily access:"},{"metadata":{"scrolled":true,"trusted":true},"cell_type":"code","source":"?GroebnerBasis.f4()","execution_count":13,"outputs":[{"output_type":"execute_result","execution_count":13,"data":{"text/plain":"\u001b[36m  f4(I[, hts::Int=17, nthrds::Int=1, maxpairs::Int=0, resetht::Int=0,\u001b[39m\n\u001b[36m          laopt::Int=1, infolevel::Int=0, monorder::Symbol=:degrevlex])\u001b[39m\n\n  Compute a Groebner basis of the given ideal I w.r.t. to the given monomial\n  order using Faugere's F4 algorithm. The function takes a Singular ideal as\n  input and returns a Singular ideal. At the moment only finite fields up to\n  31-bit and the rationals are supported as ground fields.\n\n\u001b[1m  Arguments\u001b[22m\n\u001b[1m  ≡≡≡≡≡≡≡≡≡≡≡\u001b[22m\n\n    •    \u001b[36mI::Singular.sideal\u001b[39m: ideal to compute a Groebner basis for.\n\n    •    \u001b[36mhts::Int=17\u001b[39m: hash table size log_2; default is 17, i.e. 2^17 as\n        initial hash table size.\n\n    •    \u001b[36mnthrds::Int=1\u001b[39m: number of threads; default is 1.\n\n    •    \u001b[36mmaxpairs::Int=0\u001b[39m: maximal number of pairs selected for one matrix;\n        default is 0, i.e. no restriction. If matrices get too big or\n        consume too much memory this is a good parameter to play with.\n\n    •    \u001b[36mresetht::Int=0\u001b[39m: Resets the hash table after \u001b[36mresetht\u001b[39m steps in the\n        algorthm; default is 0, i.e. no resetting at all. Since we add\n        monomials to the matrices which are only used for reduction\n        purposes, but have no further meaning in the basis, this parameter\n        might also help when memory get a problem.\n\n    •    \u001b[36mlaopt::Int=1\u001b[39m: option for linear algebra to be used. there are\n        different linear algebra routines implemented:\n      \n          •    \u001b[36m1\u001b[39m: exact sparse-dense computation (default),\n      \n          •    \u001b[36m2\u001b[39m: exact sparse computation,\n      \n          •    \u001b[36m42\u001b[39m: probabilistic sparse-dense computation,\n      \n          •    \u001b[36m43\u001b[39m: exact sparse then probabilistic dense computation,\n      \n          •    \u001b[36m44\u001b[39m: probabilistic sparse computation.\n\n    •    \u001b[36mreducegb::Int=0\u001b[39m: reduce final basis; default is 0. Note that for\n        computations over Q we do not normalize the polynomials, the basis\n        is only minimal and tailreduced. Normalize by hand if necessary.\n\n    •    \u001b[36mpbmfiles::Int=0\u001b[39m: option for generating pbm files of matrices:\n      \n          •    \u001b[36m0\u001b[39m: off (default),\n      \n          •    \u001b[36m1\u001b[39m: on.\n\n    •    \u001b[36minfolevel::Int=0\u001b[39m: info level for printout:\n      \n          •    \u001b[36m0\u001b[39m: no printout (default),\n      \n          •    \u001b[36m1\u001b[39m: a summary of the computational data is printed at the\n              beginning and\n      \n        the end of the computation,\n      \n          •    \u001b[36m2\u001b[39m: also dynamical information for each round resp.\n              matrix is printed.\n\n    •    \u001b[36mmonorder::Symbol=:degrevlex\u001b[39m: monomial order w.r.t. which the\n        computation is done;\n      \n          •    \u001b[36mdegrevlex\u001b[39m: the degree-reverse-lexicographical (DRL)\n              order (default),\n      \n          •    \u001b[36mlex\u001b[39m: the lexicographical order (LEX).","text/markdown":"```\nf4(I[, hts::Int=17, nthrds::Int=1, maxpairs::Int=0, resetht::Int=0,\n        laopt::Int=1, infolevel::Int=0, monorder::Symbol=:degrevlex])\n```\n\nCompute 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.\n\n# Arguments\n\n  * `I::Singular.sideal`: ideal to compute a Groebner basis for.\n  * `hts::Int=17`: hash table size log_2; default is 17, i.e. 2^17 as initial hash               table size.\n  * `nthrds::Int=1`:  number of threads; default is 1.\n  * `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.\n  * `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.\n  * `laopt::Int=1`: option for linear algebra to be used. there are different                 linear algebra routines implemented:\n\n      * `1`: exact sparse-dense computation (default),\n      * `2`: exact sparse computation,\n      * `42`: probabilistic sparse-dense computation,\n      * `43`: exact sparse then probabilistic dense computation,\n      * `44`: probabilistic sparse computation.\n  * `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.\n  * `pbmfiles::Int=0`: option for generating pbm files of matrices:\n\n      * `0`: off (default),\n      * `1`:  on.\n  * `infolevel::Int=0`: info level for printout:\n\n      * `0`: no printout (default),\n      * `1`:  a summary of the computational data is printed at the beginning and\n\n    the end of the computation,\n\n      * `2`: also dynamical information for each round resp. matrix is printed.\n  * `monorder::Symbol=:degrevlex`: monomial order w.r.t. which the computation is                               done;\n\n      * `degrevlex`: the degree-reverse-lexicographical (DRL) order (default),\n      * `lex`: the lexicographical order (LEX).\n","text/latex":"\\begin{verbatim}\nf4(I[, hts::Int=17, nthrds::Int=1, maxpairs::Int=0, resetht::Int=0,\n        laopt::Int=1, infolevel::Int=0, monorder::Symbol=:degrevlex])\n\\end{verbatim}\nCompute 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.\n\n\\section{Arguments}\n\\begin{itemize}\n\\item \\texttt{I::Singular.sideal}: ideal to compute a Groebner basis for.\n\n\n\\item \\texttt{hts::Int=17}: hash table size log\\_2; default is 17, i.e. 2\\^{}17 as initial hash               table size.\n\n\n\\item \\texttt{nthrds::Int=1}:  number of threads; default is 1.\n\n\n\\item \\texttt{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.\n\n\n\\item \\texttt{resetht::Int=0}: Resets the hash table after \\texttt{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.\n\n\n\\item \\texttt{laopt::Int=1}: option for linear algebra to be used. there are different                 linear algebra routines implemented:\n\n\\begin{itemize}\n\\item \\texttt{1}: exact sparse-dense computation (default),\n\n\n\\item \\texttt{2}: exact sparse computation,\n\n\n\\item \\texttt{42}: probabilistic sparse-dense computation,\n\n\n\\item \\texttt{43}: exact sparse then probabilistic dense computation,\n\n\n\\item \\texttt{44}: probabilistic sparse computation.\n\n\\end{itemize}\n\n\\item \\texttt{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.\n\n\n\\item \\texttt{pbmfiles::Int=0}: option for generating pbm files of matrices:\n\n\\begin{itemize}\n\\item \\texttt{0}: off (default),\n\n\n\\item \\texttt{1}:  on.\n\n\\end{itemize}\n\n\\item \\texttt{infolevel::Int=0}: info level for printout:\n\n\\begin{itemize}\n\\item \\texttt{0}: no printout (default),\n\n\n\\item \\texttt{1}:  a summary of the computational data is printed at the beginning and\n\n\\end{itemize}\nthe end of the computation,\n\n\\begin{itemize}\n\\item \\texttt{2}: also dynamical information for each round resp. matrix is printed.\n\n\\end{itemize}\n\n\\item \\texttt{monorder::Symbol=:degrevlex}: monomial order w.r.t. which the computation is                               done;\n\n\\begin{itemize}\n\\item \\texttt{degrevlex}: the degree-reverse-lexicographical (DRL) order (default),\n\n\n\\item \\texttt{lex}: the lexicographical order (LEX).\n\n\\end{itemize}\n\\end{itemize}\n"},"metadata":{}}]},{"metadata":{},"cell_type":"markdown","source":"For example, we can set the infolevel argument to give detailed information of the computation:"},{"metadata":{"trusted":true},"cell_type":"code","source":"G = GroebnerBasis.f4(I,infolevel=2);","execution_count":14,"outputs":[{"output_type":"stream","text":"\n--------------- INPUT DATA ---------------\n#variables                       7\n#equations                       7\nfield characteristic         32003\nhomogeneous input?               0\nmonomial order                 DRL\nbasis hash table resetting     OFF\nlinear algebra option            2\nintial hash table size      131072 (2^17)\nmax pair selection             ALL\n#threads                         1\ninfo level                       2\ngenerate pbm files               0\n------------------------------------------\n\ndeg     sel   pairs        mat          density           new data             time(rd)\n-----------------------------------------------------------------------------------------\n  2       1       6       3 x 16        43.750%      1 new       0 zero        0.000 sec\n  3       1       5       6 x 31        27.957%      1 new       0 zero        0.000 sec\n  4       2       5      15 x 75        16.889%      2 new       0 zero        0.000 sec\n  5       4       6      41 x 142       13.260%      3 new       1 zero        0.000 sec\n  6       9      10      77 x 243       12.843%      7 new       2 zero        0.001 sec\n  7      22      22     159 x 404       12.549%     13 new       9 zero        0.002 sec\n  8      47      47     288 x 591       13.482%     24 new      23 zero        0.005 sec\n  9      98      98     477 x 788       13.600%     39 new      59 zero        0.015 sec\n 10     164     164     768 x 1012      12.678%     52 new     112 zero        0.048 sec\n 11     229     229     925 x 1105      13.122%     62 new     167 zero        0.059 sec\n  5       4     298      35 x 161       18.421%      4 new       0 zero        0.001 sec\n  6      15     305     113 x 305       15.381%      8 new       7 zero        0.004 sec\n  7      35     336     218 x 457       16.699%     15 new      20 zero        0.008 sec\n  8      77     373     445 x 690       14.000%     20 new      57 zero        0.013 sec\n  9     109     395     590 x 831       14.571%     23 new      86 zero        0.019 sec\n 10     136     392     794 x 1025      12.999%     34 new     102 zero        0.041 sec\n 11     196     319     808 x 916       15.836%     40 new     156 zero        0.061 sec\n 12     313     313    1033 x 1040      14.528%     70 new     243 zero        0.084 sec\n  6     114     409     329 x 382       24.167%     35 new      79 zero        0.015 sec\n  7     159     512     517 x 491       21.197%      1 new     158 zero        0.015 sec\n  8      30     359     497 x 604       15.658%      5 new      25 zero        0.007 sec\n  9      63     357     831 x 914        9.907%     14 new      49 zero        0.014 sec\n 10     118     328     567 x 610       16.990%     29 new      89 zero        0.018 sec\n 11     210     251     685 x 655       16.481%     48 new     162 zero        0.037 sec\n 12     279     279     536 x 424       27.707%     35 new     244 zero        0.034 sec\n 13     175     175     440 x 397       27.801%      0 new     175 zero        0.017 sec\n-----------------------------------------------------------------------------------------\n\n---------------- TIMINGS ---------------\noverall                0.523 sec\noverall(cpu)           0.512 sec\nselect                 0.047 sec   9.0%\nsymbol                 0.043 sec   8.2%\nupdate                 0.064 sec  12.2%\nconvert                0.014 sec   2.7%\nla                     0.345 sec  66.1%\n-----------------------------------------\n\n---------- COMPUTATIONAL DATA -----------\nsize of basis            209\n#terms in basis        26969\n#pairs reduced          2610\n#GM criterion         172311\n#redundant               383\n#reset bht                 0\n#rows reduced           5220\n#zero reductions        2025\nmaximal uht size           2^12\nmaximal sht size           2^12\nmaximal bht size           2^17\n-----------------------------------------\n\n","name":"stdout"}]}],"metadata":{"kernelspec":{"name":"julia-1.4","display_name":"Julia 1.4.1","language":"julia"},"language_info":{"file_extension":".jl","name":"julia","mimetype":"application/julia","version":"1.4.1"}},"nbformat":4,"nbformat_minor":4}