Buchberger's algorithm: Difference between revisions

Revision as of 14:35, 1 June 2025

Latest revision as of 10:05, 29 August 2025

(2 intermediate revisions by the same user not shown)

Line 13:

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

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

:# Choose two polynomials in ''G'' and let {{math|1=''S''_''ij'' = {{sfrac|''a''_''ij'' | ''g''_{{var|i}}}} ''f''_{{var|i}} − {{sfrac|''a''_''ij'' | ''g''_''j''}} ''f''_''j''}} ''(Note that theThe 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.

Line 20:

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]].

There are numerousmany ways to improve this algorithm beyond what has been stated above. For example, one could reduce all the new elements of ''F'' can be reduced 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 useusing only {{mvar|f_i}} and {{mvar|f_j}} for reduction), so weit needn't calculatebe itcalculated 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.

Line 37:

== Implementations ==

At least one implementation of Buchberger’s algorithm has been [[Formal proof|proved]] correct within the [[proof assistant]] [[Coq (proofrenamed assistant)|Coq[[Rocq]]).<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>

In the [[SymPy|SymPy library]] 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–McCluskey algorithm]] &ndash;– analogous algorithm for Boolean algebra

== References ==

{{reflistReflist}}

== Further reading ==

* {{cite journal

| last last1= Buchberger

| first first1= B.

| authorlink author1-link= Bruno Buchberger

|date=August 1976

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

| journal = ACM SIGSAM Bulletin

| volume = 10

| issue = 3

| pages = 19–29

| publisher = ACM

|date=August 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 Donald 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 Simulation, 45:519ff

Line 72 ⟶ 70:

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

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

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

[[Category:Computer algebra]]