Thus we can skip the pair
{fi,fj}
if it satisfies the function
Criterion 2({fi,fj},
G, M) <==>
there exists fk
in G such that
{fi<>fk
and fj<>fk,
LM(fk)
divides LCM(LM(fi),
LM(fj)),
{fi,fk}
and {fj,fk}
are not in M}
where M is the set of all the pairs
{fi,fj},
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
{fi,fj}
such that
LCM(LM(fi),
LM(fj))
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 = {f1,f2,...,fs}
that generates an ideal I
Output: The reduced
Groebner basis G = {g1,g2,...,gt}
that generates I
G := F
(optionally) Reduce G
M :=
{{fi,fj}:
1 <= i < j <= s}
WHILE (M<>Ø) DO
{fi,fj} := a pair in M such
that LCM(LM(fi), LM(fj)) is of minimal
degree
M := M - {{fi,fj}}
IF (Criterion1({fi,fj}) AND
NOT(Criterion2({fi,fj}, G, M)))
THEN
S :=
S-Polynomial
(fi,fj)
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 = {f1
= x2 + 2xy2,
f2 = xy +
2y3 - 1}
with lex order and x>y
in R[x,y].
Then we set G = F and
M = {{f1,
f2}}.
S(f1,
f2) = x and
NormalForm(x, G) = x.
So we must add f3
= x to our
generating set G and update M; we get
G = {f1,
f2, f3}
and M = {{f1,
f3},{f2,
f3}}.
LCM(LM(f1), LM(f3)) = x2
and LCM(LM(f2), LM(f3)) = xy,
so we pick the pair {f2,
f3},
and compute S(f2,
f3) = 2y3
- 1, which is
already completely
reduced modulo G. We add f4
= 2y3 - 1 to G. We set
G = {f1, f2,
f3,
f4} and
M = {{f1,
f3},{f1,
f4},{f2,
f4},{f3,
f4}}.
We have:
LCM(LM(f1), LM(f3)) = x2,
LCM(LM(f1), LM(f4)) = x2y3,
LCM(LM(f2), LM(f4)) = xy3,
LCM(LM(f3), LM(f4)) =
xy3.
So we can choose between {f2,
f4} and {f3,
f4}. We skip {f3,
f4} thanks to Criterion1, pick {f2,
f4} and compute
S(f2,
f4) = -1/2x - 2y5 + y2
= -1/2 f3
- y2 f4, so
NormalForm(S(f2,
f4), G) = 0.
Now we must pick {f1,
f3} and compute
S(f1,
f3) = 2xy2
= 2y2 f3
so NormalForm(S(f1,
f3), G) = 0.
Finally, Criterion1 again lets us skip the last pair {f1,
f4}.
We can cancel f1 and
f2 from G
since their leading terms are both multiples of the leading term of
f3 and normalize
f3 and
f4. Hence
G = {f3,
f4} = {x, y3
- 1/2}.
-
Consider I =
<F> where F = {f1
= x - t,
f2 = y -
t2, f3
= z - t3}
with lex order and t>z>y>x
in R[t,x,y,z].
Then we set G = F and
M = ({f1,
f2},{f1,
f3},{f2,
f3}) (the pairs in M have been listed
in increasing order w.r.t. the LCM of their LM's).
We pick {f1,
f2} since it is the pair with the
minimum LCM and compute NormalForm(S(f1,
f2), G) = y - x2.
We add f4
= y - x2 to our
generating set G and update M; we get
G = {f1,
f2,
f3, f4}
and M = ({f1,
f4},{f2,
f4},{f2,
f3},{f1,
f3},{f3,
f4}).
We can safely skip the first two pairs thanks to Criterion1, so we must deal
with
{f2,
f3}.
S(f2,
f3) = -ty + z and
NormalForm(-ty + z, G) = z - x3.
We have a new polynomial f5
= z - x3 to consider: G = {f1,
f2,
f3, f4,
f5}
and M = ({f4,
f5},{f1,
f5},{f2,
f5},{f1,
f3},{f3,
f4},{f3,
f5}).
Criterion1 lets us skip {f4,
f5}, {f1,
f5} and {f2,
f5}. We can apply Criterion2 to
{f1,
f3} and then again Criterion1 to
{f3,
f4} and
{f3,
f5}. There is no pair left in M, hence G is a Groebner basis.
Canceling f2 and
f3
(since their leading terms are both multiples of the leading term of
f1),
we get
G = {y - x2,
z - x3, t - x}.
|