Graphics Reference
In-Depth Information
Inputs:
f(X), g(X) Œ k[X] , g(X) π 0.
Outputs:
a(X), r(X) Πk[X] satisfying f(X) = a(X) g(X) + r(X) with either
r(X) = 0 or deg r < deg g
a := 0; r := f;
while (r π 0) and (lt(g) divides lt(r)) do
{ lt(p) returns the leading term of p }
begin
a := a + lt(r)/lt(g);
r := r - (lt(r)/lt(g)) g;
end ;
Algorithm 10.10.1.
The one-variable polynomial division algorithm.
ically, it is known (Theorem B.8.7) that, given polynomials f(X) and g(X), there are
unique polynomials a(X) and r(X) with deg r < deg g, so that
() =
()() +
( .
fX
aXgX
rX
(10.56)
More to the point, there is a simple algorithm for finding a(X) and r(X). Algorithm
10.10.1 is one variant of this one-variable division algorithm. We show it here to help
motivate the generalization to the multivariable case that we shall describe shortly.
As simple as it is, this division algorithm has many applications. For example, it is
used in the Euclidean algorithm that computes the greatest common divisor of a finite
set of polynomials. (This algorithm proceeds just like the one for computing the great-
est common divisor of a finite set of integers. Structurally, the polynomial ring k[X]
looks very much like the integers Z , and many of the constructions that one can use
for Z carry over to k[X].) Algorithm 10.10.1 also leads to simple algorithms that
answer questions (1) and (2), because it is the key ingredient to proving that k[X] is
a PID (Theorem B.8.11), that is, every ideal I Õ k[X] has the form I = <g(X)> for some
g Œ k[X]. This obviously shows that every ideal I has a finite basis. A polynomial f Œ
k[X] belongs to I if and only if the remainder r(X) in equation (10.56) is zero.
When we try to answer questions (1) and (2) in the multivariable case, the first
problem we encounter is that the ring k[X 1 ,X 2 ,...,X n ] is not a PID if n > 1. There-
fore, we shall want to reduce a polynomial by long division with respect to a set of k
> 1 polynomials (corresponding to the basis of an ideal), not just one. In k[X], this
task reduces to the case k = 1 because of the PID property. On the other hand, with
polynomials of more than one variable it is in general possible to perform long divi-
sion reductions in different ways which lead to different remainders. Without unique
remainders we would lose some good algorithms. Fortunately, we can get uniqueness
if we choose the basis carefully (and define a good division algorithm). This is where
Gröbner bases come in. The fact that some bases are better than others is hardly new.
For example, in the case of vector spaces, orthonormal bases are often particularly
desirable.
Search WWH ::




Custom Search