 Groebner - Maple Programming Help

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

Groebner

 Basis
 compute a Groebner basis

 Calling Sequence Basis(J, tord, opts)

Parameters

 J - a list or set of polynomials or a PolynomialIdeal tord - a MonomialOrder, a ShortMonomialOrder, or a name opts - optional arguments of the form keyword=value

Description

 • The Groebner[Basis] command computes reduced Groebner bases for ideals and modules over both commutative and skew polynomial rings.  This help page covers the most common case, which is a list or set of commutative polynomials defining an ideal. To compute Groebner bases for modules or to compute non-commutative Groebner bases, refer to the Basis_details help page.
 • A Groebner basis has the property that the leading monomial of every polynomial in the ideal is divisible by the leading monomial of some polynomial in the Groebner basis.  Division by a Groebner basis produces a unique remainder, or NormalForm.
 • A reduced Groebner basis is minimal, that is, no polynomial can be removed, and has the additional property that no monomial of any polynomial in the basis is divisible by any of the leading monomials (other than possibly itself). If all polynomials in a reduced Groebner basis have leading coefficient $1$, then this reduced basis is unique.
 • The argument J should be a list or set of polynomial generators, or a PolynomialIdeal data structure. PolynomialIdeals offer important performance advantages for large problems.  Groebner bases are saved in the structure in a format that permits many optimizations and type checking is avoided.
 • The argument tord is typically a monomial order.  For example, plex(x,y,z) denotes lexicographic order with x > y > z. For a list of available monomial orders refer to the Monomial Orders help page.  This argument can also be a name, in which case Groebner[Basis] will choose a monomial order and assign it to tord.  In this case the variables can be specified using an optional argument variables={...}, and the type of order can be specified by order=....  See the examples below.
 • Note: the monomial orders on this help page are all of type ShortMonomialOrder, where the polynomial algebra is inferred from the generators J.  For monomial orders constructed using the MonomialOrder command (including user-defined orders) see the Basis_details help page.
 • The optional argument characteristic=p specifies the ring characteristic, allowing you to do computations modulo p instead of over the rationals.  This option is ignored when the input is a PolynomialIdeal, however in that case you can specify J mod p as the first argument to obtain the desired result.  No algorithms are currently available to compute Groebner bases over the integers in Maple, so the coefficient ring must be a field.  Algebraic extensions can be specified using RootOfs or radicals.
 • The optional argument output=extended computes a transformation matrix C expressing the Groebner basis in terms of the generators J.  The output is a sequence (G, C) where G is the Groebner basis and C is a list of lists.  Each G[i] is equal to the dot product of C[i] with J.  This matrix is not stored, so if it is requested again it must be recomputed together with the Groebner basis.
 • The optional argument method=... specifies the algorithm or strategy used to compute the Groebner basis. For more information on this and other topics relevant to performance, refer to the Basis_algorithms help page.
 • Note that the gbasis command is deprecated.  It may not be supported in a future Maple release.

Examples

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $F≔\left[{x}^{3}-3xy,{x}^{2}y-2{y}^{2}+x\right]$
 ${F}{≔}\left[{{x}}^{{3}}{-}{3}{}{x}{}{y}{,}{{x}}^{{2}}{}{y}{-}{2}{}{{y}}^{{2}}{+}{x}\right]$ (1)
 > $\mathrm{Basis}\left(F,\mathrm{plex}\left(x,y\right)\right)$
 $\left[{{y}}^{{6}}{-}{3}{}{{y}}^{{3}}{,}{{y}}^{{5}}{-}{2}{}{{y}}^{{2}}{+}{x}\right]$ (2)
 > $\mathrm{Basis}\left(F,\mathrm{tdeg}\left(x,y\right)\right)$
 $\left[{{y}}^{{3}}{+}{x}{}{y}{,}{x}{}{{y}}^{{2}}{+}{{x}}^{{2}}{,}{{x}}^{{2}}{}{y}{-}{2}{}{{y}}^{{2}}{+}{x}{,}{{x}}^{{3}}{-}{3}{}{x}{}{y}\right]$ (3)
 > $\mathrm{Basis}\left(F,'\mathrm{tord}'\right)$
 $\left[{{y}}^{{6}}{-}{3}{}{{y}}^{{3}}{,}{{y}}^{{5}}{-}{2}{}{{y}}^{{2}}{+}{x}\right]$ (4)
 > $\mathrm{tord}$
 ${\mathrm{plex}}{}\left({x}{,}{y}\right)$ (5)
 > $\mathrm{Basis}\left(F,'\mathrm{tord}',\mathrm{order}='\mathrm{grlex}'\right)$
 $\left[{{x}}^{{3}}{-}{3}{}{x}{}{y}{,}{{x}}^{{2}}{}{y}{-}{2}{}{{y}}^{{2}}{+}{x}{,}{x}{}{{y}}^{{2}}{+}{{x}}^{{2}}{,}{{y}}^{{3}}{+}{x}{}{y}\right]$ (6)
 > $\mathrm{tord}$
 ${\mathrm{grlex}}{}\left({y}{,}{x}\right)$ (7)
 > $\mathrm{Basis}\left(F,\mathrm{plex}\left(x,y\right),\mathrm{characteristic}=3\right)$
 $\left[{{y}}^{{6}}{,}{{y}}^{{5}}{+}{{y}}^{{2}}{+}{x}\right]$ (8)
 > $G,C≔\mathrm{Basis}\left(F,\mathrm{plex}\left(x,y\right),\mathrm{output}=\mathrm{extended}\right)$
 ${G}{,}{C}{≔}\left[{{y}}^{{6}}{-}{3}{}{{y}}^{{3}}{,}{{y}}^{{5}}{-}{2}{}{{y}}^{{2}}{+}{x}\right]{,}\left[\left[\frac{{1}}{{2}}{}{x}{}{y}{+}\frac{{1}}{{2}}{+}\frac{{1}}{{2}}{}{{y}}^{{6}}{-}\frac{{3}}{{4}}{}{x}{}{{y}}^{{4}}{+}\frac{{1}}{{2}}{}{{y}}^{{3}}{-}\frac{{1}}{{4}}{}{{x}}^{{2}}{}{{y}}^{{5}}{,}{-}\frac{{1}}{{2}}{}{{x}}^{{2}}{-}\frac{{3}}{{4}}{}{x}{}{{y}}^{{5}}{+}\frac{{1}}{{2}}{}{{x}}^{{2}}{}{{y}}^{{3}}{-}{x}{}{{y}}^{{2}}{-}\frac{{1}}{{2}}{}{{y}}^{{4}}{+}\frac{{3}}{{2}}{}{y}{+}\frac{{1}}{{4}}{}{{x}}^{{3}}{}{{y}}^{{4}}\right]{,}\left[\frac{{1}}{{2}}{}{{y}}^{{2}}{-}\frac{{1}}{{2}}{}{x}{}{{y}}^{{3}}{,}{-}{x}{}{y}{+}{1}{+}\frac{{1}}{{2}}{}{{x}}^{{2}}{}{{y}}^{{2}}{-}\frac{{1}}{{2}}{}{{y}}^{{3}}\right]\right]$ (9)
 > $\left[\mathrm{seq}\left(\mathrm{expand}\left(\mathrm{add}\left(C\left[i\right]\left[j\right]F\left[j\right],j=1..\mathrm{nops}\left(F\right)\right)\right),i=1..\mathrm{nops}\left(C\right)\right)\right]$
 $\left[{{y}}^{{6}}{-}{3}{}{{y}}^{{3}}{,}{{y}}^{{5}}{-}{2}{}{{y}}^{{2}}{+}{x}\right]$ (10)

We construct a PolynomialIdeal data structure, which automatically keeps track of known Groebner bases.

 > $\mathrm{with}\left(\mathrm{PolynomialIdeals}\right):$
 > $J≔⟨F⟩$
 ${J}{≔}⟨{{x}}^{{3}}{-}{3}{}{x}{}{y}{,}{{x}}^{{2}}{}{y}{-}{2}{}{{y}}^{{2}}{+}{x}⟩$ (11)
 > $\mathrm{IdealInfo}\left[\mathrm{KnownGroebnerBases}\right]\left(J\right)$
 $\left\{{\mathrm{grlex}}{}\left({y}{,}{x}\right){,}{\mathrm{plex}}{}\left({x}{,}{y}\right){,}{\mathrm{tdeg}}{}\left({x}{,}{y}\right)\right\}$ (12)

The commands below do not perform any Groebner basis computations. The known Groebner bases are examined to see if a computation can be avoided.

 > $\mathrm{HilbertDimension}\left(J\right)$
 ${0}$ (13)
 > $\mathrm{UnivariatePolynomial}\left(y,J\right)$
 ${{y}}^{{6}}{-}{3}{}{{y}}^{{3}}$ (14)
 > $\mathrm{Homogenize}\left(J,h\right)$
 $⟨{h}{}{x}{}{y}{+}{{y}}^{{3}}{,}{-}{3}{}{h}{}{x}{}{y}{+}{{x}}^{{3}}{,}{h}{}{{x}}^{{2}}{+}{x}{}{{y}}^{{2}}{,}{{h}}^{{2}}{}{x}{-}{2}{}{h}{}{{y}}^{{2}}{+}{{x}}^{{2}}{}{y}⟩$ (15)

PolynomialIdeals can also be given to the NormalForm command and the corresponding Groebner basis is used automatically for the division.

 > $f≔{x}^{3}{y}^{2}-xy-1$
 ${f}{≔}{{x}}^{{3}}{}{{y}}^{{2}}{-}{x}{}{y}{-}{1}$ (16)
 > $\mathrm{NormalForm}\left(f,J,\mathrm{tdeg}\left(x,y\right)\right)$
 ${-}{x}{}{y}{-}{6}{}{{y}}^{{2}}{+}{3}{}{x}{-}{1}$ (17)
 > $\mathrm{NormalForm}\left(f,J,\mathrm{plex}\left(x,y\right)\right)$
 ${-}{3}{}{{y}}^{{5}}{+}{{y}}^{{3}}{-}{1}$ (18)

Compatibility

 • The Groebner[Basis] command was updated in Maple 2018.