groebnerBasis -- Gröbner basis, as a matrix

Usage:

M = groebnerBasis I

M = groebnerBasis(I, Strategy=>"MGB")

M = groebnerBasis(I, Strategy=>"F4")
Inputs:
- I, an ideal, or a module or a matrix (in which case the result is the Gröbner basis of the submodule generated by the columns)
- MGBOptions, a list, For internal use only. Warning: the interface is likely to change.
Optional inputs:
- Strategy => a string, default value null, If not given, use the default algorithm. If given, value must be "MGB" or "F4", and the result is experimental
- MGBOptions
Outputs:
- M, a matrix, The matrix whose columns are the generators of the Gröbner basis of I. In the non-local monomial order case, the result is auto-reduced, and sorted.

Description

With no Strategy option, this just calls gb.

i1 : R = QQ[a..d]

o1 = R

o1 : PolynomialRing

i2 : M = groebnerBasis random(R^1,R^{4:-2});

             1      12
o2 : Matrix R  <-- R

i3 : netList (ideal M)_*

     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                              2                                                                  2                                                                                                                                                |
o3 = |34683732405a*c + 45403122888b*c + 22182631996c  + 11323472282a*d - 41881080780b*d + 2779363080c*d - 253203232590d                                                                                                                                                 |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |          2                              2                                                             2                                                                                                                                                          |
     |770749609b  - 1489880430b*c - 1206513462c  - 764007339a*d + 2911930056b*d - 842774400c*d + 18048679470d                                                                                                                                                           |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                        2                                                             2                                                                                                                                                           |
     |2312248827a*b - 357142806b*c + 81459112c  - 133654921a*d + 2336496078b*d + 3628921500c*d + 2467276010d                                                                                                                                                            |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |           2                              2                                                               2                                                                                                                                                       |
     |4954818915a  + 1727798580b*c + 3294300352c  + 2649366284a*d - 3970948296b*d + 4689606600c*d - 16197062400d                                                                                                                                                        |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                            2                                                   2                                                 2                                                 2                                               3             |
     |2724180671777819199069165996934969767349656c d + 31845529801959348715471340786533881342901167a*d  - 1758348369423550347810834068780525283695409b*d  - 5372490612166096311629940357135360732099075c*d  - 2881093661539206608396012562951334747150915d              |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                                                2                                                2                                                 2                                              3               |
     |583753001095246971229106999343207807289212b*c*d - 3728810555658846683515975313361210989728605a*d  + 137799714794694464757265704544389102727489b*d  + 1500656765398473555725586984645338388916875c*d  - 898085195860771959010006839163336134979845d                |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                              3                                                     2                                                    2                                                    2                                                  3|
     |429058455805006523853393644517257738357570820c  - 17495207858398667480033402848421761795198333065a*d  + 1246643613465577981802208108718472086159163211b*d  + 2782860869907241497772806155921074353376274385c*d  - 1570129770248436614565473340925236717563334565d |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                              2                                                  2                                                 2                                                  2                                                3          |
     |4086271007666728798603748995402454651024484b*c  + 62714189465976758566126784397257013896537565a*d  - 8375647777608618502085655902149259134237053b*d  - 33088413658761466303154964299241839752403175c*d  + 32984959329852993773956930260208666186375625d           |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                                      3                                                                                       4                                                                                   |
     |10837986594736364916361768908557335864898281192965032938353609576704055374610142101c*d  + 18068067339143793803051172652116936054176497795592352732646922051688387292128013889d                                                                                    |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                                      3                                                                                       4                                                                                   |
     |25288635387718184804844127453300450351429322783585076856158422345642795874090331569b*d  - 44321163197070688756073163897201067283499684039938325395295980988114547849112672140d                                                                                    |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                                      3                                                                                       4                                                                                   |
     |10837986594736364916361768908557335864898281192965032938353609576704055374610142101a*d  + 11156976348926947118151767119694850438216806951444649109856824320485142163381766816d                                                                                    |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     | 5                                                                                                                                                                                                                                                                |
     |d                                                                                                                                                                                                                                                                 |
     +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

With a Strategy option, the code is experimental, subject to interface changes, and might have bugs. So use at your own risk! However, it appears to work correctly and is often very fast, in cases where it applies. If you encounter any bugs, please let us know!

If either "MGB" (MGB stands for mathicGB, the name of the package used), or "F4" is given for the Strategy, then experimental code (written by Bjarke Roune and M. Stillman) is used. The plan is for this to become the default version for Gröbner bases in later versions of Macaulay2. But for now, it is experimental.

These strategies only work for ideals in polynomial rings over a finite field ZZ/p. In other cases, either an error will be given, or the current default Gröbner basis algorithm will be used.

i4 : R = ZZ/101[a..e]

o4 = R

o4 : PolynomialRing

i5 : I = ideal sub(random(R^1, R^{4:-2}), e=>1);

o5 : Ideal of R

i6 : netList I_*

     +------------------------------------------------------------------------------------------------------+
     |   2            2                     2                              2                                |
o6 = |47a  - 49a*b + b  + 28a*c + 40b*c + 7c  - 18a*d - 22b*d + 30c*d - 17d  + 46a + 10b + 13c - 13d + 3    |
     +------------------------------------------------------------------------------------------------------+
     |     2             2                     2                              2                             |
     |- 41a  + 8a*b - 46b  + 8a*c + 49b*c + 23c  - 29a*d - 18b*d - 28c*d + 18d  + 30a + 42b + 15c - 16d - 46|
     +------------------------------------------------------------------------------------------------------+
     |   2              2                      2                              2                             |
     |12a  - 18a*b - 37b  + 27a*c - 23b*c + 20c  - 21a*d + 44b*d + 19c*d - 47d  + 23a - 39b - 28d + 47      |
     +------------------------------------------------------------------------------------------------------+
     |     2             2                     2                             2                              |
     |- 28a  + 6a*b - 29b  - 9a*c + 26b*c - 33c  - 33a*d + 5b*d - 28c*d + 44d  + 28a - 37b + 42c + 30d + 4  |
     +------------------------------------------------------------------------------------------------------+

i7 : gbI = ideal groebnerBasis(I, Strategy=>"MGB");

o7 : Ideal of R

i8 : netList gbI_*

     +--------------------------------------------------------------------------------------------------------------------+
     |                 2                              2                                                                   |
o8 = |a*c - 48b*c - 36c  + 44a*d + 11b*d + 16c*d + 35d  - 30a - 49b + c + 46d - 44                                        |
     +--------------------------------------------------------------------------------------------------------------------+
     | 2              2                              2                                                                    |
     |b  - 49b*c + 41c  - 29a*d + 15b*d + 13c*d - 21d  + 29a + 14b + c - 11d - 38                                         |
     +--------------------------------------------------------------------------------------------------------------------+
     |                 2                              2                                                                   |
     |a*b + 10b*c + 49c  + 34a*d - 28b*d - 34c*d - 14d  + 16a + 18b - c - 7d - 40                                         |
     +--------------------------------------------------------------------------------------------------------------------+
     | 2              2                      2                                                                            |
     |a  - 30b*c - 12c  + 46a*d + 22c*d + 42d  - 36a - 8b + 33c - 24d - 49                                                |
     +--------------------------------------------------------------------------------------------------------------------+
     | 2         2       2        2      3              2                              2                                  |
     |c d - 18a*d  - 6b*d  + 48c*d  - 41d  + 35b*c - 36c  - 37a*d + 23b*d - 21c*d - 46d  - 9a + 12b + 5c + 11d - 35       |
     +--------------------------------------------------------------------------------------------------------------------+
     |             2        2        2      3              2                            2                                 |
     |b*c*d + 22a*d  + 49b*d  + 22c*d  - 10d  + 39b*c + 24c  + 13a*d - 44b*d - 9c*d - 4d  + 19a + 37b - 41c - 21d - 47    |
     +--------------------------------------------------------------------------------------------------------------------+
     | 3        2        2        2      3              2                              2                                  |
     |c  + 35a*d  - 22b*d  - 50c*d  - 20d  - 50b*c - 49c  - 31a*d + 10b*d + 16c*d + 17d  - 48a - 5b - 7c - 34d - 12       |
     +--------------------------------------------------------------------------------------------------------------------+
     |   2        2        2        2      3             2                            2                                   |
     |b*c  + 30a*d  - 29b*d  - 33c*d  - 45d  - 47b*c + 2c  - 40a*d + 14b*d + 4c*d - 2d  + 17a - 31b - 30c - 38d + 45      |
     +--------------------------------------------------------------------------------------------------------------------+
     |   3      4       2        2        2     3              2                            2                             |
     |c*d  + 36d  + 3a*d  + 47b*d  - 16c*d  - 2d  + 31b*c - 43c  - 17a*d + 3b*d - 18c*d - 3d  + 4a - 41b - 36c - 38d + 49 |
     +--------------------------------------------------------------------------------------------------------------------+
     |   3    4        2        2        2      3              2                            2                             |
     |b*d  + d  + 21a*d  + 10b*d  + 17c*d  - 35d  - 20b*c - 27c  - 34a*d + b*d + 29c*d + 16d  - 6a + 44b - 11c + 27d - 43 |
     +--------------------------------------------------------------------------------------------------------------------+
     |   3      4        2        2        2      3            2                              2                           |
     |a*d  + 25d  - 44a*d  + 25b*d  + 25c*d  - 34d  + 8b*c - 9c  - 30a*d - 10b*d - 45c*d - 46d  + 4a + 6b + 43c - 46d + 16|
     +--------------------------------------------------------------------------------------------------------------------+
     | 5      4        2        2        2      3             2                     2                                     |
     |d  + 21d  - 50a*d  - 20b*d  + 16c*d  + 20d  + 9b*c + 25c  + 38a*d - 43c*d + 4d  - 36a + 35b - 33c + 44d - 11        |
     +--------------------------------------------------------------------------------------------------------------------+

Also implemented is a Faugere-like algorithm that is sometimes much faster (but also sometimes takes a large amount of memory).

i9 : gbTrace=1

o9 = 1

i10 : gbI = ideal groebnerBasis(I, Strategy=>"F4");
-- computing mgb F4 OptionTable{"Log" =>             }
                                "Reducer" => F4
                                "SPairGroupSize" => 0
                                "Threads" => null

o10 : Ideal of R

i11 : netList gbI_*

      +--------------------------------------------------------------------------------------------------------------------+
      |                 2                              2                                                                   |
o11 = |a*c - 48b*c - 36c  + 44a*d + 11b*d + 16c*d + 35d  - 30a - 49b + c + 46d - 44                                        |
      +--------------------------------------------------------------------------------------------------------------------+
      | 2              2                              2                                                                    |
      |b  - 49b*c + 41c  - 29a*d + 15b*d + 13c*d - 21d  + 29a + 14b + c - 11d - 38                                         |
      +--------------------------------------------------------------------------------------------------------------------+
      |                 2                              2                                                                   |
      |a*b + 10b*c + 49c  + 34a*d - 28b*d - 34c*d - 14d  + 16a + 18b - c - 7d - 40                                         |
      +--------------------------------------------------------------------------------------------------------------------+
      | 2              2                      2                                                                            |
      |a  - 30b*c - 12c  + 46a*d + 22c*d + 42d  - 36a - 8b + 33c - 24d - 49                                                |
      +--------------------------------------------------------------------------------------------------------------------+
      | 2         2       2        2      3              2                              2                                  |
      |c d - 18a*d  - 6b*d  + 48c*d  - 41d  + 35b*c - 36c  - 37a*d + 23b*d - 21c*d - 46d  - 9a + 12b + 5c + 11d - 35       |
      +--------------------------------------------------------------------------------------------------------------------+
      |             2        2        2      3              2                            2                                 |
      |b*c*d + 22a*d  + 49b*d  + 22c*d  - 10d  + 39b*c + 24c  + 13a*d - 44b*d - 9c*d - 4d  + 19a + 37b - 41c - 21d - 47    |
      +--------------------------------------------------------------------------------------------------------------------+
      | 3        2        2        2      3              2                              2                                  |
      |c  + 35a*d  - 22b*d  - 50c*d  - 20d  - 50b*c - 49c  - 31a*d + 10b*d + 16c*d + 17d  - 48a - 5b - 7c - 34d - 12       |
      +--------------------------------------------------------------------------------------------------------------------+
      |   2        2        2        2      3             2                            2                                   |
      |b*c  + 30a*d  - 29b*d  - 33c*d  - 45d  - 47b*c + 2c  - 40a*d + 14b*d + 4c*d - 2d  + 17a - 31b - 30c - 38d + 45      |
      +--------------------------------------------------------------------------------------------------------------------+
      |   3      4       2        2        2     3              2                            2                             |
      |c*d  + 36d  + 3a*d  + 47b*d  - 16c*d  - 2d  + 31b*c - 43c  - 17a*d + 3b*d - 18c*d - 3d  + 4a - 41b - 36c - 38d + 49 |
      +--------------------------------------------------------------------------------------------------------------------+
      |   3    4        2        2        2      3              2                            2                             |
      |b*d  + d  + 21a*d  + 10b*d  + 17c*d  - 35d  - 20b*c - 27c  - 34a*d + b*d + 29c*d + 16d  - 6a + 44b - 11c + 27d - 43 |
      +--------------------------------------------------------------------------------------------------------------------+
      |   3      4        2        2        2      3            2                              2                           |
      |a*d  + 25d  - 44a*d  + 25b*d  + 25c*d  - 34d  + 8b*c - 9c  - 30a*d - 10b*d - 45c*d - 46d  + 4a + 6b + 43c - 46d + 16|
      +--------------------------------------------------------------------------------------------------------------------+
      | 5      4        2        2        2      3             2                     2                                     |
      |d  + 21d  - 50a*d  - 20b*d  + 16c*d  + 20d  + 9b*c + 25c  + 38a*d - 43c*d + 4d  - 36a + 35b - 33c + 44d - 11        |
      +--------------------------------------------------------------------------------------------------------------------+

Caveat

(1) The MGB and F4 options are experimental, work only over a finite field of char $< 2^{32}$, not over quotient rings, and not over exterior or Weyl algebras. However, these versions can be much faster when they apply. (2) The experimental versions do not stash their results into the ideal or module. (3) The experimental version only works for ideals currently.

Ways to use groebnerBasis:

groebnerBasis(Ideal)
groebnerBasis(Matrix)
groebnerBasis(Module)

For the programmer

The object groebnerBasis is a method function with options.

The source of this document is in Macaulay2Doc/functions/gb-doc.m2:316:0.

groebnerBasis -- Gröbner basis, as a matrix

Description

Caveat

See also

Ways to use groebnerBasis:

For the programmer