|
A crude version of this algorithm to find a basis for an ideal ''I'' of a polynomial ring ''R'' proceeds as follows:
:'''Input''' A set of polynomials ''F'' = {''f''<sub>1</sub>, ''f''<sub>2</sub>, ..., ''f''<sub>''k''</sub>} that generategenerates ''I''
:'''Output''' A [[Gröbner basis]] for ''I''
:# ''G'' := ''F''
:# LetFor every ''f<sub>i</sub>'', ''f<sub>j</sub>'' in ''G'', denote by ''g<sub>i</sub>'' be the leading term of ''f<sub>i</sub>'' with respect to the given ordering, and denoteby ''a<sub>ij</sub>'' the [[least common multiple]] of ''g<sub>i</sub>'' and ''g<sub>j</sub>'' by ''a<sub>ij</sub>''.
:# LetChoose two polynomials in ''G'' and let ''S''<sub>''ij''</sub> = (''a''<sub>''ij''</sub> / ''g''<sub>''i''</sub>) ''f''<sub>''i''</sub> − (''a''<sub>''ij''</sub> / ''g''<sub>''j''</sub>) ''f''<sub>''j''</sub> <br>''(Note that the leading terms here will cancel by construction)''.
:# UsingReduce ''S''<sub>''ij''</sub>, with the [[multivariate division algorithm]], reducerelative allto the set ''S<sub>ij</sub>G'' relativeuntil tothe result is not further reducible. If the setresult is non-zero, add it to ''FG''.
:# Repeat steps 1-4 until all possible pairs are considered, including those involving the new polynomials added in step 4.
:# Add all the nonzero polynomials resulting from step 3 to ''F'', and repeat steps 1-4 until nothing new is added.
:# Output ''G''
The polynomial ''S''<sub>''ij''</sub> 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]].
| 