Algebraic Geometry - Computer Graphics and Geometric Modeling - page 736

Inputs: f, p 1 , p 2 , º , p m Œ k[X 1 ,X 2 , º ,X n ] , p i π 0

Outputs: a 1 , a 2 , º , a m , r Œ k[X 1 ,X 2 , º ,X n ] satisfying

f = a 1 p 1 +º+ a m p m + r,

where either r is zero or none of the monomials appearing in r is divisible
by any of the lt(p i )

integer i;
boolean noDivision;

a 1 := a 2 := º := a m := r := 0; g := f;
while g π 0 do
begin
i := 1; noDivision := true;
while (i £ m) and noDivision do

if lt(p i ) divides lt(g)

then
begin
a i := a i + lt(g)/lt(p i );
g := g - (lt(g)/lt(p i ))*p i ;
noDivision := false ;
end
else i := i + 1;

if noDivision then
begin
r := r + lt(g);
g := g - lt(g);
end

end ;

Algorithm 10.10.2. The multivariable polynomial division algorithm.

()

u = h lt p

for some monomial h. Let g = f - hp. We shall say that the polynomial g is obtained
from f via an elementary P-reduction and write f fi g. If no such polynomial p exists,
then we shall say that f is P-irreducible . If there exists a sequence of elementary P-
reductions f = f 0 fi f 1 fi f 2 fi ...fi f m = g, then we say that f P-reduces to g and
write . If f P-reduces to g and g is P-irreducible, we shall call g a P-normal
form for f and denote such g by NF(f,P).

ææ

f g