Buchberger's algorithm: Difference between revisions

Revision as of 14:16, 25 November 2022

Revision as of 18:37, 13 December 2022

Line 2:

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.

[[Euclidean algorithm]] for polynomial [[Greatestgreatest common divisor]] computation and [[Gaussian elimination]] of [[system of linear equations|linear system]]s are special cases of Buchberger's algorithm when the number of variables or the degrees of the polynomials are respectively equal to one.

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

Line 18:

:# 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 {{mvar|f_i}} and {{mvar|f_j}} for reduction), so we needn't calculate it at all.