Content deleted Content added
clean up algorithm construction |
No edit summary |
||
Line 3:
A crude version of this algorithm to find a basis for an ideal ''I'' of a ring ''R'' proceeds as follows:
:'''Input''' A set of polynomials ''F'' = {''f''<sub>1</sub>, ''f''<sub>2</sub>, ..., ''f''<sub>''k''</sub>} that generate ''I''
:'''Output''' A [[Gröbner basis]] for ''I''▼
:# Let ''g<sub>i</sub>'' be the leading term of ''f<sub>i</sub>'' with respect to the given ordering, and denote the [[least common multiple]] of ''g<sub>i</sub>'' and ''g<sub>j</sub>'' by ''a<sub>ij</sub>''.▼
▲'''Output''' A [[Gröbner basis]] for ''I''
:# 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)''.▼
:# Using the [[multivariate division algorithm]], reduce all the ''S<sub>ij</sub>'' relative to the set ''F''.▼
▲# Let ''g<sub>i</sub>'' be the leading term of ''f<sub>i</sub>'' with respect to the given ordering, and denote the [[least common multiple]] of ''g<sub>i</sub>'' and ''g<sub>j</sub>'' by ''a<sub>ij</sub>''.
:# Add all the nonzero polynomials resulting from step 3 to ''F'', and repeat steps 1-4 until nothing new is added.▼
▲# 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)''.
▲# Using the [[multivariate division algorithm]], reduce all the ''S<sub>ij</sub>'' relative to the set ''F''.
▲# Add all the nonzero polynomials resulting from step 3 to ''F'', and repeat steps 1-4 until nothing new is added.
The polynomial ''S''<sub>''ij''</sub> is commonly referred to as the ''S''-polynomial, where ''S'' refers to ''subtraction'' (Buchberger) or ''[[syzygy]]'' (others).
| |||