groebnerBasis -- Gröbner basis, as a matrix

Synopsis

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 Groebner 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 Groebner 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 = |11299050a*c + 6906531b*c + 5601225c  + 22096970a*d + 10053225b*d - 10138695c*d - 803376d                                                                                                                         |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |        2                      2                                                 2                                                                                                                               |
     |9039240b  + 154881b*c + 789975c  + 2230550a*d + 2703015b*d + 532455c*d + 1175328d                                                                                                                                |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                   2                                                    2                                                                                                                        |
     |45196200a*b - 2066697b*c - 3338775c  - 12617990a*d - 9788625b*d + 32683665c*d + 1493072d                                                                                                                         |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |         2                        2                                                    2                                                                                                                         |
     |45196200a  - 6222819b*c - 4176525c  - 40248530a*d - 6956775b*d + 33630555c*d + 7946624d                                                                                                                          |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                   2                                        2                                        2                                        2                                     3            |
     |3964358137052399637161262316798260c d + 594168029286400198536644282613264a*d  + 1337598604362667816823185742844123b*d  + 4247534217639439790300643591761688c*d  + 633197914362837742374002422591576d             |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                             2                                       2                                       2                                    3              |
     |792871627410479927432252463359652b*c*d + 907626632807183390740981849104360a*d  + 459506552743851049077630547055715b*d  - 482254086694892198398595134531980c*d  - 66868686610007296427523927539912d               |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                    3                                           2                                          2                                           2                                        3|
     |95144595289257591291870295603158240c  - 2841837152455056818005034904179920616a*d  - 976817993612564469525108588611526519b*d  + 2581638507104454154462789583156791212c*d  + 363076509596312359223810846059182696d |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                      2                                         2                                         2                                         2                                      3     |
     |19028919057851518258374059120631648b*c  + 64257621219904726957716712697169784a*d  + 33694597027785012215432150401502373b*d  - 62238924479127557348547050385679908c*d  - 7226409689483732200678023735720504d      |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                    3                                                                    4                                                                       |
     |92377306833998610621043459166544878258614194423854521609030515753c*d  + 8498151665540849564229808863382997782054706833761464637212817128d                                                                        |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                     3                                                                     4                                                                     |
     |461886534169993053105217295832724391293070972119272608045152578765b*d  + 90396066568414181641497131332966112726627833129769050446288485072d                                                                      |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |                                                                     3                                                                     4                                                                     |
     |153962178056664351035072431944241463764356990706424202681717526255a*d  - 17326088189814257165217320650455953486068430536610639471432672813d                                                                      |
     +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     | 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 Groebner 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 Groebner 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 = |- 33a  - 19a*b - 39b  + 17a*c + 36b*c + 4c  - 20a*d + 9b*d + 13c*d + 22d  + 44a - 39b - 26c - 49d - 11|
     +------------------------------------------------------------------------------------------------------+
     |    2              2                     2                            2                               |
     |- 8a  + 43a*b - 22b  - 8a*c - 30b*c - 28c  + 36a*d + 41b*d - 6c*d - 9d  - 3a + 16b + 35c - 35d + 6    |
     +------------------------------------------------------------------------------------------------------+
     |   2             2                      2                              2                              |
     |40a  + 3a*b - 41b  - 31a*c - 49b*c + 30c  + 25a*d - 13b*d - 47c*d - 40d  - 2a + 4b + 27c + 37d - 35   |
     +------------------------------------------------------------------------------------------------------+
     |     2              2                      2                              2                           |
     |- 31a  - 39a*b - 48b  - 31a*c + 30b*c - 49c  - 48a*d - 37b*d + 28c*d + 46d  - 29a + 47b - 18c + d + 40|
     +------------------------------------------------------------------------------------------------------+

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

o7 : Ideal of R

i8 : netList gbI_*

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

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 + 12b*c - 46c  + 43a*d + 33b*d - 26c*d - 3d  - 15a + 42b + 49c - 13                                            |
      +-------------------------------------------------------------------------------------------------------------------+
      | 2              2                              2                                                                   |
      |b  + 28b*c + 40c  + 28a*d - 11b*d + 35c*d - 13d  - 29a + 18b - 15c - 17d + 15                                      |
      +-------------------------------------------------------------------------------------------------------------------+
      |                 2                              2                                                                  |
      |a*b + 21b*c + 15c  + 26a*d + 42b*d + 46c*d - 34d  - 32a + 8b + 38c + 14d - 49                                      |
      +-------------------------------------------------------------------------------------------------------------------+
      | 2              2                           2                                                                      |
      |a  + 15b*c - 43c  - 10a*d - 22b*d + c*d - 4d  - 39a + 28c + 38d - 2                                                |
      +-------------------------------------------------------------------------------------------------------------------+
      | 2         2        2        2      3              2                            2                                  |
      |c d - 34a*d  + 37b*d  + 29c*d  + 42d  + 10b*c - 11c  + 17a*d + 9b*d + 32c*d + 8d  - 39a - 36b + 32c + 25d - 49     |
      +-------------------------------------------------------------------------------------------------------------------+
      |             2       2        2      3              2                            2                                 |
      |b*c*d - 22a*d  + 5b*d  + 42c*d  - 21d  - 43b*c - 36c  - 2a*d - 13b*d - 3c*d + 25d  + 7a + 11b - 37c + 40d - 22     |
      +-------------------------------------------------------------------------------------------------------------------+
      | 3        2        2        2      3              2                            2                                   |
      |c  - 31a*d  + 30b*d  - 22c*d  - 29d  + 12b*c + 34c  + 41a*d - b*d - 27c*d + 33d  - 13a - 21b - 49c - 29d - 24      |
      +-------------------------------------------------------------------------------------------------------------------+
      |   2        2       2        2    3              2                              2                                  |
      |b*c  + 19a*d  + 2b*d  - 16c*d  - d  - 35b*c + 32c  - 19a*d - 33b*d - 24c*d - 37d  + 47a - 33b - 31c - 28d - 12     |
      +-------------------------------------------------------------------------------------------------------------------+
      |   3      4        2        2     3              2                            2                                    |
      |c*d  - 43d  - 33a*d  - 12b*d  + 7d  - 18b*c - 40c  - 16a*d - 5b*d - 5c*d + 30d  + 32a - 26b - 43c + 20d + 34       |
      +-------------------------------------------------------------------------------------------------------------------+
      |   3      4        2       2        2      3            2                            2                             |
      |b*d  - 32d  - 16a*d  + 3b*d  - 34c*d  - 33d  + b*c + 24c  + 39a*d - b*d - 45c*d + 13d  - 49a + 18b - 3c + 2d + 34  |
      +-------------------------------------------------------------------------------------------------------------------+
      |   3      4        2        2        2      3              2                         2                             |
      |a*d  - 15d  + 10a*d  - 25b*d  - 43c*d  + 21d  - 15b*c + 46c  - 3a*d - b*d - 5c*d - 8d  - 29a + 19b + 30c - 8d + 21 |
      +-------------------------------------------------------------------------------------------------------------------+
      | 5      4        2        2        2      3              2                            2                            |
      |d  + 34d  + 41a*d  - 21b*d  - 39c*d  + 10d  - 16b*c - 44c  - 13a*d + 47b*d + c*d + 44d  - 29a - 18b + 25c + 2d - 19|
      +-------------------------------------------------------------------------------------------------------------------+

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