Package Overview - Maple Help

All Products Maple MapleSim

Home : Support : Online Help : Mathematics : Algebra : Polynomials : Groebner : Package Overview

Overview of the Groebner Package

	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.

•	The long form, Groebner:-command, is always available. The short form can be used after loading the package.

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

>	$with (Groebner)$

$[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

>	$B ≔ [x + y + z, x y + y z + z x, x y z - 1]$

$B ≔ [x + y + z, x y + z x + y z, x y z - 1]$

(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$ .

>	$G ≔ Basis (B, tdeg (x, y, z))$

$G ≔ [x + y + z, y^{2} + y z + z^{2}, z^{3} - 1]$

(3)

Thus $z^{3} - 1$ is in the ideal generated by B. Notice that B is symmetric in the variables and hence $x^{3} - 1$ and $y^{3} - 1$ must also be in the ideal. We test this as follows.

>	$NormalForm (x^{3} - 1, G, tdeg (x, y, z))$

$0$

(4)

>	$NormalForm (x^{2}, G, tdeg (x, y, z))$

$y z$

(5)

Thus, $x^{3} - 1$ is in the ideal generated by B while $x^{2}$ is not. We show that B is not a Groebner basis and G is.

>	$IsBasis (B, tdeg (x, y, z))$

$false$

(6)

>	$IsBasis (G, tdeg (x, y, z))$

$true$

(7)

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

>	$B ≔ [x^{2} + y^{2} - 1, x + y + 1]$

$B ≔ [x^{2} + y^{2} - 1, x + y + 1]$

(8)

>	$G ≔ Basis (B, plex (x, y))$

$G ≔ [y^{2} + 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.

>	$LeadingMonomial (G, plex (x, y))$

$[y^{2}, 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.

>	$factor (G)$

$[y (y + 1), x + y + 1]$

(11)

>	$solve (G, \{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 $x^{2} + y^{2} - 1$ of a circle from its rational parametrization by eliminating the parameter $t$ .

>	$param ≔ \{x = \frac{1 - t^{2}}{1 + t^{2}}, y = \frac{2 t}{1 + t^{2}}\}$

$param ≔ \{x = \frac{- t^{2} + 1}{t^{2} + 1}, y = \frac{2 t}{t^{2} + 1}\}$

(13)

First we convert to polynomials and clear the fractions.

>	$B ≔ map (eq \mapsto numer (lhs (eq) - rhs (eq)), param)$

$B ≔ \{t^{2} y - 2 t + y, t^{2} x + t^{2} + x - 1\}$

(14)

>	$G ≔ Basis (B, lexdeg ([t], [x, y]))$

$G ≔ [x^{2} + y^{2} - 1, y t + x - 1, x t + t - y]$

(15)

>	$remove (has, G, t)$

$[x^{2} + y^{2} - 1]$

(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

>	$φ ≔ x^{3} + 2 x y z - z^{2}$

$φ ≔ x^{3} + 2 x y z - z^{2}$

(17)

on the sphere

>	$const ≔ x^{2} + y^{2} + z^{2} - 1$

$const ≔ x^{2} + y^{2} + z^{2} - 1$

(18)

Using the method of Lagrange multipliers, we compute

>	$G ≔ \{const, seq (diff (φ, v) - diff (const, v) t, v = [x, y, z])\}$

$G ≔ \{- 2 y t + 2 z x, - 2 z t + 2 x y - 2 z, - 2 x t + 3 x^{2} + 2 y z, x^{2} + y^{2} + z^{2} - 1\}$

(19)

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

>	$GB ≔ Basis (G, lexdeg ([t], [x, y, z]))$

$GB ≔ [x^{2} + y^{2} + z^{2} - 1, 17 y z^{2} - 13 z^{3} - x y + 17 z x + 13 z, 17 y^{2} z + 7 z^{3} - 6 x y - 7 z, 17 y^{3} + 11 z^{3} - 7 x y - 17 z x - 17 y - 11 z, x y^{2} - z^{2} x - y z, 48 z^{4} - 63 x y z - 34 z^{2} x - 34 y z - 48 z^{2}, 408 x z^{3} + 233 z^{3} + 65 x y - 408 z x - 233 z, - 6 x y z + 6 z^{2} x + 3 y z + 2 z^{2} + 2 t - 3 x]$

(20)

>	$remove (has, GB, t)$

$[x^{2} + y^{2} + z^{2} - 1, 17 y z^{2} - 13 z^{3} - x y + 17 z x + 13 z, 17 y^{2} z + 7 z^{3} - 6 x y - 7 z, 17 y^{3} + 11 z^{3} - 7 x y - 17 z x - 17 y - 11 z, x y^{2} - z^{2} x - y z, 48 z^{4} - 63 x y z - 34 z^{2} x - 34 y z - 48 z^{2}, 408 x z^{3} + 233 z^{3} + 65 x y - 408 z x - 233 z]$

(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$ .

>	$GB2 ≔ Basis (, lexdeg ([x, y], [z]))$

$GB2 ≔ [1152 z^{7} - 1763 z^{5} + 655 z^{3} - 44 z, - 1152 z^{6} + 118 z^{3} y + 1605 z^{4} - 118 y z - 453 z^{2}, - 1152 z^{5} + 3835 y z^{2} - 1404 z^{3} + 3835 z x + 2556 z, - 6912 z^{5} + 3835 y^{2} z + 10751 z^{3} - 3839 z, - 19584 z^{5} + 25987 z^{3} + 3835 x y - 6403 z, x^{2} + y^{2} + z^{2} - 1, - 9216 z^{5} + 3835 y^{3} + 3835 y z^{2} + 11778 z^{3} - 3835 y - 2562 z]$

(22)

>	$op (remove (has, GB2, \{x, y\}))$

$1152 z^{7} - 1763 z^{5} + 655 z^{3} - 44 z$

(23)

>	$sol_z ≔ solve (, z)$

$sol_z ≔ 0, 1, −1, \frac{2}{3}, - \frac{2}{3}, \frac{\sqrt{22}}{16}, - \frac{\sqrt{22}}{16}$

(24)

Substituting into the system yields the possible extremal points.

>	$[seq ((op @ map) (`union`, [solve (eval (GB2, z = 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 = - \frac{2}{3}, y = \frac{1}{3}, z = \frac{2}{3}\}, \{x = - \frac{2}{3}, y = - \frac{1}{3}, z = - \frac{2}{3}\}, \{x = - \frac{3}{8}, y = - \frac{3 \sqrt{22}}{16}, z = \frac{\sqrt{22}}{16}\}, \{x = - \frac{3}{8}, y = \frac{3 \sqrt{22}}{16}, z = - \frac{\sqrt{22}}{16}\}]$

(25)

Finally, we get the minimum and maximum values.

>	$\min (map2 (eval, φ,)), \max (map2 (eval, φ,))$

$- \frac{28}{27}, 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.

>	$G ≔ [3 y^{2} - 8 z^{3}, x^{2} - 2 z x + 5, 3 y^{3} + 8 x y^{2}] &colon;$

>	$HilbertDimension (G, tdeg (y, x, z))$

$0$

(27)

>	$HilbertSeries (G, tdeg (y, x, z), s)$

$s^{5} + 3 s^{4} + 5 s^{3} + 5 s^{2} + 3 s + 1$

(28)

>	$eval (, s = 1)$

$18$

(29)

>	$HilbertPolynomial (G, tdeg (y, x, z), s)$

$0$

(30)

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

>	$G ≔ [x^{3} y^{2} + 3 x^{2} y^{2} + y^{3} + 1] &colon;$

>	$HilbertDimension (G, tdeg (x, y))$

$1$

(31)

>	$HilbertSeries (G, tdeg (x, y), s)$

$- \frac{s^{4} + s^{3} + s^{2} + s + 1}{- 1 + s}$

(32)

>	$series (, s, 10)$

$1 + 2 s + 3 s^{2} + 4 s^{3} + 5 s^{4} + 5 s^{5} + 5 s^{6} + 5 s^{7} + 5 s^{8} + 5 s^{9} + O (s^{10})$

(33)

>	$HilbertPolynomial (G, tdeg (y, 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 $ℚ [ⅈ, \sqrt{2}] [x, y]$ .

>	$G ≔ [x^{2} + y^{2} - I, sqrt (2) y + sqrt (2) (x - sqrt (2)) - 1]$

$G ≔ [x^{2} + y^{2} - I, \sqrt{2} y + \sqrt{2} (x - \sqrt{2}) - 1]$

(35)

>	$GB ≔ Basis (G, tdeg (x, y))$

$GB ≔ [2 x + 2 y - 3 \sqrt{2}, - 6 \sqrt{2} y + 4 y^{2} + 9 - 2 I]$

(36)

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

>	$G ≔ [x^{2} - 2 x z + 5, x y^{2} + y z^{3}, 3 y^{2} - 8 z^{3}] &colon;$

$G mod 5$

$[x^{2} + 3 z x, z^{3} y + x y^{2}, 2 z^{3} + 3 y^{2}]$

(37)

>	$Basis (G, plex (x, y, z), characteristic = 5)$

$[z^{8} + z^{7}, 3 z^{6} + y z^{4}, 4 z^{3} + y^{2}, x z^{3} + z^{3} y, x^{2} + 3 z x]$

(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.

>	$L ≔ 1 + x + y + z + x^{2} + y^{2} + z^{2}$

$L ≔ x^{2} + y^{2} + z^{2} + x + y + z + 1$

(39)

>	$LeadingMonomial (L, plex (x, y, z))$

$x^{2}$

(40)

>	$LeadingMonomial (L, plex_min (x, y, z))$

$1$

(41)

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

>	$G ≔ [y w^{2} - z^{3}, x w^{3} - z^{4}]$

$G ≔ [y w^{2} - z^{3}, x w^{3} - z^{4}]$

(42)

Compare the usual Groebner basis

>	$Basis (G, plex (w, x, y, z))$

$[x^{2} z^{6} - y^{3} z^{5}, w y^{2} z^{4} - x z^{6}, w x z^{3} - y z^{4}, y w^{2} - z^{3}, x w^{3} - z^{4}]$

(43)

which allows for divisions by decreasing powers:

>	$Reduce (w^{5} x^{3} y^{2} z,, plex (w, x, y, z))$

$y^{4} z^{7}$

(44)

and the standard basis

>	$Basis (G, plex_min (w, x, y, z))$

$[- w^{4} x^{2} z + w^{4} y^{3}, - w^{4} y^{2} + w^{3} x z^{2}, - x w^{3} + w^{2} y z, - y w^{2} + z^{3}]$

(45)

which allows for divisions by increasing powers:

>	$Reduce (w^{5} x^{3} y^{2} z,, plex_min (w, x, y, z))$

$w^{6} x^{4} y$

(46)

Maple

Maple Add-Ons

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim

Maple

Powerful math software that is easy to use

Maple Add-Ons

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim