 Algorithms used by Groebner[Basis] - Maple Programming Help

Home : Support : Online Help : Mathematics : Algebra : Polynomials : Groebner : Groebner/Basis_algorithms

Algorithms used by Groebner[Basis]

 Calling Sequence Basis(J, tord, method=meth)

Parameters

 J - a list or set of polynomials or a PolynomialIdeal tord - a MonomialOrder, a ShortMonomialOrder, or a name meth - one of the methods described below

Description

 • The Groebner[Basis] command currently relies on a combination of five different algorithms to compute Groebner bases for various monomial orders and domains.  This help page documents these algorithms and their relative performance characteristics to help you decide what algorithm to use should the default choice prove unsatisfactory.  The algorithm is specified using an optional argument method=meth.
 • method=fgb runs a compiled C implementation of the F4 algorithm. It supports rational number and integer mod p coefficients, where p < 2^31. It supports tdeg orders and lexdeg orders with two blocks of variables. It does not support parameters (that is, coefficients in a rational function field) or the output=extended option.  The algorithm is Monte-Carlo probabilistic and the probability of error is expected to be less than 10^(-18).
 • method=maplef4 runs a Maple implementation of the F4 algorithm.  This implementation supports all monomial orders and coefficient fields as well as computations in non-commutative Ore algebras.  This is an exact implementation which does not use modular methods. The output=extended option is currently not supported.
 • method=buchberger runs the traditional Maple implementation of the Buchberger algorithm. This algorithm supports all domains, monomial orders and options such as output=extended. It is generally outperformed by F4 in most situations, but one notable exception is when a polynomial has been added to a Groebner basis and the basis is being recomputed. The implementation is based on Gebauer and Moller and uses the normal selection strategy.
 • method=fglm runs the Groebner basis conversion algorithm of Faugere, Gianni, Lazard, and Mora. This algorithm supports all commutative domains, but requires the ideal to be zero-dimensional. See the Groebner[FGLM] help page for more details.  When this method is specified, Groebner[Basis] will choose one of the known Groebner bases (or compute one if none are known) and run Groebner[FGLM].
 • method=walk runs the Groebner Walk conversion algorithm of Collart, Kalkbrener, and Mall, which supports all commutative domains and monomial orders.   See the Groebner[Walk] help page for more details.  When this method is specified, Groebner[Basis] will choose one of the known Groebner bases (or compute one if none are known) and run Groebner[Walk].  The Groebner walk is typically slower than FGLM for zero-dimensional ideals.
 • In addition to the algorithms above, you can specify an overall strategy using the method=... option and Groebner[Basis] will choose whatever algorithms are appropriate.  The strategies are as follows:
 • method=direct runs the fastest general purpose direct method.  This is currently the compiled F4 or Maple's F4 as a fallback. As better algorithms are implemented, this strategy will be updated to reflect the state-of-the-art method. Thus, calling Groebner[Basis] with method=direct is a way to ensure that your code always uses the fastest direct algorithm; even on future Maple releases.
 • method=convert runs the fastest applicable conversion method, which is either FGLM or the Groebner Walk, depending on the monomial order and whether the ideal is zero-dimensional. This strategy is recommended for monomial orders that eliminate variables.  For 'plex', 'lexdeg' and 'prod' orders, the strategy is to run FGLM if possible.  For all other orders and for non-zero-dimensional ideals, the Groebner Walk is used.
 • method=default runs the default strategy, which is subject to change in the future. Currently this is method=direct for 'tdeg', 'wdeg', 'grlex' and 'matrix' orders and non-commutative problems, and method=convert for 'plex', 'lexdeg' and 'prod' orders in the commutative case.
 • Setting infolevel[GroebnerBasis] to a value between 1 and 5 directs all of the algorithms to print information about their progress and performance.

Examples

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > ${\mathrm{infolevel}}_{\mathrm{GroebnerBasis}}≔2:$
 > $F≔\left[{x}^{2}-2xz+5,x{y}^{2}+y{z}^{3},3{y}^{2}-8{z}^{3}\right]$
 ${F}{≔}\left[{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}{,}{y}{}{{z}}^{{3}}{+}{x}{}{{y}}^{{2}}{,}{-}{8}{}{{z}}^{{3}}{+}{3}{}{{y}}^{{2}}\right]$ (1)
 > $\mathrm{Basis}\left(F,\mathrm{tdeg}\left(x,y,z\right)\right)$
 -> MGb F4 algorithm 1: prime=1250415347   0%  use 4 of 4, 0.001 sec 2: prime=1591063783   0%  0 out of 4, 0.000 sec 3: prime=1078566851   0%  0 out of 4, 0.001 sec 4: prime=1616347771 100%  4 out of 4, 0.001 sec 4 primes basis:       0.002 chrem:       0.000 iratr:       0.001 other:       0.001 total:       0.004  total time:         0.005 sec
 $\left[{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}{,}{8}{}{{z}}^{{3}}{-}{3}{}{{y}}^{{2}}{,}{8}{}{x}{}{{y}}^{{2}}{+}{3}{}{{y}}^{{3}}{,}{9}{}{{y}}^{{4}}{+}{48}{}{{y}}^{{3}}{}{z}{+}{320}{}{{y}}^{{2}}\right]$ (2)
 > $\mathrm{Basis}\left(F,\mathrm{grlex}\left(x,y,z\right)\right)$
 -> F4 algorithm  total time:         0.005 sec
 $\left[{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}{,}{8}{}{{z}}^{{3}}{-}{3}{}{{y}}^{{2}}{,}{8}{}{x}{}{{y}}^{{2}}{+}{3}{}{{y}}^{{3}}{,}{9}{}{{y}}^{{4}}{+}{48}{}{{y}}^{{3}}{}{z}{+}{320}{}{{y}}^{{2}}\right]$ (3)
 > $\mathrm{Basis}\left(F,\mathrm{plex}\left(x,y,z\right)\right)$
 -> FGLM algorithm FGLM algorithm 1: prime=1982249443   0%  5 elements, 0.001 sec 2: prime=1804384093   0%  0 out of 5, 0.000 sec 3: prime=803430139   0%  0 out of 5, 0.001 sec 4: prime=1443424909 100%  5 out of 5, 0.000 sec 4 primes basis:       0.001 chrem:       0.000 iratr:       0.000 other:       0.001 total:       0.002
 $\left[{9}{}{{z}}^{{9}}{-}{96}{}{{z}}^{{8}}{+}{240}{}{{z}}^{{6}}{+}{1600}{}{{z}}^{{3}}{,}{-}{3}{}{{z}}^{{8}}{+}{32}{}{{z}}^{{7}}{-}{40}{}{{z}}^{{5}}{+}{80}{}{y}{}{{z}}^{{3}}{,}{-}{8}{}{{z}}^{{3}}{+}{3}{}{{y}}^{{2}}{,}{9}{}{{z}}^{{8}}{-}{96}{}{{z}}^{{7}}{+}{120}{}{{z}}^{{5}}{+}{640}{}{x}{}{{z}}^{{3}}{,}{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}\right]$ (4)
 > $\mathrm{IsZeroDimensional}\left(F\right)$
 ${\mathrm{true}}$ (5)
 > $\mathrm{Basis}\left(F,\mathrm{lexdeg}\left(\left[x\right],\left[y,z\right]\right),\mathrm{method}=\mathrm{walk}\right)$
 -> Groebner Walk  total time:         0.001 sec
 $\left[{8}{}{{z}}^{{3}}{-}{3}{}{{y}}^{{2}}{,}{9}{}{{y}}^{{4}}{+}{48}{}{{y}}^{{3}}{}{z}{+}{320}{}{{y}}^{{2}}{,}{8}{}{x}{}{{y}}^{{2}}{+}{3}{}{{y}}^{{3}}{,}{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}\right]$ (6)
 > $\mathrm{Basis}\left(F,\mathrm{lexdeg}\left(\left[x,y\right],\left[z\right]\right),\mathrm{method}=\mathrm{direct}\right)$
 -> MGb F4 algorithm 1: prime=190086331   0%  use 0 of 5, 0.001 sec 2: prime=1058903669   0%  0 out of 5, 0.001 sec 3: prime=1448043907   0%  0 out of 5, 0.000 sec 4: prime=1811440879 100%  5 out of 5, 0.001 sec 4 primes basis:       0.003 chrem:       0.000 iratr:       0.000 other:       0.000 total:       0.003  total time:         0.014 sec
 $\left[{9}{}{{z}}^{{9}}{-}{96}{}{{z}}^{{8}}{+}{240}{}{{z}}^{{6}}{+}{1600}{}{{z}}^{{3}}{,}{-}{3}{}{{z}}^{{8}}{+}{32}{}{{z}}^{{7}}{-}{40}{}{{z}}^{{5}}{+}{80}{}{y}{}{{z}}^{{3}}{,}{9}{}{{z}}^{{8}}{-}{96}{}{{z}}^{{7}}{+}{120}{}{{z}}^{{5}}{+}{640}{}{x}{}{{z}}^{{3}}{,}{-}{8}{}{{z}}^{{3}}{+}{3}{}{{y}}^{{2}}{,}{{x}}^{{2}}{-}{2}{}{x}{}{z}{+}{5}\right]$ (7)
 > $\mathrm{Basis}\left(F,\mathrm{plex}\left(z,y,x\right),\mathrm{method}=\mathrm{direct}\right)$
 -> F4 algorithm  total time:         0.010 sec
 $\left[{3}{}{{x}}^{{12}}{-}{64}{}{{x}}^{{11}}{+}{90}{}{{x}}^{{10}}{-}{960}{}{{x}}^{{9}}{+}{1125}{}{{x}}^{{8}}{-}{4800}{}{{x}}^{{7}}{+}{7500}{}{{x}}^{{6}}{-}{8000}{}{{x}}^{{5}}{+}{28125}{}{{x}}^{{4}}{+}{56250}{}{{x}}^{{2}}{+}{46875}{,}{8}{}{{x}}^{{7}}{+}{3}{}{{x}}^{{6}}{}{y}{+}{120}{}{{x}}^{{5}}{+}{45}{}{{x}}^{{4}}{}{y}{+}{600}{}{{x}}^{{3}}{+}{225}{}{{x}}^{{2}}{}{y}{+}{1000}{}{x}{+}{375}{}{y}{,}{-}{9}{}{{x}}^{{11}}{+}{192}{}{{x}}^{{10}}{-}{255}{}{{x}}^{{9}}{+}{2560}{}{{x}}^{{8}}{-}{2925}{}{{x}}^{{7}}{+}{9600}{}{{x}}^{{6}}{-}{16875}{}{{x}}^{{5}}{-}{48750}{}{{x}}^{{3}}{-}{40000}{}{{x}}^{{2}}{+}{5625}{}{{y}}^{{2}}{-}{56250}{}{x}{,}{3}{}{{x}}^{{11}}{-}{64}{}{{x}}^{{10}}{+}{90}{}{{x}}^{{9}}{-}{960}{}{{x}}^{{8}}{+}{1125}{}{{x}}^{{7}}{-}{4800}{}{{x}}^{{6}}{+}{7500}{}{{x}}^{{5}}{-}{8000}{}{{x}}^{{4}}{+}{28125}{}{{x}}^{{3}}{+}{46875}{}{x}{+}{18750}{}{z}\right]$ (8)
 > $\mathrm{Basis}\left(F,\mathrm{wdeg}\left(\left[1,2,3\right],\left[x,y,z\right]\right),\mathrm{method}=\mathrm{convert}\right)$
 -> Groebner Walk  total time:         0.012 sec
 $\left[{-}{{x}}^{{2}}{+}{2}{}{x}{}{z}{-}{5}{,}{{x}}^{{4}}{-}{3}{}{x}{}{{y}}^{{2}}{+}{10}{}{{x}}^{{2}}{+}{20}{}{{z}}^{{2}}{+}{25}{,}{8}{}{x}{}{{y}}^{{2}}{+}{3}{}{{y}}^{{3}}{,}{-}{{x}}^{{5}}{+}{3}{}{{x}}^{{2}}{}{{y}}^{{2}}{-}{15}{}{{x}}^{{3}}{-}{50}{}{x}{-}{50}{}{z}{,}{8}{}{{x}}^{{6}}{+}{3}{}{{x}}^{{5}}{}{y}{+}{120}{}{{x}}^{{4}}{+}{45}{}{{x}}^{{3}}{}{y}{+}{600}{}{{x}}^{{2}}{+}{150}{}{x}{}{y}{+}{150}{}{y}{}{z}{+}{1000}{,}{3}{}{{x}}^{{8}}{-}{64}{}{{x}}^{{7}}{+}{90}{}{{x}}^{{6}}{-}{960}{}{{x}}^{{5}}{+}{900}{}{{x}}^{{4}}{-}{4800}{}{{x}}^{{3}}{+}{450}{}{x}{}{{y}}^{{2}}{+}{450}{}{{y}}^{{2}}{}{z}{+}{3750}{}{{x}}^{{2}}{-}{8000}{}{x}{+}{5625}\right]$ (9)

 > $\mathrm{with}\left(\mathrm{Ore_algebra}\right):$
 > ${\mathrm{infolevel}}_{\mathrm{GroebnerBasis}}≔4:$
 > $N≔3:$
 > $A≔\mathrm{diff_algebra}\left(\mathrm{seq}\left(\left[{\mathrm{D}}_{i},{x}_{i}\right],i=1..N\right),\mathrm{comm}=\left\{a,b,\mathrm{seq}\left({c}_{i},i=1..N\right)\right\},\mathrm{polynom}=\left\{\mathrm{seq}\left({x}_{i},i=1..N\right)\right\}\right):$
 > $S≔\mathrm{+}\left(\mathrm{seq}\left({x}_{i}{\mathrm{D}}_{i},i=1..N\right)\right):$
 > $P≔\mathrm{skew_product}\left(S+a,S+b,A\right):$
 > $F≔\left[\mathrm{seq}\left(\mathrm{skew_product}\left({\mathrm{D}}_{i},{x}_{i}{\mathrm{D}}_{i}+{c}_{i}-1,A\right)-P,i=1..N\right)\right]$
 ${F}{≔}\left[{{\mathrm{D}}}_{{1}}^{{2}}{}{{x}}_{{1}}{+}{{\mathrm{D}}}_{{1}}{}{{c}}_{{1}}{-}{{\mathrm{D}}}_{{1}}^{{2}}{}{{x}}_{{1}}^{{2}}{-}{2}{}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{2}}{}{{x}}_{{1}}{}{{x}}_{{2}}{-}{2}{}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{1}}{}{{x}}_{{3}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{1}}{}{{\mathrm{D}}}_{{1}}{-}{{\mathrm{D}}}_{{2}}^{{2}}{}{{x}}_{{2}}^{{2}}{-}{2}{}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{2}}{}{{x}}_{{3}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{2}}{}{{\mathrm{D}}}_{{2}}{-}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{3}}^{{2}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{3}}{}{{\mathrm{D}}}_{{3}}{-}{a}{}{b}{,}{{\mathrm{D}}}_{{2}}^{{2}}{}{{x}}_{{2}}{+}{{\mathrm{D}}}_{{2}}{}{{c}}_{{2}}{-}{{\mathrm{D}}}_{{1}}^{{2}}{}{{x}}_{{1}}^{{2}}{-}{2}{}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{2}}{}{{x}}_{{1}}{}{{x}}_{{2}}{-}{2}{}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{1}}{}{{x}}_{{3}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{1}}{}{{\mathrm{D}}}_{{1}}{-}{{\mathrm{D}}}_{{2}}^{{2}}{}{{x}}_{{2}}^{{2}}{-}{2}{}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{2}}{}{{x}}_{{3}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{2}}{}{{\mathrm{D}}}_{{2}}{-}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{3}}^{{2}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{3}}{}{{\mathrm{D}}}_{{3}}{-}{a}{}{b}{,}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{3}}{+}{{\mathrm{D}}}_{{3}}{}{{c}}_{{3}}{-}{{\mathrm{D}}}_{{1}}^{{2}}{}{{x}}_{{1}}^{{2}}{-}{2}{}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{2}}{}{{x}}_{{1}}{}{{x}}_{{2}}{-}{2}{}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{1}}{}{{x}}_{{3}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{1}}{}{{\mathrm{D}}}_{{1}}{-}{{\mathrm{D}}}_{{2}}^{{2}}{}{{x}}_{{2}}^{{2}}{-}{2}{}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{2}}{}{{x}}_{{3}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{2}}{}{{\mathrm{D}}}_{{2}}{-}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{3}}^{{2}}{-}\left({a}{+}{b}{+}{1}\right){}{{x}}_{{3}}{}{{\mathrm{D}}}_{{3}}{-}{a}{}{b}\right]$ (10)
 > $\mathrm{tord}≔\mathrm{tdeg}\left(\mathrm{seq}\left({\mathrm{D}}_{i},i=1..N\right),\mathrm{seq}\left({x}_{i},i=1..N\right)\right)$
 ${\mathrm{tord}}{≔}{\mathrm{tdeg}}{}\left({{\mathrm{D}}}_{{1}}{,}{{\mathrm{D}}}_{{2}}{,}{{\mathrm{D}}}_{{3}}{,}{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right)$ (11)
 > $T≔\mathrm{MonomialOrder}\left(A,\mathrm{tord}\right):$
 > $G≔\mathrm{Basis}\left(F,T\right):$
 -> F4 algorithm  domain: SkewAlgebra   coeffs: rat_fcn  basis: 1 of 3, syzygies: 3 of 3, degree: 4  0 x 0 with 3 rhs  basis: 2 of 5, syzygies: 1 of 3, degree: 4  2 x 2 with 1 rhs  basis: 3 of 6, syzygies: 2 of 2, degree: 5  4 x 4 with 2 rhs  basis: 5 of 8, syzygies: 4 of 4, degree: 6  12 x 12 with 4 rhs  basis: 8 of 11, syzygies: 11 of 12, degree: 7  39 x 39 with 11 rhs  basis: 10 of 13, syzygies: 10 of 10, degree: 8  75 x 75 with 10 rhs  basis: 12 of 15, syzygies: 7 of 7, degree: 9  94 x 94 with 7 rhs  symbolic prc        0.146 sec  inter reduce        0.003 sec  update pairs        0.008 sec  reduce basis        0.016 sec  total time:         0.174 sec -----------------------------
 > $\mathrm{Groebner}:-\mathrm{LeadingMonomial}\left(G,T\right)$
 $\left[{{\mathrm{D}}}_{{2}}^{{2}}{}{{x}}_{{2}}{,}{{\mathrm{D}}}_{{1}}^{{2}}{}{{x}}_{{1}}{,}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{2}}{}{{x}}_{{1}}{}{{x}}_{{2}}{,}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{1}}{}{{x}}_{{3}}{,}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{1}}{}{{x}}_{{3}}{,}{{x}}_{{2}}{}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{1}}{}{{x}}_{{3}}{,}{{\mathrm{D}}}_{{1}}^{{2}}{}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}{}{{x}}_{{2}}{}{{x}}_{{3}}{,}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}^{{3}}{}{{x}}_{{1}}{}{{x}}_{{3}}{,}{{\mathrm{D}}}_{{1}}{}{{\mathrm{D}}}_{{2}}{}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{2}}^{{2}}{}{{x}}_{{3}}{,}{{\mathrm{D}}}_{{1}}^{{2}}{}{{\mathrm{D}}}_{{3}}^{{3}}{}{{x}}_{{2}}{}{{x}}_{{3}}{,}{{\mathrm{D}}}_{{3}}^{{4}}{}{{x}}_{{1}}^{{2}}{}{{x}}_{{3}}^{{2}}{,}{{\mathrm{D}}}_{{1}}^{{2}}{}{{\mathrm{D}}}_{{2}}^{{2}}{}{{\mathrm{D}}}_{{3}}^{{2}}{}{{x}}_{{3}}^{{2}}\right]$ (12)

References

 Buchberger, B. "Grobner Bases: An algorithmic method in polynomial ideal theory." In Multidimensional systems theory, pp. 184-232, Reidel, 1985.
 Collart, S.; Kalkbrener, M.; and Mall, D. "Converting Bases with the Grobner Walk."  J. Symbolic Comput., Vol. 3, No. 4, (1997): 465-469.
 Faugere, J. "A New Efficient Algorithm for Computing Grobner Bases (F4)." Journal of Pure and Applied Algebra, Vol. 139, No. 1-3, (1999): 61-88.
 Faugere, J.; Gianni, P.; Lazard, D.; and Mora, T. "Efficient computation of zero-dimensional Grobner bases by change of ordering." J. Symbolic Comput., Vol. 16, (1993): 329-344.
 Gebauer, R., and Moller, H. "On an installation of Buchberger's algorithm." J. Symbolic Comput., Vol. 6, (1988): 275-286.
 Pearce, R., and Monagan, M. "A Sparse Algorithm for Polynomial Division with Application to F4." in preparation, 2006.