Buchberger's algorithm: Difference between revisions

Revision as of 19:25, 30 June 2012

Latest revision as of 14:35, 1 June 2025

(47 intermediate revisions by 33 users not shown)

Line 1:

{{Short description|Algorithm for computing Gröbner bases}}

In computational [[algebraic geometry]] and computational [[commutative algebra]], '''Buchberger's algorithm''' is a method of transforming a given set of generators for a polynomial [[ring ideal|ideal]] into a [[Gröbner basis]] with respect to some [[monomial order]]. It was invented by Austrian mathematician [[Bruno Buchberger]]. One can view it as a generalization of the [[Euclidean algorithm]] for univariate [[Greatest common divisor|GCD]] computation and of [[Gaussian elimination]] for linear systems.

In the theory of [[multivariate polynomial]]s, '''Buchberger's algorithm''' is a method for transforming a given set of polynomials into a [[Gröbner basis]], which is another set of polynomials that have the same common zeros and are more convenient for extracting information on these common zeros. It was introduced by [[Bruno Buchberger]] simultaneously with the definition of Gröbner bases.

The [[Euclidean algorithm]] for computing the polynomial [[greatest common divisor]] is a special case of Buchberger's algorithm restricted to polynomials of a single variable. [[Gaussian elimination]] of a [[system of linear equations]] is another special case where the degree of all polynomials equals one.

A crude version of this algorithm to find a basis for an ideal ''I'' of a polynomial ring ''R'' proceeds as follows:

For other Gröbner basis algorithms, see {{slink|Gröbner basis#Algorithms and implementations}}.

:'''Input''' A set of polynomials ''F'' = {''f''₁, ''f''₂, ..., ''f''_''k''} that generate ''I''

:'''Output''' A [[Gröbner basis]] for ''I''

== Algorithm ==

:# Let ''g_i'' be the leading term of ''f_i'' with respect to the given ordering, and denote the [[least common multiple]] of ''g_i'' and ''g_j'' by ''a_ij''.

A crude version of this algorithm to find a basis for an ideal ''{{mvar|I''}} of a polynomial ring ''R'' proceeds as follows:

:# Let ''S''_''ij'' = (''a''_''ij'' / ''g''_''i'') ''f''_''i'' &minus; (''a''_''ij'' / ''g''_''j'') ''f''_''j'' <br>''(Note that the leading terms here will cancel by construction)''.

:# Using the [[multivariate division algorithm]], reduce all the ''S_ij'' relative to the set ''F''.

:# Add all the nonzero polynomials resulting from step 3 to ''F'', and repeat steps 1-4 until nothing new is added.

:'''Input''' A set of polynomials ''F'' that generates {{mvar|I}}

The polynomial ''S''_''ij'' is commonly referred to as the ''S''-polynomial, where ''S'' refers to ''subtraction'' (Buchberger) or ''[[Syzygy (mathematics)|Syzygy]]'' (others). The pair of polynomials with which it is associated is commonly referred to as [[critical pair (logic)|critical pair]].

:'''Output''' A [[Gröbner basis]] for ''IG'' for {{mvar|I}}

:# ''G'' := ''F''

:# LetFor every ''gf_i'', be''f_j'' in ''G'', denote by ''g_i'' the leading term of ''f_i'' with respect to the given [[monomial ordering]], and denoteby ''a_ij'' the [[least common multiple]] of ''g_i'' and ''g_j'' by ''a_ij''.

:# LetChoose two polynomials in ''G'' and let {{math|1=''S''_''ij'' = ({{sfrac|''a''_''ij'' /| ''g''_{''{{var|i''}}})}} ''f''_{''{{var|i''}}} &minus;− ({{sfrac|''a''_''ij'' /| ''g''_''j'')}} ''f''_''j''}} <br>''(Note that the leading terms here will cancel by construction)''.

:# Reduce ''S''_''ij'', with the [[multivariate division algorithm]] relative to the set ''G'' until the result is not further reducible. If the result is non-zero, add it to ''G''.

:# Repeat steps 2–4 until all possible pairs are considered, including those involving the new polynomials added in step 4.

:# Output ''G''

The polynomial ''S''_''ij'' is commonly referred to as the ''S''-polynomial, where ''S'' refers to ''subtraction'' (Buchberger) or ''[[Syzygy (mathematics)|Syzygysyzygy]]'' (others). The pair of polynomials with which it is associated is commonly referred to as [[critical pair (logic)|critical pair]].

There are numerous ways to improve this algorithm beyond what has been stated above. For example, one could reduce all the new elements of ''F'' relative to each other before adding them. If the leading terms of ''f_i'' and ''f_j'' share no variables in common, then ''S_ij'' will ''always'' reduce to 0 (if we use only f_i and f_j for reduction), so we needn't calculate it at all.

There are numerous ways to improve this algorithm beyond what has been stated above. For example, one could reduce all the new elements of ''F'' relative to each other before adding them. If the leading terms of ''f_i'' and ''f_j'' share no variables in common, then ''S_ij'' will ''always'' reduce to 0 (if we use only {{mvar|f_i}} and {{mvar|f_j}} for reduction), so we needn't calculate it at all.

The algorithm terminates because it is consistently increasing the size of the monomial ideal generated by the leading terms of our set ''F'', and [[Dickson's lemma]] (or the [[Hilbert basis theorem]]) guarantees that any such ascending chain must eventually become constant. Unfortunately, it may take a very long time to terminate, corresponding to the fact that [[Gröbner bases]] can be ''extremely'' large. Thus, it has large storage requirements ([[space complexity]]). Also, the [[time complexity]] of the algorithm is doubly exponential in the input data, which implies that its worst-case behavior can be very slow.

The algorithm terminates because it is consistently increasing the size of the monomial ideal generated by the leading terms of our set ''F'', and [[Dickson's lemma]] (or the [[Hilbert basis theorem]]) guarantees that any such ascending chain must eventually become constant. Unfortunately, it may take a very long time to terminate, corresponding to the fact that [[Gröbner bases]] can be ''extremely'' large. Thus, it has large storage requirements ([[space complexity]]). Also, the [[time complexity]] of the algorithm is doubly exponential in the input data, which implies that its worst-case behavior can be very slow.

Further methods for computing Gröbner bases include the [[Faugère F4 algorithm]], based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas from [[Differential algebra]].

==See alsoComplexity ==

The [[time complexity|computational complexity]] of Buchberger's algorithm is very difficult to estimate, because of the number of choices that may dramatically change the computation time. Nevertheless, T. W. Dubé has proved<ref>{{cite journal|doi=10.1137/0219053|title=The Structure of Polynomial Ideals and Gröbner Bases|journal=SIAM Journal on Computing|volume=19|issue=4|pages=750–773|year=1990|last1=Dubé|first1=Thomas W.}}</ref> that the degrees of the elements of a reduced Gröbner basis are always bounded by

* [[Quine-McCluskey algorithm]] (analogous algorithm for Boolean algebra)

:<math>2\left(\frac{d^2}{2} +d\right)^{2^{n-2}}</math>,

* [http://www.scholarpedia.org/article/Buchberger%27s_algorithm Buchberger's algorithm] discussed more extensively on Scholarpedia

where {{math|''n''}} is the number of variables, and {{math|''d''}} the maximal [[total degree]] of the input polynomials. This allows, in theory, to use [[linear algebra]] over the [[vector space]] of the polynomials of degree bounded by this value, for getting an algorithm of complexity

<math>d^{2^{n+o(1)}}</math>.

On the other hand, there are examples<ref>{{cite journal|doi=10.1016/0001-8708(82)90048-2|doi-access=free|title=The complexity of the word problems for commutative semigroups and polynomial ideals|journal=[[Advances in Mathematics]]|volume=46|issue=3|pages=305–329|year=1982|last1=Mayr|first1=Ernst W|last2=Meyer|first2=Albert R|hdl=1721.1/149010|hdl-access=free}}</ref> where the Gröbner basis contains elements of degree

==References==

:<math>d^{2^{\Omega(n)}}</math>,

and the above upper bound of complexity is optimal. Nevertheless, such examples are extremely rare.

Since its discovery, many variants of Buchberger's have been introduced to improve its efficiency. [[Faugère's F4 and F5 algorithms]] are presently the most efficient algorithms for computing Gröbner bases, and allow to compute routinely Gröbner bases consisting of several hundreds of polynomials, having each several hundreds of terms and coefficients of several hundreds of digits.

== Implementations ==

In the [[SymPy|SymPy library]] for [[Python (programming language)|Python]], the (improved) Buchberger algorithm is implemented as <code>sympy.polys.polytools.groebner()</code>.<ref>{{cite web |title=Polynomials Manipulation Module Reference - SymPy 1.14.0 documentation |url=https://docs.sympy.org/latest/modules/polys/reference.html#sympy.polys.polytools.groebner |website=docs.sympy.org}}</ref>

There is an implementation of Buchberger’s algorithm that has been proved correct

within the proof assistant [[Coq (proof assistant)|Coq]].<ref>{{cite journal |last1=Théry |first1=Laurent |title=A Machine-Checked Implementation of Buchberger's Algorithm |journal=Journal of Automated Reasoning |date=2001 |volume=26 |issue=2 |pages=107–137 |doi=10.1023/A:1026518331905}}</ref>

== See also ==

* [[Knuth–Bendix completion algorithm]]

* [[Quine-McCluskeyQuine–McCluskey algorithm]] (&ndash; analogous algorithm for Boolean algebra)

== References ==

{{reflist}}

== Further reading ==

* {{cite journal

| last = Buchberger

Line 29 ⟶ 56:

| authorlink = Bruno Buchberger

| title = Theoretical Basis for the Reduction of Polynomials to Canonical Forms

| journal = ACM SIGSAM Bull.Bulletin

| volume = 10

| issue = 3

| pages = 19–29

| publisher = ACM

| month date=August August1976

| year = 1976

| doi = 10.1145/1088216.1088219

| mr = 0463136

| s2cid = 15179417

}} <!-- Note: This citation data is from ACM; the citation at MathWorld has several errors. -->

* David Cox, John Little, and DonalDonald O'Shea (1997). ''Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra'', Springer. {{ISBN |0-387-94680-2}}.

* Vladimir P. Gerdt, Yuri A. Blinkov (1998). ''Involutive Bases of Polynomial Ideals'', Mathematics and Computers in SimluationSimulation, 45:519ff

== External links ==

* {{springer|title=Buchberger algorithm|id=p/b110980}}

* [http://www.scholarpedia.org/article/Buchberger%27s_algorithm Buchberger's algorithm] discussed more extensively on Scholarpedia

* {{MathWorld | urlname=BuchbergersAlgorithm | title=Buchberger's Algorithm}}

Line 49 ⟶ 78:

[[Category:Algebraic geometry]]

[[Category:Commutative algebra]]

[[de:Buchberger-Algorithmus]]

[[fr:Algorithme de Buchberger]]