next | previous | forward | backward | up | index | toc

# 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 => , 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, , 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.