Overview of the Groebner Package - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Packages : Groebner

Overview of the Groebner Package

 

Calling Sequence

Description

List of Groebner Package Commands

Examples

Calling Sequence

Groebner[command](arguments)

command(arguments)

Description

• 

This page describes the most common use of the Groebner package, namely calculations of Groebner bases and related operations for ideals in (commutative) polynomial rings.  The Groebner package is actually much more general and can handle polynomials in skew polynomial rings (see Groebner/details) and modules over (commutative or skew) polynomial rings (see Groebner Bases for Modules).

• 

Each command in the Groebner package can be accessed by using either the long form or the short form of the command name in the command calling sequence.

  

As the underlying implementation of the Groebner package is a module, it is also possible to use the form Groebner:-command to access a command from the package. For more information,  see Module Members.

List of Groebner Package Commands

• 

The following is a list of available commands.

Basis

FGLM

HilbertDimension

HilbertPolynomial

HilbertSeries

Homogenize

InitialForm

InterReduce

IsBasis

IsProper

IsZeroDimensional

LeadingCoefficient

LeadingMonomial

LeadingTerm

MatrixOrder

MaximalIndependentSet

MonomialOrder

MultiplicationMatrix

MultivariateCyclicVector

NormalForm

NormalSet

RationalUnivariateRepresentation

Reduce

RememberBasis

Solve

SPolynomial

SuggestVariableOrder

Support

TestOrder

ToricIdealBasis

TrailingTerm

UnivariatePolynomial

Walk

WeightedDegree

 

 

• 

To display the help page for a particular Groebner command, see Getting Help with a Command in a Package.

• 

Many predefined monomial orderings are available for use with Groebner commands.  This includes total degree, lexicographic, elimination, and matrix-defined orderings.  See the page on monomial orders.

• 

The TestOrder command checks if two monomials are in a given monomial ordering and can be used to sort a list of monomials by a given monomial ordering.

• 

The commands LeadingCoefficient, LeadingMonomial, and LeadingTerm compute the leading coefficient, leading monomial, and leading term of a polynomial respectively.

• 

The NormalForm command computes the normal form of a polynomial modulo an ideal.  The command Reduce returns the pseudo-remainder of a polynomial in the division by a list of polynomials.  The InterReduce command inter-reduces a list of polynomials.  Both the NormalForm and Reduce commands are usually used after a (reduced) Groebner basis has been computed.

• 

The Basis command computes a (reduced) Groebner bases of a polynomial ideal. The RememberBasis command makes a Groebner basis known to the system without performing any computation.

• 

The IsBasis command tests if a basis is a Groebner basis for a given monomial ordering.

• 

The Solve command preprocesses a set of generators in view of solving.

• 

The SPolynomial command computes the S-polynomial of two polynomials.

• 

The UnivariatePolynomial command finds univariate polynomials of least degree in a polynomial ideal.

• 

The commands IsZeroDimensional and IsProper decide whether an ideal has finitely many solutions, or at least one solution, respectively.

• 

The commands HilbertDimension, HilbertPolynomial, and HilbertSeries compute the Hilbert dimension, Hilbert polynomial, and Hilbert series of an ideal, respectively.

• 

A typical test of membership in an ideal is:

  

1. Perform a Groebner basis computation to find a Groebner basis of the ideal (usually with tdeg);

  

2. Call Groebner[NormalForm] to test whether it returns zero.

• 

A typical use of Groebner bases for elimination is:

  

1. Compute a Groebner basis with respect to an elimination monomial order (with the lexdeg syntax);

  

2. Select those polynomials in which the indeterminate to be eliminated has disappeared.

• 

When relevant, most commands of the Groebner package accept algebraic numbers and algebraic functions denoted by I, radicals, or RootOfs in their the inputs. Exceptions are MultiplicationMatrix, NormalSet, and Solve. Also when relevant, they accept PolynomialIdeal data structures in their input.

• 

You can use the Groebner package in conjunction with the PolynomialIdeals package.

  

Note: Both packages have the following exports of the same name and almost identical functionality: HilbertDimension, IsProper, IsZeroDimensional, and UnivariatePolynomial. After loading both packages using with, these names refer to the corresponding exports of the most recently loaded package, but you can still access the exports with the same name in the other package using the long form, that is, by prepending the package name.

Examples

withGroebner

Basis,FGLM,HilbertDimension,HilbertPolynomial,HilbertSeries,Homogenize,InitialForm,InterReduce,IsBasis,IsProper,IsZeroDimensional,LeadingCoefficient,LeadingMonomial,LeadingTerm,MatrixOrder,MaximalIndependentSet,MonomialOrder,MultiplicationMatrix,MultivariateCyclicVector,NormalForm,NormalSet,RationalUnivariateRepresentation,Reduce,RememberBasis,SPolynomial,Solve,SuggestVariableOrder,Support,TestOrder,ToricIdealBasis,TrailingTerm,UnivariatePolynomial,Walk,WeightedDegree

(1)

Groebner Bases and Ideal Membership Testing

Bx+y+z,xy+yz+zx,xyz1

Bx+y+z,xy+zx+yz,xyz1

(2)

First we compute a Groebner basis G for the ideal generated by B using the graded reverse lexicographical monomial ordering tdeg with x>y>z.

GBasisB,tdegx,y,z

Gx+y+z,y2+yz+z2,z31

(3)

Thus z31 is in the ideal generated by B.  Notice that B is symmetric in the variables and hence x31 and y31 must also be in the ideal. We test this as follows.

NormalFormx31,G,tdegx,y,z

0

(4)

NormalFormx2,G,tdegx,y,z

yz

(5)

Thus, x31 is in the ideal generated by B while x2 is not.  We show that B is not a Groebner basis and G is.

IsBasisB,tdegx,y,z

false

(6)

IsBasisG,tdegx,y,z

true

(7)

For our second example we triangularize a polynomial system {x2+y2=1, x+y+1=0} by computing a Groebner basis using the pure lexicographical monomial ordering plex with x>y.

Bx2+y21,x+y+1

Bx2+y21,x+y+1

(8)

GBasisB,plexx,y

Gy2+y,x+y+1

(9)

Note Maple does not automatically order the terms of polynomials in the monomial ordering being used.  Here are the leading monomials of the polynomials in G.

LeadingMonomialG,plexx,y

y2,x

(10)

From the triangular form of the Groebner basis, it is easy to see how to solve the system.  Note, the solutions of the original system are the same as the zeros of the polynomials in the Groebner basis.  This is true for any monomial ordering.

factorG

yy+1,x+y+1

(11)

solveG,x,y

x=−1,y=0,x=0,y=−1

(12)

Monomial Orderings

Besides the tdeg monomial ordering for "fast" normal form computation and the plex monomial ordering for "slow" triangularization, lexdeg orderings are available for more efficient elimination.  For the purpose of generality, the Groebner package implements weighted monomial orderings (wdeg) and matrix-defined monomial orderings.  Products of orders and user-defined orderings are also available.

For our first example, we find the implicit equation x2+y21 of a circle from its rational parametrization by eliminating the parameter t.

paramx=1t21+t2,y=2t1+t2

paramx=t2+1t2+1,y=2tt2+1

(13)

First we convert to polynomials and clear the fractions.

Bmapeq→numerlhseqrhseq,param

Bt2y2t+y,t2x+t2+x1

(14)

GBasisB,lexdegt,x,y

Gx2+y21,ty+x1,tx+ty

(15)

removehas,G,t

x2+y21

(16)

As a second example, here is a calculation that is performed far faster by using lexdeg than by using plex.  Assume that we want to find the extrema of

φx3+2xyzz2

φx3+2xyzz2

(17)

on the sphere

constx2+y2+z21

constx2+y2+z21

(18)

Using the method of Lagrange multipliers, we compute

Gseqvφvconstt,v=x,y,z,const

G2ty+2zx,2zt+2xy2z,2tx+3x2+2yz,x2+y2+z21

(19)

and we eliminate the multiplier t by the use of an appropriate monomial order

GBBasisG,lexdegt,x,y,z

GBx2+y2+z21,17yz213z3xy+17zx+13z,17y2z+7z36xy7z,17y3+11z37xy17zx17y11z,xy2z2xyz,48z463xyz34z2x34yz48z2,408xz3+233z3+65xy408zx233z,6xyz+6z2x+3yz+2z2+2t3x

(20)

removehas,GB,t

x2+y2+z21,17yz213z3xy+17zx+13z,17y2z+7z36xy7z,17y3+11z37xy17zx17y11z,xy2z2xyz,48z463xyz34z2x34yz48z2,408xz3+233z3+65xy408zx233z

(21)

In the general case, we would have to compute numerical estimates and substitute into φ.  Here, we can go further and compute all the possible values for z by the elimination of x and y.

GB2Basis,lexdegx,y,z

GB21152z71763z5+655z344z,1152z6+118yz3+1605z4118yz453z2,1152z5+3835yz21404z3+3835zx+2556z,6912z5+3835y2z+10751z33839z,19584z5+25987z3+3835xy6403z,x2+y2+z21,9216z5+3835y3+3835yz2+11778z33835y2562z

(22)

opremovehas,GB2,x,y

1152z71763z5+655z344z

(23)

sol_zsolve,z

sol_z0,1,−1,23,23,2216,2216

(24)

Substituting into the system yields the possible extremal points.

seqop@map`union`,solveGB2z=i|GB2z=i,x,y,z=i,i=sol_z

x=1,y=0,z=0,x=−1,y=0,z=0,x=0,y=1,z=0,x=0,y=−1,z=0,x=0,y=0,z=1,x=0,y=0,z=−1,x=23,y=13,z=23,x=23,y=13,z=23,x=38,y=32216,z=2216,x=38,y=32216,z=2216

(25)

Finally, we get the minimum and maximum values.

minmap2eval,φ,,maxmap2eval,φ,

2827,1

(26)

Similar calculations using plex require a significantly longer amount of time.

Ideal Invariants

The dimension of a variety (zero for isolated points, one for lines, two for planes) is the Hilbert dimension of the corresponding annihilating ideal. The Groebner package allows one to compute this Hilbert dimension, together with the Hilbert polynomial and the Hilbert series.

As a first example, here is a zero-dimensional ideal, corresponding to finitely many points in the variety.

G3y28z3,x22zx+5,3y3+8xy2:

HilbertDimensionG,tdegy,x,z

0

(27)

HilbertSeriesG,tdegy,x,z,s

s5+3s4+5s3+5s2+3s+1

(28)

s=1|s=1

18

(29)

HilbertPolynomialG,tdegy,x,z,s

0

(30)

As another example, here is an ideal of positive dimension.

Gx3y2+3x2y2+y3+1:

HilbertDimensionG,tdegx,y

1

(31)

HilbertSeriesG,tdegx,y,s

s4+s3+s2+s+11+s

(32)

series,s,10

1+2s+3s2+4s3+5s4+5s5+5s6+5s7+5s8+5s9+Os10

(33)

HilbertPolynomialG,tdegy,x,s

5

(34)

Ground Fields

The Groebner package supports transcendental and algebraic extensions of the field of rational numbers and finite fields. This includes algebraic number fields. Here is a sample computation with complex numbers in ,2x,y.

Gx2+y2I,2y+2x21

Gx2+y2I,2y+2x21

(35)

GBBasisG,tdegx,y

GB2x+2y32,62y+4y2+92I

(36)

Computations with modular integers are supported as well, by means of an option.

Gx22xz+5,xy2+yz3,3y28z3:

Gmod5

x2+3zx,yz3+xy2,2z3+3y2

(37)

BasisG,plexx,y,z,characteristic=5

z8+z7,3z6+yz4,4z3+y2,xz3+yz3,x2+3zx

(38)

Standard Bases

As another example, the Groebner package allows for the computation of standard bases.  We define the leading monomial of a polynomial as its minimum monomial instead of its maximum monomial by using a plex_min monomial order rather than a plex monomial order.

L1+x+y+z+x2+y2+z2

Lx2+y2+z2+x+y+z+1

(39)

LeadingMonomialL,plexx,y,z

x2

(40)

LeadingMonomialL,plex_minx,y,z

1

(41)

Then Groebner bases can be computed for homogeneous ideals.  Here is an example in x,y,z,w.

Gyw2z3,xw3z4

Gyw2z3,xw3z4

(42)

Compare the usual Groebner basis

BasisG,plexw,x,y,z

x2z6y3z5,wy2z4xz6,wxz3yz4,yw2z3,xw3z4

(43)

which allows for divisions by decreasing powers:

Reducew5x3y2z,,plexw,x,y,z

y4z7

(44)

and the standard basis

BasisG,plex_minw,x,y,z

w4x2z+w4y3,w4y2+w3xz2,xw3+w2yz,yw2+z3

(45)

which allows for divisions by increasing powers:

Reducew5x3y2z,,plex_minw,x,y,z

w6x4y

(46)

See Also

Groebner/details

Groebner[Basis]

PolynomialIdeals

PolynomialIdeals Example Worksheet

PolynomialIdeals[PolynomialIdeal]

RegularChains

Terminology Used in Groebner

UsingPackages

with