Graphics Reference
In-Depth Information
Input:
A nonempty finite set P of polynomials.
Output:
A Gröbner basis G for the ideal <P>.
polynomialSet
G;
polynomialPairSet
B;
polynomial
p, q, g;
G := P; B := { {p,q} | p, q Œ G and p π q } ;
while
B πf
do
begin
{p,q} := AnyElementOf (B);
B := B - {{p,q}};
g := NF(S(p,q),G);
g
if
π 0
then
begin
B := B » { {g,g¢ } | g¢Œ G };
G := G » { g };
end
end
;
Algorithm 10.10.3.
The Buchberger Gröbner basis algorithm.
Solution.
We show the steps in the algorithm.
At start of first time through loop:
G = {p
1
,p
2
} and B = {{p
1
,p
2
}}
In first loop:
{p,q} = {p
1
,p
2
}, B is set to empty,
S(p,q) = XY - X, and g = NF(S(p,q)) = XY - X.
We add to B and G
At start of second time through loop:
G = {p
1
,p
2
,XY - X} and
B = {{XY - X,p
1
}, {XY - X,p
2
}}
In second loop:
(p,q) = {XY - X,p
1
}, B is set to {{XY - X,p
2
}}
S(p,q) =-XY - X, and g = NF(S(p,q)) =-2X.
We add to B and G
At start of third time through loop: G = {p
1
,p
2
,XY - X,-2X} and
B = {{-2X,p
1
},{-2X,p
1
},{-2X,XY - X},{XY - X,p
2
}}
In third loop:
{p,q} = {-2X,p
1
}, B is set to {{-2X,p
1
},{-2X,XY - X},{XY - X,p
2
}},
S(p,q) = X, and g = NF(S(p,q)) = 0.
We now go through the loop three more times, removing one element of B
each time, and each time the reduced element g is again 0.
