\documentstyle [11pt]{article}
\title{Implicitization by Gr\"obner basis conversion}
\author{Michael Kalkbrener\\Department of Mathematics\\
Swiss Federal Institute of 
Technology\\
CH-8092 Zurich, Switzerland}

\textheight     620pt
\textwidth      420pt
\topmargin       18pt
\oddsidemargin   30pt
\evensidemargin  30pt

\date{} 
\newtheorem{theorem}{Theorem}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}

\begin{document}
\maketitle


\section{Introduction}

The problem of converting parametrically defined varieties into 
their implicit form is of great importance in geometric modeling 
(see [Sederberg et al. 1984]
or [Buchberger 1987]). From an algebraic point of view this problem has the 
following form:
for a given vector of rational functions 
$(p_1/q_1,\ldots,p_n/q_n)\in K(y_1,\ldots,y_m)^n$, $K$
a field, compute a finite basis of the prime ideal 
\[ P:=\{f\in K[x_1,\ldots,x_n]\mid f(p_1/q_1,\ldots,p_n/q_n)=0\}. \]
If $q_1=\ldots =q_n=1$, i.e. the given parametrization is polynomial,
$P$ is the elimination ideal $I\cap K[x_1,\ldots,x_n]$ of the ideal $I$ 
generated by $\{x_1-p_1,\ldots,x_n-p_n\}$ in 
$K[x_1,\ldots,x_n,y_1,\ldots,y_m]$. In the general case of rational
parametrizations the situation is slightly more complicated: $P$
is the elimination ideal $J\cap K[x_1,\ldots,x_n]$, where $J$ is the
ideal generated by $\{q_1x_1-p_1,\ldots,q_nx_n-p_n,(\prod_{i=1}^n q_i)z-1\}$ 
in the polynomial ring $K[x_1,\ldots,x_n,y_1,\ldots,y_m,z]$. Hence,
in both cases standard elimination
techniques like resultants, Gr\"obner bases or characteristic sets
can be applied
([Sederberg et al. 1984], [Arnon, Sederberg 1984],
[Goldman 1985], [Buchberger 1987], [Hoffmann 1989],
[Chionh 1990], [Kalkbrener 1990], [Gao, Chou 1991], [Manocha, Canny 1992],
[Recio et al.]).
Gr\"obner bases have the important 
advantage that
they can be used for solving the implicitization problem in full 
generality. On the other hand elimination by means of Buchberger's 
Gr\"obner bases algorithm is often very time-consuming.
Therefore [Hoffmann 1989] suggested to apply Gr\"obner basis
conversion to the implicitization problem. The idea underlying Gr\"obner basis
conversion is the following. It is well-known that the computing
time of a Gr\"obner basis computation 
heavily depends on the chosen order. Instead of computing 
a Gr\"obner basis $G_1$
with respect to a ``slow'' order directly
we could compute a Gr\"obner basis $G_2$
with respect to a ``fast'' order first and then convert $G_2$ to $G_1$.
If the conversion can be done efficiently this method will be faster than
the direct approach.

It makes sense to apply this conversion strategy to the implicitization
problem. Assume that $P$ is given by a polynomial parametrization.
In this case we have to compute a Gr\"obner basis of 
$\{x_1-p_1,\ldots,x_n-p_n\}$
with respect to an elimination order for $\{x_1,\ldots,x_n\}$, i.e.
an order $\prec$
with $X\prec Y$ for every power product
$X$ in $x_1,\ldots,x_n$ and every power
product $Y$ in $y_1,\ldots,y_m$. 
In general this is very time-consuming. Note that 
$\{x_1-p_1,\ldots,x_n-p_n\}$ is already a Gr\"obner basis 
with respect to any elimination order for $\{y_1,\ldots,y_m\}$. 
Hence, in this special case we can use a basis conversion 
algorithm instead of the standard Buchberger algorithm. In the general
case,
$\{q_1x_1-p_1,\ldots,q_nx_n-p_n,(\prod_{i=1}^n q_i)z-1\}$
is usually not a Gr\"obner basis 
but ``close'' to Gr\"obner bases 
with respect to elimination orders for $\{y_1,\ldots,y_m\}$. 
Therefore we expect that also in the general case the conversion
strategy works well.
 
In [Faug{\`e}re et al. 1993]
an algorithm is presented 
which solves the conversion problem by linear algebra techniques.
The FGLM-algorithm  
has a very good practical performance. Its applicability to
the implicitization problem is limited by the fact that it works
for zero-dimensional ideals only. It has been used for hypersurface
implicitization [Hoffmann 1989], [Licciardi, Mora 1994] and for
the implicitization of curves [Licciardi, Mora 1994].

Recently a conversion algorithm for ideals of arbitrary dimension has
been presented in [Collart et al. 1994]. 
The conversion is done in several steps following a
path in the Gr\"obner fan [Mora, Robbiano 1988] of the given ideal. 

Assume that the Hilbert-Poincar\'e series of a homogeneous ideal $I$ is
known. This may happen if $I$ is given by a regular sequence or a Gr\"obner
basis. In [Gianni et al. 1993] it is shown how the knowledge of the
Hilbert-Poincar\'e series can be used to speed up Gr\"obner bases 
computations for $I$. The algorithms in [Gianni et al. 1993] and
[Collart et al. 1994]
can be applied to the implicitization problem in its most
general form. 

We will now give a short presentation of these three conversion
algorithms. For details, we refer to [Faug{\`e}re et al. 1993], 
[Gianni et al. 1993] and
[Collart et al. 1994]. In the last section of this paper
we investigate how these conversion 
algorithms can be applied 
to the implicitization problem.

\section{Notations}
Throughout this paper let $K$ be a field.
The ideal generated by a subset $F$ of the polynomial ring
$K[x_1,\ldots,x_n]$
is denoted by $\langle F\rangle$
and the set of power products in $x_1,\ldots,x_n$ by 
$PP(x_1,\ldots,x_n)$. For subsets $U,V$ of $PP(x_1,\ldots,x_n)$ we define
\[ U\cdot V:=\{uv\mid u\in U,~v\in V\}. \]

Let $\prec$ be an arbitrary
admissible order on
$PP(x_1,\ldots,x_n)$. 
For any non-zero 
polynomial $f\in K[x_1,\ldots,x_n]$ we denote its leading power product by
$lpp_{\prec}(f)$ and its total degree in $x_1,\ldots,x_n$ by $deg(f)$.
By convention, $lpp_{\prec}(0):=0$ and $deg(0):=-1$.
For an ideal $I$ in $K[x_1,\ldots,x_n]$ we denote the ideal 
$\langle \{lpp_{\prec}(f)\mid f\in I\}\rangle$ by $I_{\prec}$. 

Let $\ll$ be an admissible order on $PP(x_1,\ldots,x_n,y_1,\ldots,y_m)$. 
We call $\ll$ an elimination  order for $\{x_1,\ldots,x_n\}$ if there 
exist admissible orders $\ll_1$ on $PP(x_1,\ldots,x_n)$
and $\ll_2$ on
$PP(y_1,\ldots,y_m)$ such that for every 
$u_1,u_2\in PP(x_1,\ldots,x_n)$ and $v_1,v_2\in PP(y_1,\ldots,y_m)$
\[ u_1v_1\ll u_2v_2\ \ \hbox{ iff }\ \  v_1\ll_2 v_2 \hbox{ or }
(v_1=v_2 \hbox{ and } u_1\ll_1 u_2). \]

\section{Basis conversion for zero-dimensional ideals}
The algorithm in [Faug{\`e}re et al. 1993] is based on 
Lemma 1 and the following
simple formula. Let $I$ be an ideal in $K[x_1,\ldots,x_n]$,
$G$ a reduced Gr\"obner basis of $I$ with respect to an arbitrary admissible
order, $c_1\ldots,c_m\in K$ and $f_1,\ldots,f_m\in K[x_1,\ldots,x_n]$. Then
\begin{equation}
\sum_{j=1}^m c_j f_j\in I \ \ \hbox{ iff }\ \ \sum_{j=1}^m c_j h_j=0,
\label{142:1}
\end{equation}
where $h_j$ denotes the normal form of $f_j$ modulo $G$. This is true in
particular for power products $f_j$. The importance of formula (\ref{142:1})
is that it allows us to test ideal membership incrementally using
linear dependence tests.

\medskip
\begin{lemma}
Let $\prec$ be an arbitrary admissible order on $PP(x_1,\ldots,x_n)$ and
$I$ a zero-dimensional ideal in $K[x_1,\ldots,x_n]$. Then the set
$PP(x_1,\ldots,x_n)\setminus \{lpp(f)\mid f\in I\setminus\{0\}\}$ is finite.
\end{lemma}



\medskip
We now sketch the algorithm.
Let $<$ and $\prec$ be two arbitrary
admissible orders on $PP(x_1,\ldots,x_n)$,
$I$ a zero-dimensional ideal in $K[x_1,\ldots,x_n]$ and $F$ a Gr\"obner basis
of $I$ with respect to $<$. We assume that $F$ is given and
we want to compute the reduced Gr\"obner basis $G$ of $I$ 
with respect to $\prec$. Denote the first power products in 
$M_1:=PP(x_1,\ldots,x_n)$ with respect to $\prec$
by $u_1\prec u_2\prec u_3\prec\ldots$ Let $k$ be the smallest
natural number such that there exists a non-zero polynomial in $I$ which
depends on $u_1,\ldots,u_k$ only. Note that Lemma 1 implies the 
existence of $k$. We can compute $k$ using formula (\ref{142:1}): let
$h_j$ be the normal form of $u_j$ modulo $F$. Then $k$ is the smallest
natural number such that there exist $c_1,\ldots,c_{k-1}\in K$ with
\[ h_k+\sum_{j=1}^{k-1} c_j h_j=0. \]
Furthermore, $g_1:=u_k+\sum_{j=1}^{k-1} c_j u_j$ is the polynomial in $I$. Now define 
\[ M_2:=PP(x_1,\ldots,x_n)\setminus (\{u_1,\ldots,u_{k-1}\}\cup 
(\{u_k\}\cdot PP(x_1,\ldots,x_n))) \]
and let $v_1\prec v_2\prec v_3\prec\ldots$ be the first
power products in $M_2$ with respect to $\prec$. Compute the smallest natural number $l$
such that there exists a polynomial $g_2$ in $I$ which
depends on $u_1,\ldots,u_{k-1},v_1,\ldots,v_l$ only. Define
\[ M_3:=PP(x_1,\ldots,x_n)\setminus (\{u_1,\ldots,u_{k-1},v_1,\ldots,v_{l-1}\}\cup 
(\{u_k,v_l\}\cdot PP(x_1,\ldots,x_n))) \]
and continue in the same way. It follows from Dickson's lemma
that we eventually arrive at a natural number $i$ such that
$M_i$ is empty. It is easy to see that the polynomial set $\{g_1,\ldots,g_{i-1}\}$
is the reduced Gr\"obner basis of $I$ with respect to $\prec$.

\smallskip
A formalization of this strategy 
and a complexity analysis can be found in [Faug{\`e}re et al. 1993]
(see also [Hoffmann 1989]). 
Practical experience shows that using
the FGLM-algorithm is generally much faster than
is constructing Gr\"obner bases with respect to
elimination orders
directly.





\section{The Gr\"obner walk: basis conversion for arbitrary ideals}

Let {\bf Q} denote the rational numbers and 
$\omega = (\omega_1, \ldots,\omega_n)$ be an element of the set of 
weight vectors 
\[ \Omega^n:=\{(\psi_1,\ldots,\psi_n)\in{\bf Q}^n\mid  \psi_i\geq 0 \hbox{ for every }
i\in\{1,\ldots,n\}\}. \]
For a power product $u=x_1^{i_1}\cdots x_n^{i_n}$ in 
$PP(x_1,\ldots,x_n)$ we define
its $\omega$-degree by
\[ deg_{\omega}(u):=\sum_{j=1}^n i_j \omega_j. \]
The $\omega$-degree of a non-zero polynomial $f$, abbreviated $deg_{\omega}(f)$, 
is the maximum of the $\omega$-degrees of the power products which occur in $f$ with
non-zero coefficients and $deg_{\omega}(0):=-1$. 
A polynomial $f$ is called $\omega$-homogeneous
if all power products in $f$ have the same $\omega$-degree. 
Note that for $\omega =(1,\ldots,1)$ this notion coincides with standard 
homogeneity.
Obviously, every polynomial $f\not= 0$
can be written in the form $f=in_{\omega}(f)+f'$, where 
$in_{\omega}(f)$ is $\omega$-homogeneous and 
$deg_{\omega}(in_{\omega}(f))>deg_{\omega}(f')$. Furthermore, $in_{\omega}(0):=0$.
For the admissible order $\prec$ and
the weight vector $\omega$
we define the admissible order $_\omega\kern-5pt\prec$ on 
$PP(x_1,\ldots,x_n)$ by
\[ u_1 \,{_\omega\kern-5pt\prec}\, u_2 \ \ \hbox{ if }\ \ 
deg_{\omega}(u_1)<deg_{\omega}(u_2)\ \hbox{ or }\ 
(deg_{\omega}(u_1)=deg_{\omega}(u_2)
\hbox{ and } u_1\prec  u_2). \]

\medskip
We recall the concept of the Gr\"obner fan.
A subset $Q$ of ${\bf Q}^n$ is called a polyhedral set if $Q$ is the 
intersection of
a finite number of closed halfspaces or $Q={\bf Q}^n$.
The Gr\"obner cone of an ideal $I\subseteq K[x_1,\ldots,x_n]$
with respect to the admissible order $\prec$ is defined by
\[ cone(\prec):=
cl(\{\omega\in\Omega^n\mid \{in_{\omega}(f)\mid f\in I\} \hbox{ generates }
I_{\prec}\}), \]
where {\em cl} denotes the usual topological closure in ${\bf Q}^n$. 
This notation
is justified by the following result (see Theorem 2.7 in [Mora, Robbiano 1988]).

\medskip
\begin{theorem}
Let $\prec$ be an admissible order. Then $cone(\prec)$ is 
a convex polyhedral cone in ${\bf Q}^n$ 
with a non-empty interior.
\end{theorem}

\medskip
We call the set $F(I):=\{cone(\prec)\mid\, \prec \hbox{ an admissible order}\}$
the Gr\"obner fan of $I$. For a proof of the following result, 
see Lemma 2.6
in [Mora, Robbiano 1988].

\medskip
\begin{theorem}
The Gr\"obner fan of $I$ has finite cardinality.
\end{theorem}

\medskip
Let $<$ and $\ll$ be two admissible orders and $G=\{g_1,\ldots,g_r\}$ 
the reduced Gr\"obner basis of $I$ with respect 
to $<$. It is easy to show (see Lemma 4.3 in [Collart et al. 1994]) that
\begin{equation}
cone(<)=cone(\ll)\ \ \hbox{ iff }\ \ 
lpp_{<}(g_i)=lpp_{\ll}(g_i)
\hbox{ for every } i\in\{1,\ldots,r\}. \label{64:1}
\end{equation}
As a consequence we obtain that 
\[
cone(<)=cone(\ll)\ \ \hbox{ implies }\ \ G=H, 
\]
where $G$ is the reduced Gr\"obner basis of $I$ with respect
to $<$ and $H$ is the reduced Gr\"obner basis of $I$ with respect
to $\ll$. Hence, we can speak about the reduced Gr\"obner basis 
of $I$ over $cone(<)$.

\medskip
We now sketch the algorithm in [Collart et al. 1994]
for computing the reduced Gr\"obner basis of $I$ with respect to $\ll$,
given admissible orders $<$ and $\ll$ 
and the reduced Gr\"obner basis $G$ of $I$ with respect to $<$.
We may assume without loss of generality that $<$ and $\ll$ are given by 
sequences $S_<$ and $S_{\ll}$ of rational vectors which span ${\bf Q}^n$
(see [Robbiano 1985]). In this case the first members of $S_<$ and $S_{\ll}$, 
denoted
by $\sigma$ respectively $\tau$, are in $cone(<)$ respectively 
$cone(\ll)$.

The basic idea is the following: we move on the line segment 
\[ \overline{\sigma\tau}:=\{(1-a)\sigma +a\tau\mid 0\leq a\leq 1\} \]
from $\sigma$ to $\tau$. Whenever we leave a
Gr\"obner cone $C$ and enter a new cone $C'$ we transform the reduced
Gr\"obner basis over $C$ into the reduced Gr\"obner basis over $C'$.
After finitely many conversions we arrive at $cone(\ll)$ and obtain
the reduced Gr\"obner basis w.r.t. $\ll$.

More precisely, let $\omega$ be the weight vector with 
\[ \overline{\sigma\omega}=\overline{\sigma\tau}\cap cone(<). \]
$\omega$ can be easily computed from $\sigma,\tau$ and $G$ using linear
algebra techniques. It can be shown that if $\tau\not= \omega$ there exists
an $\omega'\in \overline{\omega\tau}$ with $\omega\not=\omega'$ and
$\overline{\omega\omega'}\subseteq cone({_{\omega}\kern-5pt\ll})$. Therefore
after leaving $cone(<)$ we enter $cone({_{\omega}\kern-5pt\ll})$ and we
now have to transform the reduced Gr\"obner basis $G$ over $cone(<)$
into a Gr\"obner basis $F$ over $cone({_{\omega}\kern-5pt\ll})$.
This can be done in the following way.
First of all it is easy to prove that 
$\{in_\omega(g)\mid g\in G\}$ is a
basis of $\langle\{in_{\omega}(f)\mid f\in I\}\rangle$.
Using Buchberger's algorithm we can compute the 
reduced Gr\"obner basis $\{m_1,\ldots,m_s\}$ of 
$\langle\{in_{\omega}(f)\mid f\in I\}\rangle$ 
with 
respect to ${_{\omega}\kern-5pt\ll}$. In the course of this Gr\"obner 
basis computation
$\omega$-homogeneous polynomials $h_{i1},\ldots,h_{ir}$ 
can be constructed
with
\[ m_i=\sum_{j=1}^r h_{ij}in_{\omega}(g_j) \hbox{ and } deg_{\omega}(m_i)=
deg_{\omega}(h_{ij}in_{\omega}(g_j)) \hbox{ for } j\in \{1,\ldots,r\} 
\hbox{ with }
h_{ij}\not= 0. \]
Replacing $in_{\omega}(g_j)$ by $g_j$ we obtain
\[
f_i:=\sum_{j=1}^r h_{ij}g_j \ \ \hbox{ and }\ \ 
F:=\{f_1,\ldots,f_s\}. \]
It is shown in [Collart et al. 1994] that 
$F$ is a Gr\"obner basis of $I$ with 
respect to ${_{\omega}\kern-5pt\ll}$.
Using (\ref{64:1}) as termination condition we obtain a Gr\"obner basis
w.r.t. $\ll$ after finitely many basis conversions.

\smallskip
Note that we have obtained $F$ by applying Buchberger's algorithm to
$\{in_\omega(g)\mid g\in G\}$ instead of $G$. In general the polynomials in 
$\{in_\omega(g)\mid g\in G\}$ are
much smaller than the polynomials in $G$. Therefore we expect that
each of these Gr\"obner basis conversions in the Gr\"obner
walk is much faster than the direct computation of the Gr\"obner basis 
w.r.t. $\ll$. On the other hand several of these conversions have
to be done. 
At present we know nothing about the practical
performance of the Gr\"obner walk
because only an experimental implementation in Mathematica
has been made.


\section{Basis conversion for homogeneous ideals using Hilbert functions}

Let $I$ be a homogeneous ideal in $K[x_1,\ldots,x_n]$, 
$G:=\{g_1,\dots,g_s\}$ a basis of $I$
and $\prec$ an admissible order 
on 
$PP(x_1,\ldots,x_n)$. 

\smallskip
Assume that we know the Hilbert function $HF_I$ of $I$.
This may happen, for instance, if $G$ is a Gr\"obner basis with respect to
an arbitrary order or $g_1,\dots,g_s$ is a regular sequence.
Compute the Hilbert function $HF_J$ of the monomial ideal 
$J:=\langle \{lpp_{\prec}(g_1),\dots,lpp_{\prec}(g_s)\}\rangle$.
If $HF_I=HF_J$ then $G$ is a Gr\"obner basis of $I$ w.r.t $\prec$. 
Otherwise, let $m$ be such
that $HF_J(j)=HF_I(j)$ for $j<m$ and $HF_J(m)=HF_I(m)+k$ with $k>0$. 
We deduce that

\smallskip
\noindent
(1) $G$ contains all the elements of degree $<m$ of a Gr\"obner basis of $I$ and

\noindent
(2) a Gr\"obner basis of $I$ contains $k$ further elements of degree $m$.

\smallskip
\noindent
With this information we can perform the Gr\"obner bases algorithm, but with
the following modification:

\smallskip
\noindent
(1) all critical pairs of degree $<m$ are useless (the degree of a
critical pair being the degree  of the lcm of the two
leading power products),

\noindent
(2) precisely $k$ critical pairs of degree $m$ are useful.

\smallskip
\noindent
When we have found $k$ useful critical
pairs of degree $m$, giving rise to new elements $g_{s+1},\ldots,g_{s+k}$ in
the Gr\"obner basis, we recompute the new Hilbert function, and proceed
in the algorithm. For efficiently computing Hilbert functions resp. 
Hilbert-Poincar\'e series, consult [Bigatti et al. 1991].


\section{Implicitization by basis conversion}
We will now investigate how these conversion 
algorithms can be applied 
to the implicitization problem. Let us first assume that 
a polynomial parametrization
\[ (p_1,\ldots,p_n)\in K[y_1,\ldots,y_m]^n \]
is given. Then $P:=\{f\in K[x_1,\ldots,x_n]\mid f(p_1,\ldots,p_n)=0\}$
is the elimination ideal $I\cap K[x_1,\ldots,x_n]$, where 
$I:=\langle\{x_1-p_1,\ldots,x_n-p_n\}\rangle$. Note that 
$G:=\{x_1-p_1,\ldots,x_n-p_n\}$ is already a Gr\"obner basis 
with respect to any elimination order for $\{y_1,\ldots,y_m\}$.
Obviously $I$ is not 
zero-dimensional and this is the main obstacle to applying the FGLM-algorithm 
to the implicitization
problem. Fortunately in some special cases the strategy of the
FGLM-algorithm also works for ideals of positive dimension. Assume that
$(p_1,\ldots,p_n)$ is a parametrization of a hypersurface, i.e. the
dimension of $P$ is $n-1$. Then $P$
is generated by a single polynomial. We can find such a generator
using the same 
strategy as in the FGLM-algorithm (see [Hoffmann 1989]): 
denote the first power products in $PP(x_1,\ldots,x_n)$ w.r.t. a total
degree order $\prec$ by $u_1\prec u_2\prec u_3\prec\ldots$ and test 
linear dependence between the normal forms of the $u_j$ modulo the Gr\"obner
basis $G$. In this way we can find a polynomial in $P$ of minimal total 
degree. Obviously
this polynomial generates $P$. 

Other strategies for applying the FGLM-algorithm
to hypersurface
implicitization and to the implicitization of curves are given in 
[Licciardi, Mora 1994].

It is obvious how the implicitization problem can be solved by means 
of the Gr\"obner walk algorithm: 
since $G$ is a Gr\"obner basis with respect to any elimination 
order for $\{y_1,\ldots,y_m\}$ the Gr\"obner walk algorithm can be used for
successively transforming $G$ into
a Gr\"obner basis with respect to an elimination 
order for $\{x_1,\ldots,x_n\}$.

Assume that the $p_i$ are homogeneous of degree $d_i$. 
We can make $x_1-p_1,\ldots,x_n-p_n$
homogeneous by giving weight $d_i$ to variable $x_i$.
Since the sequence $x_1-p_1,\ldots,x_n-p_n$ is regular we already
know that the Poincar\'e series of $K[x_1,\ldots,x_n,y_1,\ldots,y_m]/I$ is
\[ \prod (1-T^{d_i})/(1-T)^{n+m}. \]
Hence, we can 
apply the algorithm in [Gianni et al. 1993]. 
If the $p_i$ are not homogeneous we can homogenize them, proceed as before
and dehomogenize the result.


\medskip
If the given parametrization 
\[ (p_1/q_1,\ldots,p_n/q_n)\in K(y_1,\ldots,y_m)^n \]
is not polynomial but rational 
the situation is slightly more complicated: the ideal 
$P:=\{f\in K[x_1,\ldots,x_n]\mid f(p_1/q_1,\ldots,p_n/q_n)=0\}$ 
is the elimination ideal $J\cap K[x_1,\ldots,x_n]$, where $J$ is the
ideal generated by $\{q_1x_1-p_1,\ldots,q_nx_n-p_n,(\prod_{i=1}^n q_i)z-1\}$ 
in the polynomial ring $K[x_1,\ldots,x_n,y_1,\ldots,y_m,z]$.
The set
$G:=\{q_1x_1-p_1,\ldots,q_nx_n-p_n,(\prod_{i=1}^n q_i)z-1\}$
is usually not a Gr\"obner basis. Hence before we can apply the FGLM-algorithm
or the Gr\"obner walk we have to compute a Gr\"obner basis $G'$ of $P$
with respect to an arbitrary order. In general, elimination orders for
$\{y_1,\ldots,y_m\}$ work well. After having computed $G'$ we
can proceed as in the case of polynomial parametrizations.

If we want to apply the algorithm based on Hilbert functions we have
to homogenize the polynomials 
\[ (\prod_{i=1}^n q_i)z-1,q_1x_1-p_1,\ldots,q_nx_n-p_n. \]
It is easy to see that the homogenized sequence 
is regular. Therefore we know the 
Poincar\'e series of $K[x_1,\ldots,x_n,y_1,\ldots,y_m,z]/J'$, where
$J'$ is the ideal generated by the homogenized sequence, and we proceed
as in the case of polynomial parametrizations.

\medskip
We have now shown that in principle these conversion algorithms are
well applicable to the implicitization problem.
However the practical value of the implicitization algorithms 
based on Gr\"obner basis
conversion is difficult to assess. The main problem is that at present
almost no experimental data is available.  
A carefully study of the practical applicability of these 
conversion methods would be very interesting.

\vskip 1cm
\noindent
{\Large\bf References}
{\small

\vskip .5cm
\noindent
[Arnon, Sederberg 1984]\ \ \ 
Arnon, D.S.; Sederberg, T.W.:
Implicit equation for a parametric surface by Gr\"obner basis.
{\em Proc. 1984 MACSYMA User's Conference}, 431--436,
General Electric, Schenectady, New York (1984).
 
\medskip
\noindent
[Bigatti et al. 1991]\ \ \ 
Bigatti, A.M.; Caboara, M.; Robbiano L.:
On the computation of Hilbert-Poincar\'e series. {\em Applicable Algebra
in Engineering, Communication and Computing} {\bf 2}, 21--33 (1991).

\medskip
\noindent
[Buchberger 1987]\ \ \ 
Buchberger, B.:
Applications of Gr\"obner bases in non-linear computational
  geometry.
{\em Proc. Workshop on Scientific Software}, 59--88, IMA, Minneapolis,
  USA (1987).

\medskip
\noindent
[Chionh 1990]\ \ \ 
Chionh, E.W.:
{\em Base points, resultants, and the implicit representation of
  rational surfaces}.
PhD thesis, Department of Computer Science, University of Waterloo,
  Canada (1990).

\medskip
\noindent
[Collart et al. 1994]\ \ \ 
Collart, S.; Kalkbrener, M.; Mall, D.:
The Gr\"obner walk. Technical Report 94-02, ETH-Zurich, Switzerland (1994).


\medskip
\noindent
[Faug{\`e}re et al. 1993]\ \ \ 
Faug{\`e}re, J.C.; Gianni, P.; Lazard, D.; Mora, T.:
Efficient computation of zero-dimensional Gr{\"o}bner bases by
  change of ordering. {\em Journal of Symbolic Computation} {\bf 16},
329--344 (1993).

\medskip
\noindent
[Gao, Chou 1991]\ \ \ 
Gao, X.S.; Chou S.C.:
Computations with parametric equations. {\em Proc. ISSAC'91}, 122--127 (1991).

\medskip
\noindent
[Gianni et al. 1993]\ \ \ 
Gianni, P.; Mora, T.; Robbiano, L.; Traverso, C.:
Hilbert functions and Buchberger algorithm. Preprint (1993).

\medskip
\noindent
[Goldman 1985]\ \ \ 
Goldman, R.N.:
The method of resolvents: a technique for the implicitization,
  inversion, and intersection of non-planar, parametric, rational cubic
  curves.
{\em Computer Aided Geometric Design} {\bf 2}, 237--255 (1985).

\medskip
\noindent
[Hoffmann 1989]\ \ \ 
Hoffmann, C.M.:
Geometric and Solid Modeling: An Introduction.
Morgan Kaufmann Publishers Inc. (1989).

\medskip
\noindent
[Kalkbrener 1990]\ \ \ 
Kalkbrener, M.:
Implicitization of rational curves and surfaces.
{\em Proc. AAECC-8}, 249--259, Tokyo, Japan (1990).

\medskip
\noindent
[Manocha, Canny 1992]\ \ \ 
Manocha, D.; Canny, J.F.:
Implicit representation of parametric surfaces.
{\em Journal of Symbolic Computation} {\bf 13},
485--510 (1992).

\medskip
\noindent
[Licciardi, Mora 1994]\ \ \ 
Licciardi, S.; Mora, T.:
Implicitization of hypersurfaces and curves by the Primbasissatz and basis
conversion. {\em Proc. ISSAC'94}, 191--196 (1994).

\medskip
\noindent
[Mora, Robbiano 1988]\ \ \ 
Mora, T.; Robbiano, L.:
The Gr\"obner fan of an ideal.
{\em Journal of Symbolic Computation} {\bf 6},
183--208 (1988).

\medskip
\noindent
[Recio et al.]\ \ \ 
Recio, T.; Alonso, C.; Gutierrez, J.:
An implicitization algorithm with fewer variables. To appear in
{\em Computer Aided Geometric Design}.

\medskip
\noindent
[Robbiano 1985]\ \ \ 
Robbiano, L.:
Term orderings on the polynomial ring. {\em Proc. EUROCAL'85}, 513--517 (1985).

\medskip
\noindent
[Sederberg et al. 1984]\ \ \ 
Sederberg, T.W.; Anderson, D.C.; Goldman, R.N.:
Implicit representation of parametric curves and surfaces.
{\em Computer Vision, Graphics, and Image Processing} {\bf 28}, 72--84
(1984).
}

\end{document}
