Gröbner basis

In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring <math>K[x_1,\ldots,x_n]</math> over a field <math>K</math>. A Gröbner basis allows many important properties of the ideal and the associated algebraic variety to be deduced easily, such as the dimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solving systems of polynomial equations and computing the images of algebraic varieties under projections or rational maps.

Gröbner basis computation can be seen as a multivariate, non-linear generalization of both Euclid's algorithm for computing polynomial greatest common divisors, and

Gaussian elimination for linear systems.

Gröbner bases were introduced by Bruno Buchberger in his 1965 Ph.D. thesis, which also included an algorithm to compute them (Buchberger's algorithm). He named them after his advisor Wolfgang Gröbner. In 2007, Buchberger received the Association for Computing Machinery's Paris Kanellakis Theory and Practice Award for this work.

However, the Russian mathematician Nikolai Günther had introduced a similar notion in 1913, published in various Russian mathematical journals. These papers were largely ignored by the mathematical community until their rediscovery in 1987 by Bodo Renschuch et al. An analogous concept for multivariate power series was developed independently by Heisuke Hironaka in 1964, who named them standard bases. This term has been used by some authors to also denote Gröbner bases.

The theory of Gröbner bases has been extended by many authors in various directions. It has been generalized to other structures such as polynomials over principal ideal rings or polynomial rings, and also some classes of non-commutative rings and algebras, like Ore algebras.

Tools

Polynomial ring

Gröbner bases are primarily defined for ideals in a polynomial ring <math>R=K[x_1,\ldots,x_n]</math> over a field . Although the theory works for any field, most Gröbner basis computations are done either when is the field of rationals or the integers modulo a prime number.

In the context of Gröbner bases, a nonzero polynomial in <math>R=K[x_1,\ldots,x_n]</math> is commonly represented as a sum <math> c_1M_1 +\cdots + c_mM_m,</math> where the <math>c_i</math> are nonzero elements of , called coefficients, and the <math>M_i</math> are monomials (called power products by Buchberger and some of his followers) of the form <math>x_1^{a_1}\cdots x_n^{a_n}, </math> where the <math>a_i</math> are nonnegative integers. The vector <math>A=[a_1, \ldots ,a_n]</math> is called the exponent vector of the monomial. When the list <math>X=[x_1, \ldots, x_n]</math> of the variables is fixed, the notation of monomials is often abbreviated as <math>x_1^{a_1}\cdots x_n^{a_n}=X^A.</math>

Monomials are uniquely defined by their exponent vectors, and, when a monomial ordering (see below) is fixed, a polynomial is uniquely represented by the ordered list of the ordered pairs formed by an exponent vector and the corresponding coefficient. This representation of polynomials is especially efficient for Gröbner basis computation in computers, although it is less convenient for other computations such as polynomial factorization and polynomial greatest common divisor.

If <math> F=\{f_1,\ldots, f_k\}</math> is a finite set of polynomials in the polynomial ring , the ideal generated by is the set of linear combinations of elements of with coefficients in ; that is the set of polynomials that can be written <math DISPLAY=inline>\sum_{i=1}^k g_i f_i</math> with <math>g_1,\ldots, g_k\in R.</math>

Monomial ordering

All operations related to Gröbner bases require the choice of a total order on the monomials, with the following properties of compatibility with multiplication. For all monomials , , ,

<math>M \leq N \Longleftrightarrow MP \leq NP </math>
<math>M \leq MP </math>.

A total order satisfying these condition is sometimes called an admissible ordering.

These conditions imply that the order is a well-order, that is, every strictly decreasing sequence of monomials is finite.

Although Gröbner basis theory does not depend on a particular choice of an admissible monomial ordering, three monomial orderings are especially important for the applications:

Lexicographical ordering, commonly called lex or plex (for pure lexical ordering).
Total degree reverse lexicographical ordering, commonly called degrevlex.
Elimination ordering, lexdeg.

Gröbner basis theory was initially introduced for the lexicographical ordering. It was soon realised that the Gröbner basis for degrevlex is almost always much easier to compute, and that it is almost always easier to compute a lex Gröbner basis by first computing the degrevlex basis and then using a "change of ordering algorithm". When elimination is needed, degrevlex is not convenient; both lex and lexdeg may be used but, again, many computations are relatively easy with lexdeg and almost impossible with lex.

Basic operations

Leading term, coefficient and monomial

Once a monomial ordering is fixed, the terms of a polynomial (a term is the product of a monomial with its nonzero coefficient) are naturally ordered by decreasing monomials (for this order). This makes the representation of a polynomial as a sorted list of pairs coefficient–exponent vector a canonical representation of the polynomials (that is, two polynomials are equal if and only if they have the same representation).

The first (greatest) term of a polynomial for this ordering and the corresponding monomial and coefficient are respectively called the leading term, leading monomial and leading coefficient and denoted, in this article, and .

Most polynomial operations related to Gröbner bases involve the leading terms. So, the representation of polynomials as sorted lists make these operations particularly efficient (reading the first element of a list takes a constant time, independently of the length of the list).

Polynomial operations

The other polynomial operations involved in Gröbner basis computations are also compatible with the monomial ordering; that is, they can be performed without reordering the result:

The addition of two polynomials consists in a merge of the two corresponding lists of terms, with a special treatment in the case of a conflict (that is, when the same monomial appears in the two polynomials).
The multiplication of a polynomial by a scalar consists of multiplying each coefficient by this scalar, without any other change in the representation.
The multiplication of a polynomial by a monomial consists of multiplying each monomial of the polynomial by . This does not change the term ordering by definition of a monomial ordering.

Divisibility of monomials

Let <math>M=x_1^{a_1}\cdots x_n^{a_n}</math> and <math>N=x_1^{b_1}\cdots x_n^{b_n}</math> be two monomials, with exponent vectors <math>A=[a_1,\ldots, a_n]</math> and <math>B=[b_1,\ldots, b_n].</math>

One says that divides , or that is a multiple of , if <math>a_i\le b_i</math> for every ; that is, if is componentwise not greater than . In this case, the quotient <math display =inline>\frac NM</math> is defined as <math display =inline>\frac NM=x_1^{b_1-a_1}\cdots x_n^{b_n-a_n}.</math> In other words, the exponent vector of <math display =inline>\frac NM</math> is the componentwise subtraction of the exponent vectors of and .

The greatest common divisor of and is the monomial <math display=inline>x_1^{\min(a_1,b_1)}\cdots x_n^{\min(a_n,b_n)}</math> whose exponent vector is the componentwise minimum of and . The least common multiple is defined similarly with instead of .

One has

:<math>\operatorname{lcm}(M,N)=\frac {MN}{\gcd(M,N)}.</math>

Reduction

The reduction of a polynomial by other polynomials with respect to a monomial ordering is central to Gröbner basis theory. It is a generalization of both row reduction occurring in Gaussian elimination and division steps of the

Euclidean division of univariate polynomials. are true for any monomial ordering (see that article for the definitions of the different orders that are mentioned below).

It is a common misconception that the lexicographical order is needed for some of these results. On the contrary, the lexicographical order is, almost always, the most difficult to compute, and using it makes impractical many computations that are relatively easy with graded reverse lexicographic order (grevlex), or, when elimination is needed, the elimination order (lexdeg) which restricts to grevlex on each block of variables.

Equality of ideals

Reduced Gröbner bases are unique for any given ideal and any monomial ordering. Thus two ideals are equal if and only if they have the same (reduced) Gröbner basis (usually a Gröbner basis software always produces reduced Gröbner bases).

Membership and inclusion of ideals

The reduction of a polynomial f by the Gröbner basis G of an ideal yields 0 if and only if f is in . This allows to test the membership of an element in an ideal. Another method consists in verifying that the Gröbner basis of G∪{f} is equal to G.

To test if the ideal generated by f1, ..., fk is contained in the ideal , it suffices to test that every is in . One may also test the equality of the reduced Gröbner bases of and ∪ {f1, ...,fk}.

Solutions of a system of algebraic equations

Any set of polynomials may be viewed as a system of polynomial equations by equating the polynomials to zero. The set of the solutions of such a system depends only on the generated ideal, and, therefore does not change when the given generating set is replaced by the Gröbner basis, for any ordering, of the generated ideal. Such a solution, with coordinates in an algebraically closed field containing the coefficients of the polynomials, is called a zero of the ideal. In the usual case of rational coefficients, this algebraically closed field is chosen as the complex field.

An ideal does not have any zero (the system of equations is inconsistent) if and only if 1 belongs to the ideal (this is Hilbert's Nullstellensatz), or, equivalently, if its Gröbner basis (for any monomial ordering) contains 1, or, also, if the corresponding reduced Gröbner basis is [1].

Given the Gröbner basis G of an ideal I, it has only a finite number of zeros, if and only if, for each variable x, G contains a polynomial with a leading monomial that is a power of x (without any other variable appearing in the leading term). If this is the case, then the number of zeros, counted with multiplicity, is equal to the number of monomials that are not multiples of any leading monomial of G. This number is called the degree of the ideal.

When the number of zeros is finite, the Gröbner basis for a lexicographical monomial ordering provides, theoretically, a solution: the first coordinate of a solution is a root of the greatest common divisor of polynomials of the basis that depend only on the first variable. After substituting this root in the basis, the second coordinate of this solution is a root of the greatest common divisor of the resulting polynomials that depend only on the second variable, and so on. This solving process is only theoretical, because it implies GCD computation and root-finding of polynomials with approximate coefficients, which are not practicable because of numeric instability. Therefore, other methods have been developed to solve polynomial systems through Gröbner bases (see System of polynomial equations for more details).

Dimension, degree and Hilbert series

The dimension of an ideal I in a polynomial ring R is the Krull dimension of the ring R/I and is equal to the dimension of the algebraic set of the zeros of I. It is also equal to number of hyperplanes in general position which are needed to have an intersection with the algebraic set, which is a finite number of points. The degree of the ideal and of its associated algebraic set is the number of points of this finite intersection, counted with multiplicity. In particular, the degree of a hypersurface is equal to the degree of its definition polynomial.

The dimension depend only on the set of the leading monomials of the Gröbner basis of the ideal for any monomial ordering. The same is true for the degree and degree-compatible monomial orderings; a monomial ordering is degree compatible if smaller for the degree implies smaller for the monomial ordering.

The dimension is the maximal size of a subset S of the variables such that there is no leading monomial depending only on the variables in S. Thus, if the ideal has dimension 0, then for each variable x there is a leading monomial in the Gröbner basis that is a power of .

Both dimension and degree may be deduced from the Hilbert series of the ideal, which is the series <math display="inline">\sum_{i=0}^\infty d_i t^i</math>, where <math>d_i</math> is the number of monomials of degree i that are not multiple of any leading monomial in the Gröbner basis. The Hilbert series may be summed into a rational fraction

:<math>\sum_{i=0}^\infty d_it^i=\frac{P(t)}{(1-t)^d},</math>

where d is the dimension of the ideal and <math>P(t)</math> is a polynomial. The number <math>P(1)</math> is the degree of the algebraic set defined by the ideal, in the case of a homogeneous ideal or a monomial ordering compatible with the degree; that is, to compare two monomials, one compares their total degrees first.

The dimension does not depend on the choice of a monomial ordering, although the Hilbert series and the polynomial <math>P(t)</math> may change with changes of the monomial ordering. However, for homogeneous ideals or monomial orderings compatible with the degree, the Hilbert series and the polynomial <math>P(t)</math> do not depend on the choice of monomial ordering.

Most computer algebra systems that provide functions to compute Gröbner bases provide also functions for computing the Hilbert series, and thus also the dimension and the degree.

Elimination

The computation of Gröbner bases for an elimination monomial ordering allows computational elimination theory. This is based on the following theorem.

Consider a polynomial ring <math>K[x_1,\ldots,x_n,y_1,\ldots,y_m]=K[X,Y],</math> in which the variables are split into two subsets X and Y. Let us also choose an elimination monomial ordering "eliminating" X, that is a monomial ordering for which two monomials are compared by comparing first the X-parts, and, in case of equality only, considering the Y-parts. This implies that a monomial containing an X-variable is greater than every monomial independent of X.

If G is a Gröbner basis of an ideal I for this monomial ordering, then <math>G\cap K[Y]</math> is a Gröbner basis of <math>I\cap K[Y]</math> (this ideal is often called the elimination ideal). Moreover, <math>G\cap K[Y]</math> consists exactly of the polynomials of whose leading terms belong to (this makes the computation of <math>G\cap K[Y]</math> very easy, as only the leading monomials need to be checked).

This elimination property has many applications, some described in the next sections.

Another application, in algebraic geometry, is that elimination realizes the geometric operation of projection of an affine algebraic set into a subspace of the ambient space: with above notation, the (Zariski closure of) the projection of the algebraic set defined by the ideal I into the Y-subspace is defined by the ideal <math>I\cap K[Y].</math>

The lexicographical ordering such that <math>x_1>\cdots >x_n</math> is an elimination ordering for every partition <math>\{x_1, \ldots, x_k\},\{x_{k+1},\ldots,x_n\}.</math> Thus a Gröbner basis for this ordering carries much more information than usually necessary. This may explain why Gröbner bases for the lexicographical ordering are usually the most difficult to compute.

Intersecting ideals

If and are two ideals generated respectively by {f1, ..., fm} and {g1, ..., gk}, then a single Gröbner basis computation produces a Gröbner basis of their intersection . For this, one introduces a new indeterminate t, and one uses an elimination ordering such that the first block contains only t and the other block contains all the other variables (this means that a monomial containing t is greater than every monomial that does not contain t). With this monomial ordering, a Gröbner basis of consists in the polynomials that do not contain t, in the Gröbner basis of the ideal

:<math>K=\langle tf_1,\ldots, tf_m, (1-t)g_1, \ldots, (1-t)g_k\rangle.</math>

In other words, is obtained by eliminating t in K.

This may be proven by observing that the ideal K consists of the polynomials <math>(a-b)t+b</math> such that <math>a\in I</math> and <math>b\in J</math>. Such a polynomial is independent of t if and only if , which means that <math>b\in I\cap J.</math>

Implicitization of a rational curve

A rational curve is an algebraic curve that has a set of parametric equations of the form

:<math>\begin{align}

x_1 &= \frac{f_1(t)}{g_1(t)}\\

&\;\;\vdots\\

x_n &= \frac{f_n(t)}{g_n(t)},

\end{align}

</math>

where <math>f_i(t)</math> and <math>g_i(t)</math> are univariate polynomials for 1 ≤ i ≤ n. One may (and will) suppose that <math>f_i(t)</math> and <math>g_i(t)</math> are coprime (they have no non-constant common factors).

Implicitization consists in computing the implicit equations of such a curve. In case of n = 2, that is for plane curves, this may be computed with the resultant. The implicit equation is the following resultant:

:<math>\text{Res}_t(g_1x_1-f_1,g_2x_2-f_2).</math>

Elimination with Gröbner bases allows to implicitize for any value of n, simply by eliminating t in the ideal

<math>\langle g_1x_1-f_1,\ldots, g_nx_n-f_n\rangle.</math>

If n = 2, the result is the same as with the resultant, if the map <math>t \mapsto (x_1,x_2)</math> is injective for almost every t. In the other case, the resultant is a power of the result of the elimination.

Saturation

When modeling a problem by polynomial equations, it is often assumed that some quantities are non-zero, so as to avoid degenerate cases. For example, when dealing with triangles, many properties become false if the triangle degenerates to a line segment, i.e. the length of one side is equal to the sum of the lengths of the other sides. In such situations, one cannot deduce relevant information from the polynomial system unless the degenerate solutions are ignored. More precisely, the system of equations defines an algebraic set which may have several irreducible components, and one must remove the components on which the degeneracy conditions are everywhere zero.

This is done by saturating the equations by the degeneracy conditions, which may be done via the elimination property of Gröbner bases.

Definition of the saturation

The localization of a ring consists in adjoining to it the formal inverses of some elements. This section concerns only the case of a single element, or equivalently a finite number of elements (adjoining the inverses of several elements is equivalent to adjoining the inverse of their product). The localization of a ring R by an element f is the ring <math>R_f=R[t]/(1-ft),</math> where t is a new indeterminate representing the inverse of f. The localization of an ideal of R is the ideal <math>I_f=R_fI</math> of <math>R_f.</math> When R is a polynomial ring, computing in <math>R_f</math> is not efficient because of the need to manage the denominators. Therefore, localization is usually replaced by the operation of saturation.

The with respect to f of an ideal in R is the inverse image of <math>R_f I</math> under the canonical map from R to <math>R_f.</math> It is the ideal <math>I:f^\infty= \{g\in R \mid (\exists k\in \mathbb N) f^k g\in I\}</math> consisting in all elements of R whose product with some power of f belongs to .

If is the ideal generated by and 1−ft in R[t], then <math>I:f^\infty = J\cap R.</math> It follows that, if R is a polynomial ring, a Gröbner basis computation eliminating t produces a Gröbner basis of the saturation of an ideal by a polynomial.

The important property of the saturation, which ensures that it removes from the algebraic set defined by the ideal the irreducible components on which the polynomial f is zero, is the following: The primary decomposition of <math>I:f^\infty</math> consists of the components of the primary decomposition of I that do not contain any power of f.

Computation of the saturation

A Gröbner basis of the saturation by f of a polynomial ideal generated by a finite set of polynomials F, may be obtained by eliminating t in <math>F\cup\{1-tf\},</math> that is by keeping the polynomials independent of t in the Gröbner basis of <math>F\cup\{1-tf\}</math> for an elimination ordering eliminating t.

Instead of using F, one may also start from a Gröbner basis of F. Which method is most efficient depends on the problem. However, if the saturation does not remove any component, that is if the ideal is equal to its saturated ideal, computing first the Gröbner basis of F is usually faster. On the other hand, if the saturation removes some components, the direct computation may be dramatically faster.

If one wants to saturate with respect to several polynomials <math>f_1,\ldots, f_k</math> or with respect to a single polynomial which is a product <math>f = f_1 \cdots f_k, </math> there are three ways to proceed which give the same result but may have very different computation times (it depends on the problem which is the most efficient).

Saturating by <math>f = f_1 \cdots f_k </math> in a single Gröbner basis computation.
Saturating by <math>f_1,</math> then saturating the result by <math>f_2,</math> and so on.
Adding to F or to its Gröbner basis the polynomials <math>1-t_1f_1, \ldots, 1-t_kf_k,</math> and eliminating the <math>t_i</math> in a single Gröbner basis computation.

Effective Nullstellensatz

Hilbert's Nullstellensatz has two versions. The first one asserts that a set of polynomials has no common zeros over an algebraic closure of the field of the coefficients, if and only if 1 belongs to the generated ideal. This is easily tested with a Gröbner basis computation, because 1 belongs to an ideal if and only if 1 belongs to the Gröbner basis of the ideal, for any monomial ordering.

The second version asserts that the set of common zeros (in an algebraic closure of the field of the coefficients) of an ideal is contained in the hypersurface of the zeros of a polynomial f, if and only if a power of f belongs to the ideal. This may be tested by saturating the ideal by f; in fact, a power of f belongs to the ideal if and only if the saturation by f provides a Gröbner basis containing 1.

Implicitization in higher dimension

By definition, an affine rational variety of dimension k may be described by parametric equations of the form

:<math>\begin{align}

x_1&=\frac{p_1}{p_0}\\

&\;\;\vdots\\

x_n&=\frac{p_n}{p_0},

\end{align}

</math>

where <math>p_0,\ldots,p_n</math> are n+1 polynomials in the k variables (parameters of the parameterization) <math>t_1,\ldots,t_k.</math> Thus the parameters <math>t_1,\ldots,t_k</math> and the coordinates <math>x_1,\ldots,x_n</math> of the points of the variety are zeros of the ideal

:<math>I=\left\langle p_0x_1-p_1, \ldots, p_0x_n-p_n\right\rangle.</math>

One could guess that it suffices to eliminate the parameters to obtain the implicit equations of the variety, as it has been done in the case of curves. Unfortunately this is not always the case. If the <math>p_i</math> have a common zero (sometimes called base point), every irreducible component of the non-empty algebraic set defined by the <math>p_i</math> is an irreducible component of the algebraic set defined by I. It follows that, in this case, the direct elimination of the <math>t_i</math> provides an empty set of polynomials.

Therefore, if k>1, two Gröbner basis computations are needed to implicitize:

Saturate <math>I</math> by <math>p_0</math> to get a Gröbner basis <math>G</math>
Eliminate the <math>t_i</math> from <math>G</math> to get a Gröbner basis of the ideal (of the implicit equations) of the variety.

Algorithms and implementations

Buchberger's algorithm is the oldest algorithm for computing Gröbner bases. It was devised by Bruno Buchberger together with the Gröbner basis theory. It is straightforward to implement, but it appeared soon that raw implementations can solve only trivial problems. The main issues are the following ones:

Even when the resulting Gröbner basis is small, the intermediate polynomials can be huge. It results that most of the computing time may be spent in memory management. So, specialized memory management algorithms may be a fundamental part of an efficient implementation.
The integers occurring during a computation may be sufficiently large for making fast multiplication algorithms and multimodular arithmetic useful. For this reason, most optimized implementations use the GMP library. Also, modular arithmetic, Chinese remainder theorem and Hensel lifting are used in optimized implementations
The choice of the S-polynomials to reduce and of the polynomials used for reducing them is devoted to heuristics. As in many computational problems, heuristics cannot detect most hidden simplifications, and if heuristic choices are avoided, one may get a dramatic improvement of the algorithm efficiency.
In most cases most S-polynomials that are computed are reduced to zero; that is, most computing time is spent to compute zero.
The monomial ordering that is most often needed for the applications (pure lexicographic) is not the ordering that leads to the easiest computation, generally the ordering degrevlex.

For solving 3. many improvements, variants and heuristics have been proposed before the introduction of F4 and F5 algorithms by Jean-Charles Faugère. As these algorithms are designed for integer coefficients or with coefficients in the integers modulo a prime number, Buchberger's algorithm remains useful for more general coefficients.

Roughly speaking, F4 algorithm solves 3. by replacing many S-polynomial reductions by the row reduction of a single large matrix for which advanced methods of linear algebra can be used. This solves partially issue 4., as reductions to zero in Buchberger's algorithm correspond to relations between rows of the matrix to be reduced, and the zero rows of the reduced matrix correspond to a basis of the vector space of these relations.

F5 algorithm improves F4 by introducing a criterion that allows reducing the size of the matrices to be reduced. This criterion is almost optimal, since the matrices to be reduced have full rank in sufficiently regular cases (in particular, when the input polynomials form a regular sequence). Tuning F5 for a general use is difficult, since its performances depend on an order on the input polynomials and a balance between the incrementation of the working polynomial degree and of the number of the input polynomials that are considered. To date (2022), there is no distributed implementation that is significantly more efficient than F4, but, over modular integers F5 has been used successfully for several cryptographic challenges; for example, for breaking HFE challenge.

Issue 5. has been solved by the discovery of basis conversion algorithms that start from the Gröbner basis for one monomial ordering for computing a Gröbner basis for another monomial ordering. FGLM algorithm is such a basis conversion algorithm that works only in the zero-dimensional case (where the polynomials have a finite number of complex common zeros) and has a polynomial complexity in the number of common zeros. A basis conversion algorithm that works is the general case is the Gröbner walk algorithm. In its original form, FGLM may be the critical step for solving systems of polynomial equations because FGML does not take into account the sparsity of involved matrices. This has been fixed by the introduction of sparse FGLM algorithms.

Most general-purpose computer algebra systems have implementations of one or several algorithms for Gröbner bases, often also embedded in other functions, such as for solving systems of polynomial equations or for simplifying trigonometric functions; this is the case, for example, of CoCoA, GAP, Macaulay 2, Magma, Maple, Mathematica, SINGULAR, SageMath and SymPy. When F4 is available, it is generally much more efficient than Buchberger's algorithm. The implementation techniques and algorithmic variants are not always documented, although they may have a dramatic effect on efficiency.

Implementations of F4 and (sparse)-FGLM are included in the library Msolve. Beside Gröbner algorithms, Msolve contains fast algorithms for real-root isolation, and combines all these functions in an algorithm for the real solutions of systems of polynomial equations that outperforms dramatically the other software for this problem (Maple and Magma).

Generalizations

The concept and algorithms of Gröbner bases have been generalized to submodules of free modules over a polynomial ring. In fact, if is a free module over a ring , then one may consider the direct sum <math>R\oplus L</math> as a ring by defining the product of two elements of to be . This ring may be identified with <math>R[e_1, \ldots, e_l]/\left\langle \{e_ie_j|1\le i\le j\le l\}\right\rangle</math>, where <math>e_1, \ldots, e_l</math> is a basis of L. This allows identifying a submodule of generated by <math>g_1, \ldots, g_k</math> with the ideal of <math>R[e_1, \ldots, e_l]</math> generated by <math>g_1, \ldots, g_k</math> and the products <math>e_ie_j</math>, <math>1\le i\le j\le l</math>. If is a polynomial ring, this reduces the theory and the algorithms of Gröbner bases of modules to the theory and the algorithms of Gröbner bases of ideals.

The concept and algorithms of Gröbner bases have also been generalized to ideals over various rings, commutative or not, like polynomial rings over a principal ideal ring or Weyl algebras.

Areas of applications

Error-Correcting Codes

Gröbner bases have been applied in the theory of error-correcting codes for algebraic decoding. By using Gröbner basis computation on various forms of error-correcting equations, decoding methods were developed for correcting errors of cyclic codes, affine variety codes, algebraic-geometric codes and even general linear block codes. Applying Gröbner basis in algebraic decoding is still a research area of channel coding theory.

References

External links

Faugère's own implementation of his F4 algorithm
Comparative Timings Page for Gröbner Bases Software
Prof. Bruno Buchberger Bruno Buchberger
Gröbner basis introduction on Scholarpedia