Citizendia
Your Ad Here

In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R. 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 techniques of Abstract algebra, especially Commutative algebra, with Commutative algebra is the branch of Abstract algebra that studies Commutative rings their ideals, and modules over such rings In Ring theory, a branch of Abstract algebra, an ideal is a special Subset of a ring. In Mathematics, especially in the field of Abstract algebra, a polynomial ring is a ring formed from the set of Polynomials in one or more variables One can view it as a multivariate, non-linear generalization of:

The theory of Gröbner bases for polynomial rings was developed by Bruno Buchberger in 1965, who named them after his advisor Wolfgang Gröbner. Bruno Buchberger (born October 22, 1942 in Innsbruck) is Professor of Computer Mathematics at Johannes Kepler University in Linz, The Association for Computing Machinery awarded him its 2007 Paris Kanellakis Theory and Practice Award for this work. An analogous concept for local rings was developed independently by Heisuke Hironaka in 1964, who named them standard bases. In Mathematics, more particularly in Abstract algebra, local rings are certain rings that are comparatively simple and serve to describe what is called Heisuke Hironaka (広中 平祐 Hironaka Heisuke; born April 9, 1931) is a Japanese Mathematician.

Contents

Formal definition

A Gröbner basis G is characterised by any one of the following properties, stated relative to some monomial order:

All these properties are equivalent; different authors use different definitions depending on the topic they choose. It is the last two properties which allow calculations in the factor ring R/I with the same facility as modular arithmetic. In Mathematics a quotient ring, also known as factor ring or residue class ring, is a construction in Ring theory, quite similar to the It is a significant fact of commutative algebra that Gröbner bases always exist, and can be effectively obtained for any ideal starting with a generating subset. Commutative algebra is the branch of Abstract algebra that studies Commutative rings their ideals, and modules over such rings

Multivariate division requires a monomial ordering, 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 reverse lexicographic order (also called graded reverse lexicographic order or simply total degree order). In Mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al product Lexicographic order eliminates variables, however the resulting Gröbner bases are often very large and expensive to compute. Degree reverse lexicographic order typically provides for the fastest Gröbner basis computations. In this order monomials are compared first by total degree, with ties broken by taking the smallest monomial with respect to lexicographic ordering with the variables reversed.

In most cases (polynomials in finitely many variables with complex coefficients or, more generally, coefficients over any field, for example), Gröbner bases exist for any monomial ordering. One method for computing them is known as Buchberger's algorithm. In computational Algebraic geometry and computational Commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial Another method for computing Gröbner bases, based on the same mathematics as the Buchberger algorithm, is the Faugère F4 algorithm. In Computer algebra, the Faugère F4 algorithm, by Jean-Charles Faugère, computes the Gröbner basis of an ideal of a multivariate Polynomial There are also two algorithms for converting a Gröbner basis with respect to one monomial order to a Gröbner basis with respect to a different monomial order; the FGLM algorithm and the Gröbner walk algorithm. These algorithms are often employed to compute (difficult) lexicographic Gröbner bases from (easier) total degree Gröbner bases.

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 terms of the other elements of the basis. In the worst case, computation of a Gröbner basis may require time that is exponential or even doubly-exponential in the number of solutions of the polynomial system (for degree reverse lexicographic order and lexicographic order, respectively). Despite these complexity bounds, both standard and reduced Gröbner bases are often computable in practice, and most computer algebra systems contain routines to do so. A computer algebra system ( CAS) is a software program that facilitates Symbolic mathematics.

The concept and algorithms of Gröbner bases have been generalized to modules over a polynomial ring and to non-commutative (skew) polynomial rings such as Weyl algebras. In Abstract algebra, the concept of a module over a ring is a generalization of the notion of Vector space, where instead of requiring the scalars In Abstract algebra, the Weyl algebra is the ring of Differential operators with Polynomial coefficients (in one variable

Properties and applications of Gröbner bases

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. In Mathematics, Polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm but an approximate (By contrast, this is generally not true for a non-Gröbner basis with 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.

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 (over an algebraic closure of the field in which the coefficients lie) to the system of equations

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

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 {f1 − a1, . . . , fm − am} 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. In Mathematics, parametric equations are a method of defining a curve Given the equations

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

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

{x1 − f1, . . . , xn − fn}

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. This article is about algebraic varieties For the term "a variety of algebras" and an explanation of the difference between a variety of algebras and an algebraic variety

Intersecting ideals

{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. In Arithmetic and Number theory, the least common multiple or lowest common multiple ( lcm) or smallest common multiple of two In Mathematics, the greatest common divisor (gcd, sometimes known as the greatest common factor (gcf or highest common factor (hcf, of two non-zero 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 not a Euclidean domain, so the Euclidean algorithm doesn't work here. In Abstract algebra, a Euclidean domain (also called a Euclidean ring) is a type of ring in which the Euclidean algorithm applies

See also

Further reading

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic