Buchberger's refined algorithm

Here we will discuss some improvements on the basic Buchberger algorithm for computing Groebner bases.
The most expensive operation in the algorithm is the reduction of the S-polynomials modulo G. Moreover, the lack of uniqueness in the result of the computation of a normal form for an S-polynomial may lead to a nonzero polynomial whereas the S-polynomial does reduce to zero modulo G. Fortunately, Buchberger [2] developed two criteria for detecting 0-reductions a priori. He also developed other strategies that significantly speed up the calculations.

Buchberger's Criterion 1. If LCM(LM(p), LM(q)) = LM(p) LM(q) then

S(p,q) -->^*_{p,q} 0

This means that we can ignore those pairs whose leading monomials are relatively prime. Namely, the pair {f_i,f_j} can be safely skipped if it does not satisfy the function

Criterion 1({f_i,f_j}) <==>

LCM(LM(f_i), LM(f_j)) <> LM(f_i) LM(f_j).

Buchberger's Criterion 2. If, when considering the pair {f_i,f_j}, there exist an element f_k of the basis G other than f_i and f_j such that LCM(LM(f_i), LM(f_j)) is a multiple of LM(f_k) and S(f_i,f_k) and S(f_j,f_k) have already been considered, then

S(f_i,f_j) -->^*_G0.

Thus we can skip the pair {f_i,f_j} if it satisfies the function

Criterion 2({f_i,f_j}, G, M) <==>

there exists f_k in G such that
{f_i<>f_k and f_j<>f_k,
LM(f_k) divides LCM(LM(f_i), LM(f_j)),
{f_i,f_k} and {f_j,f_k} are not in M}

where M is the set of all the pairs {f_i,f_j}, 1<= i<j <=length(G).

Another strategy to speed up the calculation regards the procedure to select a pair. It can be shown that if we always select a pair {f_i,f_j} such that LCM(LM(f_i), LM(f_j)) is as small as possible w.r.t. the chosen monomial ordering (the so called "normal" selection strategy), then criterion1 and criterion2 are "good" in the sense that nonzero remainders will tend to come up sooner in the process, so there will be more of a chance that subsequent normal forms will be 0. Moreover, the likelyhood that criterion2 can even be applied is increased. Finally, if the degree ordering is used, this strategy seems to lead to simpler polynomials than other choices.

Optionally we can also apply a procedure for pre-reduction of the raw input set. (There is also another reformulation of the algorithm in which the partial basis is reduced after each new polynomial is added.)

The improved form of Buchberger's algorithm is the following.

Improved Construction of Reduced Groebner Basis.

Input: A polynomial set F = {f₁,f₂,...,f_s} that generates an ideal I
Output: The reduced Groebner basis G = {g₁,g₂,...,g_t} that generates I
G := F
(optionally) Reduce G
M := {{f_i,f_j}: 1 <= i < j <= s}
WHILE (M<>Ø) DO

{f_i,f_j} := a pair in M such that LCM(LM(f_i), LM(f_j)) is of minimal degree
M := M - {{f_i,f_j}}
IF (Criterion1({f_i,f_j}) AND NOT(Criterion2({f_i,f_j}, G, M))) THEN

S := S-Polynomial (f_i,f_j)
h := NormalForm (S, G)
IF (h <> 0) THEN

M := M U {{g, h} for all g in G}
G := G U {h}

Reduce G and adjust constants to make the generators monic.

Examples.

Reconsider I = <F> where F = {f₁= x² + 2xy², f₂= xy + 2y³ - 1} with lex order and x>y in R[x,y].
Then we set G = F and M = {{f₁, f₂}}.
S(f₁, f₂) = x and NormalForm(x, G) = x. So we must add f₃= x to our generating set G and update M; we get G = {f₁, f₂, f₃} and M = {{f₁, f₃},{f₂, f₃}}.
LCM(LM(f₁), LM(f₃)) = x² and LCM(LM(f₂), LM(f₃)) = xy, so we pick the pair {f₂, f₃}, and compute S(f₂, f₃) = 2y³- 1, which is already completely reduced modulo G. We add f₄ = 2y³ - 1 to G. We set G = {f₁, f₂, f₃, f₄} and M = {{f₁, f₃},{f₁, f₄},{f₂, f₄},{f₃, f₄}}.
We have:
LCM(LM(f₁), LM(f₃)) = x²,
LCM(LM(f₁), LM(f₄)) = x²y³,
LCM(LM(f₂), LM(f₄)) = xy³,
LCM(LM(f₃), LM(f₄)) = xy³.
So we can choose between {f₂, f₄} and {f₃, f₄}. We skip {f₃, f₄} thanks to Criterion1, pick {f₂, f₄} and compute S(f₂, f₄) = -¹/₂x - 2y⁵ + y²= -¹/₂ f₃- y² f₄, so NormalForm(S(f₂, f₄), G) = 0.
Now we must pick {f₁, f₃} and compute S(f₁, f₃) = 2xy²= 2y² f₃ so NormalForm(S(f₁, f₃), G) = 0.
Finally, Criterion1 again lets us skip the last pair {f₁, f₄}.
We can cancel f₁ and f₂ from G since their leading terms are both multiples of the leading term of f₃ and normalize f₃ and f₄. Hence
G = {f₃, f₄} = {x, y³ - ¹/₂}.

Consider I = <F> where F = {f₁ = x - t, f₂ = y - t², f₃ = z - t³} with lex order and t>z>y>x in R[t,x,y,z].
Then we set G = F and M = ({f₁, f₂},{f₁, f₃},{f₂, f₃}) (the pairs in M have been listed in increasing order w.r.t. the LCM of their LM's).
We pick {f₁, f₂} since it is the pair with the minimum LCM and compute NormalForm(S(f₁, f₂), G) = y - x². We add f₄ = y - x² to our generating set G and update M; we get G = {f₁, f₂, f₃, f₄} and M = ({f₁, f₄},{f₂, f₄},{f₂, f₃},{f₁, f₃},{f₃, f₄}).
We can safely skip the first two pairs thanks to Criterion1, so we must deal with {f₂, f₃}.
S(f₂, f₃) = -ty + z and NormalForm(-ty + z, G) = z - x³. We have a new polynomial f₅= z - x³ to consider: G = {f₁, f₂, f₃, f₄, f₅} and M = ({f₄, f₅},{f₁, f₅},{f₂, f₅},{f₁, f₃},{f₃, f₄},{f₃, f₅}).
Criterion1 lets us skip {f₄, f₅}, {f₁, f₅} and {f₂, f₅}. We can apply Criterion2 to {f₁, f₃} and then again Criterion1 to {f₃, f₄} and {f₃, f₅}. There is no pair left in M, hence G is a Groebner basis. Canceling f₂ and f₃ (since their leading terms are both multiples of the leading term of f₁), we get

G = {y - x², z - x³, t - x}.

Last updated

Last updated