 FACTOID # 2: Puerto Rico has roughly the same gross state product as Montana, Wyoming and North Dakota combined.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > GrĂ¶bner basis

In computer algebra and computational algebraic geometry, a Gröbner basis (named after Wolfgang Gröbner) is a particular kind of generating subset of an ideal I in a polynomial ring. It is characterised by the property that the ideal given by the leading terms of polynomials in I is itself generated by the leading terms of the basis. This criterion is stated relative to some monomial order. It is a significant fact of commutative algebra that such generating subsets exist, and can be effectively obtained starting with any generating subset. A computer algebra system (CAS) is a software program that facilitates symbolic mathematics. ... Algebraic geometry is a branch of mathematics which, as the name suggests, combines abstract algebra, especially commutative algebra, with geometry. ... In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ... In mathematics, a monomial order is a total order on the set of all monomials (considering monomials which only differ in their coefficient to be the same) satisfying two additional properties. ... In abstract algebra, commutative algebra is the field of study of commutative rings, their ideals, modules and algebras. ...

The basis depends on the monomial ordering chosen, and different orderings can give rise to radically different Gröbner bases. Two of the most commonly used orderings are lexicographic ordering, and degree lexicographic, a variant on lexicographic ordering where monomials are sorted first by degree, then by lexicographic ordering when two monomials are of the same degree. In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. ...

In most cases (polynomials in finitely many variables with complex coefficients (more generally coefficients over any field), for example), Gröbner bases exist for any monomial ordering. One method for generating them is known as Buchberger's algorithm.

A Gröbner basis is termed reduced if the leading coefficient of each element of the basis is 1 and no monomial in any element of the basis is in the ideal generated by the leading coefficients of the other elements of the basis. Both standard and reduced Gröbner bases are often computable in practice.

 Contents

Properties and applications of Gröbner bases GA_googleFillSlot("encyclopedia_square");

Deciding equality of ideals

Reduced Gröbner bases can be shown to be unique for any given ideal and monomial ordering, and are also often computable in practice. Thus one can determine if two ideals are equal by looking at their reduced Gröbner bases.

Deciding membership of ideals

The reduction of a polynomial f by the multivariate division algorithm for an ideal using a Gröbner basis will yield 0 if and only if f is in the ideal. (This is not true in general for polynomials in more than one variable). This gives a test for determining whether or not a polynomial is in an ideal with a given set of generators. Although polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm, an approximate multivariate division algorithm can be constructed. ...

Elimination property

If a Gröbner basis for an ideal I in

k[x1, x2, ..., xn]

is computed relative to the lexicographic ordering with

x1 > x2 > ... > xn,

the intersection of I with

k[xk, xk+1, ..., xn]

is given by the intersection of the Gröbner basis with

k[xk, xk'+1, ..., xn].

In particular a polynomial f lies in

k[xk, xk+1, ..., xn],

if and only if its leading term lies in this subring. This is known as the elimination property

Solving equations

In particular, this gives us a method for solving simultaneous polynomial equations. If there are only finitely many solutions to the system of equations

{f1[x1, ..., xn] = a1, ..., fm[x1, ..., xn] = an},

we should be able to manipulate these equations to get something of the form

g(xn) = b.

The elimination property says that if we compute a Gröbner basis for the ideal generated by {f1a1, ..., fmam} relative to the right lexicographic ordering, then we can find the polynomial g as one of the elements of our basis. Furthermore, (taking k = n − 1) there will be another polynomial in the basis involving only xn−1 and xn, so we can take our possible solutions for xn and find corresponding values for xn−1. This lifting continues all the way up until we've found the values of all the variables.

Conversion of parametric equations

The same elimination property can almost be used to convert parametric equations of polynomials into nonparametric equations. Given the equations In mathematics, a parametric equation explicitly relates two or more variables in terms of one or more independent parameters. ...

{x1 = f1(t1, ..., tm), ..., xn = fn(t1, ..., tm)},

we compute a Gröbner basis for the ideal generated by

{x1f1, ..., xnfn}

relative to any ordering which places polynomials involving t greater than those which don't: for example, lexicographic ordering with

t1 > t2 > ... > tm > x1 > ... > xn.

Taking only the elements of the basis which do not involve the t variables, we get a set of equations describing not the original surface, but the smallest affine variety containing it. In classical algebraic geometry (and to some extent also in modern algebraic geometry), the main objects of study are algebraic varieties. ...

Intersecting ideals

• If I is generated by
{f1, ..., fm}

and J is generated by some

{g1, ..., gk},

then the intersection of I and J can be found by taking a Gröbner basis for the ideal generated by

{tf1, ..., tfm, (1 − t)g1, ..., (1 − t)gk}

relative to any lexicographic ordering which places t first, then taking only those terms not involving t. In particular, this allows us to calculate the least common multiple (and hence the greatest common divisor) of two polynomials f and g, since it is the generator of the intersection of the ideals generated by f and by g. This is true even if we do not know how to factor the polynomials! Also note, that for more than one variable the polynomial ring is no euclidian domain, so the Euclidian algorithm doesn't work here. In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (GCF) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...

• Comparative Timings Page for Gröbner Bases Software (http://magma.maths.usyd.edu.au/users/allan/gb)

Share your thoughts, questions and commentary here
Press Releases | Feeds | Contact