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 K over a field K. 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, andGaussian elimination for linear systems. Gröbner bases were introduced in 1965, together with an algorithm to compute them (Buchberger's algorithm), by Bruno Buchberger in his Ph.D. thesis. 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. Gröbner bases are primarily defined for ideals in a polynomial ring R = K [ x 1 , … , x n ] {displaystyle R=K} over a field K. Although the theory works for any field, most Gröbner basis computations are done either when K is the field of rationals or the integers modulo a prime number. A polynomial is a sum c 1 M 1 + ⋯ + c m M m {displaystyle c_{1}M_{1}+cdots +c_{m}M_{m}} where the c i {displaystyle c_{i}} are nonzero elements of K and the M i {displaystyle M_{i}} are monomials or 'power products' of the variables. This means that a monomial M is a product M = x 1 a 1 ⋯ x n a n , {displaystyle M=x_{1}^{a_{1}}cdots x_{n}^{a_{n}},} where the a i {displaystyle a_{i}} are nonnegative integers. The vector A = [ a 1 , … , a n ] {displaystyle A=} is called the exponent vector of M. The notation is often abbreviated as x 1 a 1 ⋯ x n a n = X A {displaystyle x_{1}^{a_{1}}cdots x_{n}^{a_{n}}=X^{A}} . Monomials are uniquely defined by their exponent vectors so computers can represent monomials efficiently as exponent vectors, and polynomials as lists of exponent vectors and their coefficients. If F = { f 1 , … , f k } {displaystyle F={f_{1},ldots ,f_{k}}} is a finite set of polynomials in a polynomial ring R, the ideal generated by F is the set of linear combinations of elements from F with coefficients in all of R: 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 M, N, P,