Content deleted Content added
m Fixing link |
polynomial ring |
||
Line 1:
In computational [[algebraic geometry]] and computational [[commutative algebra]], '''Buchberger's algorithm''' is a method of transforming a given set of generators for a polynomial [[ring ideal|ideal]] into a [[Gröbner basis]] with respect to some [[monomial order]]. It was invented by Austrian mathematician [[Bruno Buchberger]]. One can view it as a generalization of the [[Euclidean algorithm]] for univariate [[Greatest common divisor|GCD]] computation and of [[Gaussian elimination]] for linear systems.
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 generate ''I''
Line 11:
:# 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 (mathematics)|Syzygy]]'' (others). The pair of polynomials
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. It also should be noted that if the leading terms of ''f<sub>i</sub>'' and ''f<sub>j</sub>'' share no variables in common, then ''S<sub>ij</sub>'' will ''always'' reduce to 0 (if we use only f<sub>i</sub> and f<sub>j</sub> for reduction), so we needn't calculate it at all.
| |||