New Elimination Tools based on Symmetric Functions for the Implicitization of Parametric Curves and Surfaces.

L. González-Vega^{∗} Dpto. Matemáticas, Estadística y Computación Universidad de Cantabria, Santander 39071, Spain

Abstract

This paper is devoted to present a new algorithm computing the implicit equation of a parametric plane curve and several classes of parametric surfaces in the three dimensional euclidean space. This algorithm does not require of the computation of any symbolic determinant or Grobner Basis, being these tools replaced by the computation of some symmetric functions, in particular the Newton Sums on the solution set of a well precised zero dimensional ideal.

1 Introduction

One of the main problems in the manipulation of parametric curves and surfaces in computer aided design is the finding of efficient algorithms for computing the implicit equation of curves and surfaces parametrized by rational functions (see for example [M93] or the chapters 5 and 7 in [H89]). This is due, for example, to the fact that, if for tracing the considered curve and surface the parametric representation is the most convenient, to decide in a efficient way the position of a point with respect to the curve or surface considered, the implicit equation is desired.

The implicitization problem for hypersurfaces parametrized in a rational way can be stated in the following terms: let V be a hypersurface in C^{n} parametrized by (i ∈ {1, …, n}):

x_{i} = \frac{f_{i}(t_{1}, …, t_{n−1})}{g_{i}(t_{1}, …, t_{n−1})}

where f_{i} and g_{i} belong to ZZ[t_{1}, …, t_{n−1}] with gcd(f_{i}, g_{i}) = 1. The implicitization problem for V is the finding of a non zero element R_{V}(x_{1}, …, x_{n}) in ZZ[x_{1}, …, x_{n}] with the smallest possible total degree and such that:

R_{V}(\frac{f_{1}(\underline{t})}{g_{1}(\underline{t})}, …, \frac{f_{n}(\underline{t})}{g_{n}(\underline{t})}) = 0

More general formulations of the implicitization problem for arbitrary parametric varieties can be found in [AGR94],

[CLO93] (chapter 3) or [GC92].

This paper is devoted to show a new family of algorithms computing the implicit equation of plane curves and space surfaces parametrized in a rational way. The main advantange of these algorithms is that they do not require the computation of any symbolic determinant or Grobner Bases. These tools coming from Elimination Theory are replaced by the computation of some symmetric functions (Newton Sums) by developping in negative powers of the parameters some well precised rational functions.

The algorithms to be presented in sections 3 and 4 solve completely the cases of plane curves parametrized in a rational way and space surfaces described by a parametrization with the following structure:

x = f(t_{1}, t_{2})  f ∈ Q[t_{1}, t_{2}]
y = \frac{t_{1}^{n_{1}} + Q_{1}(t_{1}, t_{2})}{D_{1}(t_{1}, t_{2})} deg(Q_{1}), deg(D_{1}) < n_{1}

z = \frac{t_{2}^{n_{2}} + Q_{2}(t_{1}, t_{2})}{D_{2}(t_{1}, t_{2})} deg(Q_{2}), deg(D_{2}) < n_{2}

∗Partially supported by CICyT PB 92/0498/C02/01 (Geometría Real y Algoritmos), Caja Cantabria, TIC–1026–CE and Esprit/Bra 6846 (PoSSo).

The results of section 4 extend automatically to the cases of parametric hypersurfaces whose parametrization has a structure as the previous one but for sake of simplicity the attention has been focused only over the case of space surfaces.

Section 2 is devoted to present several algorithms for computing some symmetric functions (in particular Newton Sums) on the solutions of a polynomial system of equations with a finite number of solutions. These results are the basis of the implicitization algorithms presented in sections 3 and 4.

2 Computation of symmetric functions

The goal of this section is the presentation of several formulae computing some symmetric functions (in particular Newton Sums) on the solutions of a polynomial system of equations with a finite number of solutions. First the case of one variable is considered. Let f and g be two polynomials in Q[T] such that:

f = ∏_{i=1}^{s}(T − Δ_{i})^{e_{i}} Δ_{i} ∈ C

Next theorem shows a way of computing the symmetric function in the Δ_{i}’s (the trace):

T_{f}(g) = ∑_{i=1}^{s} e_{i}g(Δ_{i}) ∈ Q

Its proof is straightforward.

Theorem 2.1 The rational number T_{f}(g) is the coefficient of T^{−1} in the expansion in negative powers of T of the rational function:

\frac{g(T) · f′(T)}{f(T)}

The most usual types of symmetric functions (Elementary and Newton Sums) will play a prominent role in the implicitization algorithms to be presented in the next two sections. These symmetric functions are presented in the next definitions.

Definition 2.2 Let x_{1}, …, x_{n} be a collection of n variables. The Elementary Symmetric Functions of order n,

σ_{1}, …, σ_{n}

are defined by the following equality:

∏_{i=1}^{n}(T − x_{i}) = T^{n} + σ_{1}T^{n−1} + … + σ_{n−1}T + σ_{n}

Definition 2.3 Let x_{1}, …, x_{n} be a collection of n variables. The Newton Sums of order n,

S_{0}, S_{1}, S_{2}, …, S_{j}, …

are:

S_{j}(x_{1}, …, x_{n}) = ∑_{k=1}^{n} x_{k}^{j}

Next proposition presents Newton Identities allowing the conversion (in the two directions) between the Elementary Symmetric Functions and the Newton Sums. A proof of this proposition can be found in [S93].

Proposition 2.4 (Newton Identities) Let x_{1}, …, x_{n} be a collection of n variables. For every j in {1, …, n} the following identity holds:

jσ_{j}(\underline{x}) + S_{j}(\underline{x}) + S_{j−1}(\underline{x})σ_{1}(\underline{x}) + … + S_{1}(\underline{x})σ_{j−1}(\underline{x}) = 0

Next the formulae presented in theorem 2.1 is generalized to the case of a polynomial system of equations with a finite number of complex solutions and a particular structure. Let F_{1}, …, F_{n} be polynomials in Q[x_{1}, …, x_{n}] such that the polynomial system of equations:

\begin{aligned}F_{1}(x_{1}, …, x_{n}) & = 0 \\ F_{2}(x_{1}, …, x_{n}) & = 0 \\ ⋮ & ⋮ \\ F_{n}(x_{1}, …, x_{n}) & = 0 \end{aligned}

has a finite number of solutions in C^{n}, Δ_{1}, …, Δ_{s}, and let e_{i} be the multiplicity of every Δ_{i}. If g ∈ Q[x_{1}, …, x_{n}] then next theorem presents a way of computing the symmetric function (in the Δ_{i}’s):

T_{F_{1},...,F_{n}}(g) = ∑_{i=1}^{s} e_{i}g(Δ_{i}) ∈ Q

Theorem 2.5 Let F_{1}, …, F_{n} be polynomials in Q[x_{1}, …, x_{n}] such that

F_{1}(x_{1}, …, x_{n}) = x_{1}^{m_{1}} + Q_{1}(x_{1}, …, x_{n})
F_{2}(x_{1}, …, x_{n}) = x_{2}^{m_{2}} + Q_{2}(x_{1}, …, x_{n})
⋮  ⋮
F_{n}(x_{1}, …, x_{n}) = x_{n}^{m_{n}} + Q_{n}(x_{1}, …, x_{n})

with every Q_{i} a polynomial with total degree smaller than m_{i}. If g(x_{1}, …, x_{n}) is a polynomial in Q[x_{1}, …, x_{n}] then T_{F_{1},...,F_{n}}(g) is equal to the coefficient of x_{1}^{−1} · . . . · x_{n}^{−1} in the expansion in negative powers of the x_{i}’s of the rational function:

\frac{g · Jac(F_{1}, …, F_{n})}{x_{1}^{m_{1}} · . . . · x_{n}^{m_{n}}} · ∑_{k=0}^{deg(g)}(−1)^{k} ∑_{α_{1}+...+α_{n}=k} ∏_{i=1}^{n} (\frac{Q_{i}}{x_{i}^{m_{i}}} )^{α_{i}}

where Jac is the jacobian determinant of the polynomials F_{1}, …, F_{n}.

The proof of this theorem is a consequence of the formulae of the multidimensional logarithmic residue (see [T92] or [CDS94]).

3 Implicitization on plane curves parametrized in a rational way

This section is devoted to present a new algorithm computing the implicit equation of a curve C in C^{2} parametrized by:

x = \frac{f_{1}(t)}{f_{2}(t)} y = \frac{g_{1}(t)}{g_{2}(t)}

where f_{1}, f_{2}, g_{1} and g_{2} are polynomials in ZZ[t] such that gcd(f_{1}, f_{2}) = 1 and gcd(g_{1}, g_{2}) = 1.

3.1 The polynomial case

First it is regarded the case where the parametrization of C is polynomial: f_{2}(t) = 1 and g_{2}(t) = 1. The keypoint of the algorithm is the simple fact assuring that if R_{C}(x, y) is the implicit equation of C then R_{C}(x, y) is the squarefree part of the resultant of the polynomials f_{1}(t) − x and g_{1}(t) − y with respect to the variable t (see [H89] for example). In order words, R_{C}(x, y) is the squarefree part of the polynomial in Q[x, y]:

H_{C}(x, y) = ∏_{{t̃:g_{1}(t̃)−y=0}}(x − f_{1}(t̃))

where the roots of g_{1}(t) − y = 0 are considered in an algebraic closure of Q(y) (see [DST87] for this description of the resultant).

If n is the degree of g_{1} then H_{C}(x, y) has the following structure:

H_{C}(x, y) = x^{n} + r_{1}(y)x^{n−1} + … + r_{n}(y)

where r_{k}(y) is exactly the k-th elementary symmetric function of orden n in the values obtained when evaluating f_{1} on the n roots (taking into account multiplicities) of g_{1}(t) − y = 0. If t̃_{1}, …, t̃_{n} are those roots then:

r_{k}(y) = σ_{k}(f_{1}(t̃_{1}), …, f_{1}(t̃_{n}))

By using Newton Identities (proposition 2.1), polynomials r_{k}(y) are easy to determine once the Newton Sums on

f_{1}(t̃_{1}), …, f_{1}(t̃_{n})

are determined. These polynomials

S_{j}(f_{1}(t̃_{1}), …, f_{1}(t̃_{n}))

are obtained by using theorem 2.1, through the expansion in negative powers of t of the rational functions:

\frac{(f_{1}(t))^{j}g′_{1}(t)}{g_{1}(t) − y} j ∈ \{1, …, n\}

This remark ends the proof of the next theorem which solves the implicitization problem for plane curves parametrized in a polynomial way.

Theorem 3.1 Let C be a plane curve defined by a polynomial parametrization:

x = f(t) y = g(t)

and n = deg(g). Then the implicit equation of C is the squarefree part of the polynomial:

H_{C}(x, y) = x^{n} + r_{1}(y)x^{n−1} + … + r_{n}(y)

where (k ∈ {1, …, n}):

kr_{k}(y) = −S_{k}(y) − S_{k−1}(y)r_{1}(y) − … − S_{1}(y)r_{k−1}(y)

and every S_{j}(y) is the coefficient of t^{−1} in the expansion in negative powers of t of the rational function:

\frac{(f(t))^{j}g′(t)}{g(t) − y}

The using of symmetric functions in Computer Algebra to determine and deal with the resultant of two polynomials is not new (see for example [L84], [DT87], [V87], [GLV88] or [V88]).

Example 3.2 The method presented in theorem 3.1 is used to determine the implicit equation of the curve C defined by the parametrization:

x = f(t) = t^{4} − t + 1 y = g(t) = t^{3} + t + 1

In this case the polynomial H_{C}(x, y) has the structure:

x^{3} + r_{1}(y)x^{2} + r_{2}(y)x + r_{3}(y)

The computation of the polynomials r_{1}(y), r_{2}(y) and r_{3}(y) requires the knowledge of the Newton Sums (of order 3) S_{1}(y), S_{2}(y) and S_{3}(y) on the values taken by f(t) over the roots of:

t^{3} + t + 1 − y = 0

This is obtained by developping in negative powers of t the rational function g′(t)/(g(t) − y):

\frac{3t^{2}+1}{t^{3}+t+1−y} = \frac{3}{t} − \frac{2}{t^{3}} − \frac{−3+3y}{t^{4}} + \frac{2}{t^{5}} + \frac{5−5y}{t^{6}}
+\frac{1−6y+3y^{2}}{t^{7}} − \frac{−7+7y}{t^{8}} − \frac{−6+16y−8y^{2}}{t^{9}}
+\frac{6−9y^{2}+3y^{3}}{t^{10}} + \frac{13−30y+15y^{2}}{t^{11}} − \frac{−22y+33y^{2}−11y^{3}}{t^{12}}
−\frac{−19+36y−6y^{2}−12y^{3}+3y^{4}}{t^{13}} − \frac{−13+65y−78y^{2}+26y^{3}}{t^{14}}
+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

and multiplying such expansion by f(t), (f(t))^{2} and (f(t))^{3}:

\begin{aligned}S_{1}(y) & = 5 \\ S_{2}(y) & = −11 + 26y − 8y^{2} \\ S_{3}(y) & = −76 + 93y + 6y^{2} − 21y^{3} + 3y^{4} \end{aligned}

Newton Identities allow to conclude that:

\begin{aligned}r_{1}(y) & = −5 \\ r_{2}(y) & = 18 − 13y + 4y^{2} \\ r_{3}(y) & = −23 + 34y − 22y^{2} + 7y^{3} − y^{4} \end{aligned}

and that the implicit equation of C is:

R_{C}(x, y) = x^{3} − 5x^{2} + (18 − 13y + 4y^{2})x − 23 + 34y − 22y^{2} + 7y^{3} − y^{4}

3.2 The rational case

Next it is considered the case of a plane curve C parametrized in a rational way by:

x = \frac{f_{1}(t)}{f_{2}(t)} y = \frac{g_{1}(t)}{g_{2}(t)}

where f_{1}, f_{2}, g_{1} and g_{2} are polynomials in ZZ[t] such that gcd(f_{1}, f_{2}) = 1 and gcd(g_{1}, g_{2}) = 1.

The philosophy of the method is the same than in the previous case but the manipulation of denominators implies some modifications. First we consider the polynomials in ZZ[x, y][t]:

F = f_{2}(t)x − f_{1}(t) G = g_{2}(t)y − g_{1}(t)

together with the polynomial in ZZ(y)[x] defined by:

H_{C}(x, y) = ∏_{{t̃:G(y,t̃)=0}}(f_{2}(t̃)x − f_{1}(t̃))

The squarefree part of the numerator of H_{C}(x, y) is the implicit equation R_{C}(x, y) of C which is exactly the resultant of F and G with respect to t.

Since the polynomials f_{2}(t) and G(y, t) have no common factors (if such factor exists then it will be a common factor of g_{1}(t) and g_{2}(t)) then there exist polynomials u(y, t) and v(y, t) in ZZ(y)[t] such that

u(y, t)f_{2}(t) + v(y, t)G(y, t) = 1

This equality allows to write:

H_{C}(x, y) = ∏_{{t̃:G(y,t̃)=0}} f_{2}(t̃)(x − u(y, t̃)f_{1}(t̃)) = ∏_{{t̃:G(y,t̃)=0}} f_{2}(t̃) ∏_{{t̃:G(y,t̃)=0}}(x − u(y, t̃)f_{1}(t̃))

being the first factor an element of ZZ(y) (the resultant of f_{2}(t) and G(t, y) with respect to t divided by a well precised power of the leading coefficient of G with respect to t) and the second one a polynomial in ZZ(y)[x] such that the squarefree part of its numerator is R_{C}(x, y). Denoting by H̃_{C}(x, y) this second factor, if n is the degree of G(y, t) with respect to t then:

H̃_{C}(x, y) = x^{n} + … + r_{n−1}(y)x + r_{n}(y)

with r_{j}(y) ∈ ZZ(y).

Using the same arguments than in the polynomial case, the r_{k}(y)’s can be determined through the computation of the Newton Sums:

S_{j}((u(y, t̃_{1})f_{1}(t̃_{1}), …, u(y, t̃_{n})f_{1}(t̃_{n})))

where j ∈ {1, …, n} and t̃_{1}, …, t̃_{n} the roots of G(y, t) = 0. As usual such Newton Sum is determined through the expansion of:

\frac{(u(y, t)f_{1}(t))^{j}(g′_{1}(t) − yg′_{2}(t))}{g_{1}(t) − yg_{2}(t)}

in negative powers of t. Thus, it has been obtained the proof of the next theorem solving the implicitization problem for plane curves parametrized in a rational way.

Theorem 3.3 Let C be a plane curve defined by a rational parametrization:

x = \frac{f_{1}(t)}{f_{2}(t)} y = \frac{g_{1}(t)}{g_{2}(t)}

with gcd(f_{1}, f_{2}) = 1, gcd(g_{1}, g_{2}) = 1 and n = max{deg(g_{1}), deg(g_{2})}. Then the implicit equation of C is the squarefree part of the numerator of:

H̃_{C}(x, y) = x^{n} + r_{1}(y)x^{n−1} + … + r_{n}(y)

where (k ∈ {1, …, n}):

kr_{k}(y) = −S_{k}(y) − S_{k−1}(y)r_{1}(y) − … − S_{1}(y)r_{k−1}(y)

and every S_{j}(y) is the coefficient of t^{−1} in the expansion in negative powers of t of the rational function:

\frac{(u(y, t)f_{1}(t))^{j}(g′_{1}(t) − yg′_{2}(t))}{g_{1}(t) − yg_{2}(t)}

and u(y, t) is an element in ZZ(y)[t] verifying:

u(y, t)f_{2}(t) + v(y, t)(g_{1}(t) − yg_{2}(t)) = 1

The computation of u(y, t) (the inverse of f_{2}(t) modulo G(y, t)) can be performed by using the extended euclidean algorithm or the formulae:

u(y, t) = \frac{L(y, t)}{Res_{t}(f_{2}(t), G(y, t))}

where L(y, t) is a polynomial of degree n − 1 in t defined by means of a determinant of size n + deg(f_{2}) involving the powers of t up to degree n − 1 and the coefficients of f_{2}(t) and G(y, t) as polynomials in t. A more detailed description can be found in [GV89] or [L82].

4 Implicitization of space surfaces parametrized in a rational way

This section is devoted to present a new algorithm computing the implicit equation of a surface S in C^{3} parametrized by:

x = \frac{f_{1}(t_{1}, t_{2})}{f_{2}(t_{1}, t_{2})} y = \frac{g_{1}(t_{1}, t_{2})}{g_{2}(t_{1}, t_{2})} z = \frac{h_{1}(t_{1}, t_{2})}{h_{2}(t_{1}, t_{2})}

where f_{1}, f_{2}, g_{1}, f_{1}, f_{2}, g_{1}, g_{2}, h_{1} and h_{2} are polynomials in ZZ[t_{1}, t_{2}] such that gcd(f_{1}, f_{2}) = 1, gcd(g_{1}, g_{2}) = 1 and gcd(h_{1}, h_{2}) = 1 verifying some additional assumptions.

4.1 Reduction to the case of plane curves

If the parametrization of the parametric surface S verifies:

max{deg_{t_{2}}(h_{1}(t_{1}, t_{2})), deg_{t_{2}}(h_{2}(t_{1}, t_{2}))} = 1

then it is posible to describe t_{2} in a rational way in terms of z and t_{1}. Replacing this expression of t_{2} in x and y, it is obtained that the problem of computing the implicit equation of S has been reduced to determine such equation for the plane curve:

x = \frac{F_{1}(t_{1}, z)}{F_{2}(t_{1}, z)} y = \frac{G_{1}(t_{1}, z)}{G_{2}(t_{1}, z)}

Example 4.1 In this example it is showed one of the advantages of using symmetric functions to compute implicit equations of parametric hypersurfaces: the avoiding of extraneous factors. A hyperboloid in C^{3} can be parametrized by:

x = \frac{t^{2} − 2st − 1}{t^{2} + 1} y = \frac{2t + st^{2} + s}{t^{2} + 1} z = s

Its implicit equation is determined by considering the parametric plane curve:

x = \frac{t^{2} − 2zt − 1}{t^{2} + 1} y = \frac{2t + zt^{2} + z}{t^{2} + 1}

The using of the algorithm presented in the previous section (theorem 3.3) provides as result the equation:

y^{2} + x^{2} − 1 − z^{2}

By using the Sylvester Resultant the equation obtained contains an extraneous factor:

4(1 + z^{2})(y^{2} + x^{2} − 1 − z^{2})

that needs to be removed by using a factorization algorithm.

Next table shows the comparison of the algorithm here presented with respect other methods solving the same problem over the following examples (extracted from [K91] and [AGR94]):

\begin{matrix}(1) & x = \frac{t^{2}−2st−1}{t^{2}+1} & y = \frac{2t+st^{2}+s}{t^{2}+1} & z = s \\ (2) & x = \frac{u+2t^{4}−1}{u−t−2} & y = \frac{t^{2}u+1}{t} & z = \frac{1}{tu} \\ (3) & x = \frac{t^{2}−u^{2}}{u} & y = \frac{t^{2}−u^{2}}{t} & z = \frac{1}{t−u} \\ (4) & x = \frac{ut+2t^{5}−t}{ut−v−2t} & y = \frac{t^{3}u+t}{v} & z = \frac{1}{tu} \end{matrix}

The computation was performed by using the release 3 of Maple V on a Sparc–15 Workstation (timings are in seconds):

                                  Ex. Sym  Res  Kal  Rab  Quo

(1) 1.2 3.5 4.2 1.8 7.0
(2) 0.6 0.7 21 ⋆ 29
(3) 0.1 0.1 3.7 0.8 2.6
(4) 0.7 1.1 •  ⋆ 170

Sym corresponds to the algorithm presented in this section, Res to the algorithm computing the Sylvester Resultant plus the timing of the factorization, Kal to the algorithm presented in [K91], Rab to the algorithm using the Rabinowitsch’s trick (Grobner Bases plus adding a new extra variable to avoid problems with denominators) and Quo to the algorithm presented in [AGR94]. The symbol • indicates that the corresponding algorithm does not work in such example and ⋆ indicates that the computation did not end in 5 minutes. The timings corresponding to Kal, Rab and Quo were taken from [AGR94] and thus the previous table must be taken only as indicative since the computations were performed in very different computers. To remark finally that in (1) and (3) appear extraneous factors when computing the Sylvester Resultant.

4.2 The polynomial case

In this section the problem of computing the implicit equation of a surface parametrized in a polynomial way is solved by using the same strategy followed in subsection 3.1. Let S be a surface in C^{3} parametrized by:

x = f(t_{1}, t_{2}) y = g(t_{1}, t_{2}) z = h(t_{1}, t_{2})

where f, g and h are polynomials in ZZ[t_{1}, t_{2}]. The key point is again to compute:

H_{S}(x, y, z) = ∏_{(t̃_{1},t̃_{2})∈V}(x − f(t̃_{1}, t̃_{2}))

where V is the set of zeros of the polynomials g(t_{1}, t_{2}) − y = 0 and h(t_{1}, t_{2}) − z = 0 in an algebraic closure of C(y, z). In order to make the things properly, first it is necessary to assure that the set V is finite: this is obtained by assuming that g(t_{1}, t_{2}) and g(t_{1}, t_{2}) have the following structure:

\begin{matrix}g_{1}(t_{1}, t_{2}) = t_{1}^{n_{1}} + Q_{1}(t_{1}, t_{2}) \\ h_{1}(t_{1}, t_{2}) = t_{2}^{n_{2}} + Q_{2}(t_{1}, t_{2}) \end{matrix}

(with deg(Q_{1}) < n_{1} and deg(Q_{2}) < n_{2}). This hypothesis comes motivated by theorem 2.5 which allows to determine symmetric functions over the solution set of polynomial systems of equations with this structure. In this case, next theorem is clear after 2.5 and the proofs of the theorems 3.1 and 3.3.

Theorem 4.2 Let S be a surface defined by a polynomial parametrization:

x = f(t_{1}, t_{2})  y = g(t_{1}, t_{2})  z = h(t_{1}, t_{2})

such that the polynomials g and h have the following structure:

\begin{matrix}g_{1}(t_{1}, t_{2}) = t_{1}^{n_{1}} + Q_{1}(t_{1}, t_{2}) \\ h_{1}(t_{1}, t_{2}) = t_{2}^{n_{2}} + Q_{2}(t_{1}, t_{2}) \end{matrix}

(with deg(Q_{1}) < n_{1} and deg(Q_{2}) < n_{2}), n = deg(f) and m = n_{1}n_{2}. Then the implicit equation of S is the squarefree part of the numerator of:

H_{S}(x, y, z) = x^{m} + r_{1}x^{m−1} + … + r_{m−1}x + r_{m}

where (k ∈ {1, …, n}):

kr_{k}(y, z) = −S_{k} − S_{k−1}r_{1} − … − S_{1}r_{k−1}

and every S_{j}(y, z) is the coefficient of t_{1}^{−1}t_{2}^{−1} in the Laurent polynomial:

\frac{(f(t_{1}, t_{2}))^{j}Jac(t_{1}, t_{2})}{t_{1}^{n_{1}}t_{2}^{n_{2}}} · ∑_{k=0}^{jn}(−1)^{k} · ∑_{α_{1}+α_{2}=k} (\frac{Q_{1}(t_{1}, t_{2}) − y}{t_{1}^{n_{1}}} )^{α_{1}}(\frac{Q_{2}(t_{1}, t_{2}) − z}{t_{2}^{n_{2}}} )^{α_{2}}

where Jac(t_{1}, t_{2}) is tha Jacobian Determinant of g(t_{1}, t_{2}) and h(t_{1}, t_{2}).

Example 4.3 The method presented in theorem 4.2 is used to determine the implicit equation of the surface parametrized by:

x = t_{1}^{2} + t_{2}^{2} y = t_{1}^{3} + t_{2}^{2} z = t_{2}^{3} + t_{1}^{2}

In this particular case the equation H_{S} has the following structure:

H_{S}(x, y, z) = x^{9} + ∑_{i=1}^{9} r_{i}(y, z)x^{9−i}

The computation of the r_{i}(y, z)’s is performed by computing the Newton Sums of order 9, S_{j}(y, z) (j ∈ {1, …, 9}). For that, first it is computed the Jacobian Determinant of g and h:

Jac(t_{1}, t_{2}) = t_{1}t_{2}(9t_{1}t_{2} − 4)

and the Laurent polynomials (j ∈ {1, …, 9}):

\frac{(9t_{1}t_{2} − 4)(t_{1}^{2} + t_{2}^{2})^{j}}{t_{1}^{2}t_{2}^{2}} · ∑_{k=0}^{2j}(−1)^{k} ∑_{i=0}^{k} (\frac{t_{2}^{2} − y}{t_{1}^{3}} )^{i}(\frac{t_{1}^{2} − z}{t_{2}^{3}} )^{k−i}

whose coefficient in t_{1}^{−1}t_{2}^{−1} is S_{j}(y, z). In this way the following results are obtained:

S_{1}(y) = 0
S_{2}(y) = 10
S_{3}(y) = 9x^{2} − 42z − 42y + 9y^{2}
S_{4}(y) = 36x^{2} − 24y + 192yz − 24z + 30 + 36y^{2}
S_{5}(y) = 210x^{2} + 10 − 180yx^{2} − 240z − 240y + 120yz + 210y^{2} − 180y^{2}z
S_{6}(y) = −612y^{2}z + 9x^{4} + 630y^{2} + 100 + 9y^{4} − 612yx^{2} + 2160yz − 480x^{3} − 480y^{3}
−228z + 180y^{2}x^{2} + 630x^{2} − 228y
S_{7}(y) = 1428y^{3}z + 70 + 2037y^{2} + 1428yx^{3} − 6300yx^{2} + 2037x^{2} − 6300y^{2}z
+2184yz + 756y^{2}x^{2} − 812y^{3} − 1190y − 812x^{3} + 315x^{4} − 1190z + 315y^{4}
S_{8}(y) = 350 − 1008y^{3}x^{2} − 1504y + 5488y^{2} + 1172x^{4} + 5488x^{2} − 1504z − 7872y^{3}
−1008y^{4}z − 1008y^{2}x^{3} + 1172y^{4} + 7712yx^{3} + 7712y^{3}z + 20160y^{2}x^{2}
−7872x^{3} − 1008yx^{4} − 13872y^{2}z − 13872yx^{2} + 15680yz
S_{9}(y) = −5598z − 5598y + 14499y^{4} − 15036x^{3} + 14499x^{4} + 360 − 15036y^{3} + 14967y^{2}
+14967x^{2} + 21024yz + 9y^{6} − 1800y^{5} + 52164yx^{3} − 77616y^{2}z
−25884y^{2}x^{3} + 52164y^{3}z − 1800x^{5} − 5274yx^{4} − 25884y^{3}x^{2} + 49680y^{2}x^{2}
+756x^{4}y^{2} + 756x^{2}y^{4} − 5274y^{4}z + 9x^{6} − 77616yx^{2}

Newton Identities allow to conclude that the implicit equation of S is:

−2y^{4} − 2z^{4} − 96x^{2}yz^{2} − 24x^{2}yz − 21x^{3}y^{2}z^{2} + 44xy^{3}z + 18xy^{2}z^{3} + 60x^{3}y^{2}z + 60x^{3}yz^{2}
+76x^{3}yz + 18xy^{4}z + 24xy^{2}z − 54x^{2}y^{2}z^{2} − 60x^{2}y^{3}z − 96x^{2}y^{2}z − 60x^{2}yz^{3} + 78xy^{2}z^{2}
+18xy^{3}z^{2} + 18xyz^{4} + 3x^{3}z^{4} + 38x^{3}y^{2} − 22x^{4}y − 24x^{4}yz − 22x^{4}z + 36x^{4}y^{2}z
−9x^{5}y^{2} + 36x^{4}yz^{2} + 6x^{5}y + 14x^{6}y − 9x^{5}z^{2} − 48x^{5}yz − 3x^{6}y^{2} − 3x^{6}z^{2} + 14x^{6}z − 12x^{2}y^{2}
+44xyz^{3} − 12x^{2}z^{2} + 38x^{3}y^{3} − 18x^{2}z^{4} − 18x^{2}y^{4} − 28x^{2}z^{3} + 8x^{3}y + 8x^{3}z + 38x^{3}z^{2}
+38x^{3}z^{3} + 3x^{3}y^{4} + 24xyz^{2} + 5xz^{4} + 8xy^{3} + 8xz^{3} + x^{9} − 5x^{7} + 5x^{5} − 2x^{4} − y^{6} + 2y^{5}
−2y^{4}z − 16y^{2}z^{3} − 8y^{3}z − z^{6} + 2z^{5} − 2yz^{4} + 5xy^{4} − 8yz^{3} − 16y^{3}z^{2} − 12y^{2}z^{2} − 3z^{4}y^{2}
−27x^{4}y^{2} − 27x^{4}z^{2} − 28x^{2}y^{3} + 6x^{5}z − 3z^{2}y^{4}

Theorem 4.2 can be extended directly to the case of surfaces with a rational parametrization with the following structure:

\begin{matrix}x = & f(t_{1}, t_{2}) \\ y = & \frac{t_{1}^{n_{1}} + Q_{1}(t_{1}, t_{2})}{D_{1}(t_{1}, t_{2})} \\ z = & \frac{t_{2}^{n_{2}} + Q_{2}(t_{1}, t_{2})}{D_{2}(t_{1}, t_{2})} \end{matrix}

where Q_{1}, D_{1}, Q_{2} and D_{2} are polynomials in Q[t_{1}, t_{2}] such that the total degrees of Q_{1} and D_{1} (resp. Q_{2} and D_{2}) are smaller than n_{1} (resp. n_{2}).

5 Conclusions

A new family of algorithms computing the implicit equation of parametric plane curves and space surfaces has been presented. These algorithms do not precise of the computation of symbolic determinants or Grobner Basis and they are mainly based on the computation of Newton Sums on the solution set of a polynomial ideal by means of either an expansion of a rational function in negative powers of the parameter in the case of plane curves or in the determination of a well precised coefficient of a Laurent polynomial in the case of surfaces.

A first implementation of these algorithms has been accomplished in the Computer Algebra System Maple and the first results obtained are quite good. Next steps concerning their study will regard the following questions:

• to generalize the algorithm in section 4.2 to a more general class of parametric surfaces: a first step in this direction could be the using of the results in [CDS94] to get formulae with the same type than in theorem 2.5 for polynomial systems of equations without solutions at infinity and a second possibility could be the using of infinitesimals (as in [MC92]).

• the most comsuming time in the algorithms in sections 3 and 4 is clearly the computation of the Laurent polynomials providing the desired Newton Sums: optimizations of this step are required in order to apply these algorithms to the implicitization of parametric hypersurfaces in C^{n} with n ≥ 4.

• to study the behaviour of these algorithms for parametric surfaces with base points, but first experiences show that such points only provide some well precised extraneous factor.

References

[AGR94] C. Alonso, J. Gutiérrez and T. Recio: An implicitization algorithm with fewer variables. To appear in Computer Aided Geometric Design (1994).

[CDS94] E. Cattani, A. Dickenstein and B. Sturmfels: Computing multidimensional residues. To appear in the proceedings of the conference MEGA-94, Birkhäuser (1995).

[CLO93] D. Cox, J. Little and D. O’Shea: Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics, Springer-Verlag (1993).

[DST87] J. H. Davenport, Y. Siret and E. Tournier: Calcul Formel: Systémes et algorithmes de manipulation algebriques. Masson París (1987).

[DT87] R. Dvornicich and C. Traverso: Newton symmetric functions and the arithmetic of algebraically closed fields. Proc. AAECC–5, Lecture Notes in Computer Science 356, 216–224 (1989).

[GC92] X.-S. Gao and S.-C. Chou: Implicitization of rational parametric equations. Journal of Symbolic Computation, 14, 459–470 (1992).

[GV89] L. González-Vega: La sucesión de Sturm-Habicht y sus aplicaciones al Algebra Computacional. Doctoral Thesis, University of Cantabria (1989).

[GLV88] M. Giusti, D. Lazard and A. Valibouze: Algebraic transformations of polynomial equations, symmetric polynomials and elimination. Proc. ISSAC–88, Lecture Notes in Computer Science 358, 309–314 (1989).

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

[K91] M. Kalkbrener: Implicitization of rational parametric curves and surfaces. Proc. AAECC–8, Lecture Notes in Computer Science 508, 249–259 (1990).

[L84] A. Lascoux: La résultant de deux polynômes. Seminaire d’Algebre M. P. Malliavin, 1984–1985.

[L82] R. Loos: Generalized polynomial remainder sequences. Computer Algebra, ed. B. Buchberger, G.E. Collins and R. Loos, 115–138. Computing Suplementum 4, Springer Verlag, NY (1982).

[M93] A. M. Mandache: Applications of Polynomial Systems Solving in Geometric Modelling and Robotics: An Annotated Bibliography. Technical Report RISC-Linz (1993).

[MC92] D. Manocha and J. Canny: Multipolynomial resultants and linear algebra. Proceedings ISSAC-92, 158–167, ACM Press (1992).

[S93] B. Sturmfels: Algorithms in Invariant Theory. Text and Monographs in Symbolic Computation, 1, Springer-Verlag (1993).

[T92] A. K. Tsikh: Multidimensional Residues and Their Applications. Translations of Mathematical Monographs, 103, American Mathematical Society (1992).

[V87] A. Valibouze: Fonctions symetriques et changements de bases. Proc. EUROCAL–87, Lecture Notes in Computer Science 378, 323–332 (1989).

[V88] A. Valibouze: Manipulations de fonctions symetriques. Doctoral Thesis, University of Paris 6 (1988).