Implicitization by Gröbner basis conversion

Michael Kalkbrener Department of Mathematics Swiss Federal Institute of Technology CH-8092 Zurich, Switzerland mkalk@math.ethz.ch

Abstract

The problem of converting parametrically defined varieties into their implicit form is of great importance in geometric modeling. It essentially is an elimination problem and therefore techniques like resultants, Gröbner bases or characteristic sets can be applied. Gröbner 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öbner bases algorithm is often very time-consuming.

In this talk we present an alternative approach: implicitization by Gröbner basis conversion. The idea underlying Gröbner basis conversion is the following. It is well-known that the computing time of a Gröbner basis computation heavily depends on the chosen order. Instead of computing a Gröbner basis G_{1} with respect to a “slow” order directly we could compute a Gröbner 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.

We present three conversion algorithms. The FGLM-algorithm solves the conversion problem by linear algebra techniques. In the Gröbner walk algorithm the conversion is done in several steps following a path in the Gröbner fan of the given ideal. The third algorithm uses the knowledge of the Hilbert-Poincaré series of an ideal I to speed up Gröbner bases computations for I.

Gröbner basis conversion is well applicable to the implicitization problem since the parametric equations form “almost” a Gröbner basis. We investigate how these three conversion algorithms can be applied.

keywords: rational parametric varieties, implicitization, Gröbner basis, basis conversion.