Graphics Reference
In-Depth Information
Example 10.9.3 points out a major problem with using the Sylvester resultant for
finding implicit equations from parameterizations. One may get a much higher degree
polynomial equation than is necessary and, since factoring polynomials is a nontriv-
ial problem, there would be no easy way to eliminate the extraneous factors in general.
From a computational point of view one always has to worry about numerical sta-
bility, so that it is important to get polynomials with as small degree as possible. A
more efficient method for implicitizing parametric objects is needed.
Finally, in showing how resultants can be used to implicitize objects, we have
assumed above that computations are carried out with exact arithmetic. Unfortunately,
when one tries to do this on a computer it is easy to give examples, where, due to round-
off errors, small variations in polynomial coefficients can lead to wildly different and
incorrect implicit forms. Although exact rational arithmetic is possible it is very expen-
sive computationally. For a more efficient way to deal with the round-off problem here
see, for example, [Hobb91].
10.10
Gröbner Bases
This section will define and discuss applications of certain special bases of polyno-
mial ideals called Gröbner bases. These bases lead to algorithms that not only solve
a large variety of problems but provide efficient solutions to them. We shall use them
to give answers to the following questions:
(1) Does an ideal I Õ k[X
1
,X
2
,...,X
n
] have a finite basis and how does one find one?
(2) Given an ideal I Õ k[X
1
,X
2
,...,X
n
] and a polynomial f, when is f ΠI?
(3) Given polynomials f
1
, f
2
,..., f
k
Πk[X
1
,X
2
,...,X
n
], what are the solutions in
k
n
to the system of equations
(
)
=
fXX
,...,
X
n
0
112
,
M
M
(
)
=
fXX
,
,...,
X
0
?
(10.54)
m
12
n
(4) How does one find an implicit representation for a set defined parametrically by
(
)
xf t t
=
,...,
t
n
1112
,
M
M
(
)
xf
=
t
,
t
,...,
t
,
(10.55)
mm
12
n
where the f
i
are either polynomials or rational functions?
Our brief introduction to the subject will hopefully motivate the reader to go and
learn more about it. Some good references for Gröbner bases and their many appli-
cations are [CoLO97], [AdaL94], and [CoLO98].
Gröbner bases were developed to answer questions such as the four listed above
in the case of
multi
variable polynomials or ideals where things get more complicated
than in the one-variable case. The main reason that answers are either easy or at least
well-understood in the 1-variable case is that one has a nice division algorithm. Specif-
