Buchberger's algorithm: Difference between revisions

Revision as of 08:04, 4 July 2022

Revision as of 01:07, 20 July 2022

Line 7:

== Algorithm ==

A crude version of this algorithm to find a basis for an ideal ''{{mvar|I''}} of a polynomial ring ''R'' proceeds as follows:

:'''Input''' A set of polynomials ''F'' that generates ''{{mvar|I''}}

:'''Output''' A [[Gröbner basis]] ''G'' for ''{{mvar|I''}}

:# ''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 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''_{''i''{{var|I}}})}} ''f''_{''i''{{var|I}}} − ({{sfrac|''a''_''ij'' /| ''g''_''j'')}} ''f''_''j''}} ''(Note that 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.

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

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.