In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, and more specifically in
computer algebra
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions ...
, computational
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
, and computational
commutative algebra
Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prom ...
, a Gröbner basis is a particular kind of
generating set of an ideal in a
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...
over a
field . A Gröbner basis allows many important properties of the ideal and the associated
algebraic variety
Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. ...
to be deduced easily, such as the
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
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
Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. ...
under
projections or
rational map
In mathematics, in particular the subfield of algebraic geometry, a rational map or rational mapping is a kind of partial function between algebraic varieties. This article uses the convention that varieties are irreducible.
Definition
Formal d ...
s.
Gröbner basis computation can be seen as a multivariate, non-linear generalization of both
Euclid's algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an ef ...
for computing
polynomial greatest common divisor
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common ...
s, and
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
for linear systems.
Gröbner bases were introduced in 1965, together with an algorithm to compute them (
Buchberger's algorithm), by
Bruno Buchberger
Bruno Buchberger (born 22 October 1942) is Professor of Computer Mathematics at Johannes Kepler University in Linz, Austria. In his 1965 Ph.D. thesis, he created the theory of Gröbner bases, and has developed this theory throughout his career. ...
in his Ph.D. thesis. He named them after his advisor
Wolfgang Gröbner
Wolfgang Gröbner (11 February 1899 – 20 August 1980) was an Austrian mathematician. His name is best known for the Gröbner basis, used for computations in algebraic geometry. However, the theory of Gröbner bases for polynomial rings was deve ...
. In 2007, Buchberger received the
Association for Computing Machinery
The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...
'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
In mathematics, a power series (in one variable) is an infinite series of the form
\sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots
where ''an'' represents the coefficient of the ''n''th term and ''c'' is a con ...
was developed independently by
Heisuke Hironaka
is a Japanese mathematician who was awarded the Fields Medal in 1970 for his contributions to algebraic geometry.
Career
Hironaka entered Kyoto University in 1949. After completing his undergraduate studies at Kyoto University, he received his ...
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 ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...
s, and also some classes of non-commutative rings and algebras, like
Ore algebras.
Tools
Polynomial ring
Gröbner bases are primarily defined for
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considered ...
s in a
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...