Buchberger's algorithm: Difference between revisions

Revision as of 14:54, 16 April 2025

Revision as of 09:30, 31 May 2025

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]], 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]]<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 ==