Content deleted Content added
→top: Split a sentence in two for clarity. Tags: Mobile edit Mobile app edit Android app edit App section source |
m →Implementations: Disambiguation of Coq link |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Algorithm for computing Gröbner bases}}
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.
Line 15:
:# Choose two polynomials in ''G'' and let {{math|1=''S''<sub>''ij''</sub> = {{sfrac|''a''<sub>''ij''</sub> | ''g''<sub>{{var|i}}</sub>}} ''f''<sub>{{var|i}}</sub> − {{sfrac|''a''<sub>''ij''</sub> | ''g''<sub>''j''</sub>}} ''f''<sub>''j''</sub>}} ''(Note that the leading terms here will cancel by construction)''.
:# Reduce ''S''<sub>''ij''</sub>, 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
:# Output ''G''
Line 35:
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 ==
| |||