---
title: Buchberger's algorithm
slug: buchberger-s-algorithm
qid: 
snapshot: enwiki-001359915802
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1359915802
tags: [23118434, 23603337, 26870222, 26870223, 28607422, 44391295]
---

# Buchberger's algorithm

> [!note] Provenance
> Snapshot `enwiki-001359915802` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1359915802> · Licensed CC BY-SA 4.0

In the theory of multivariate polynomials, 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. For other Gröbner basis algorithms, see .

In the theory of multivariate polynomials, 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. For other Gröbner basis algorithms, see . 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 (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 (others). The pair of polynomials with which it is associated is commonly referred to as critical pair. There are many ways to improve this algorithm beyond what has been stated above. For example, 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 using only and for reduction), so it needn't be calculated 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.
