Implicitization by Gröbner basis conversion

Michael Kalkbrener Department of Mathematics Swiss Federal Institute of Technology CH-8092 Zurich, Switzerland

1 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}, …, p_{n}/q_{n}) ∈ K(y_{1}, …, y_{m})^{n}, K a field, compute a finite basis of the prime ideal

P := {f ∈ K[x_{1}, …, x_{n}] | f(p_{1}/q_{1}, …, p_{n}/q_{n}) = 0}.

If q_{1} = … = q_{n} = 1, i.e. the given parametrization is polynomial, P is the elimination ideal I ∩ K[x_{1}, …, x_{n}] of the ideal I generated by {x_{1} − p_{1}, …, x_{n} − p_{n}} in K[x_{1}, …, x_{n}, y_{1}, …, y_{m}]. In the general case of rational parametrizations the situation is slightly more complicated: P is the elimination ideal J ∩ K[x_{1}, …, x_{n}], where J is the ideal generated by {q_{1}x_{1} − p_{1}, …, q_{n}x_{n} − p_{n}, (∏_{i=1}^{n} q_{i})z − 1} in the polynomial ring K[x_{1}, …, x_{n}, y_{1}, …, y_{m}, z]. Hence, in both cases standard elimination techniques like resultants, Gröbner 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ö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. Therefore [Hoffmann 1989] suggested to apply Gröbner basis conversion to the implicitization problem. 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.

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öbner basis of {x_{1} − p_{1}, …, x_{n} − p_{n}} with respect to an elimination order for {x_{1}, …, x_{n}}, i.e. an order ≺ with X ≺ Y for every power product X in x_{1}, …, x_{n} and every power product Y in y_{1}, …, y_{m}. In general this is very time-consuming. Note that {x_{1} − p_{1}, …, x_{n} − p_{n}} is already a Gröbner basis with respect to any elimination order for {y_{1}, …, 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_{1}x_{1} − p_{1}, …, q_{n}x_{n} − p_{n}, (∏_{i=1}^{n} q_{i})z − 1} is usually not a Gröbner basis but “close” to Gröbner bases with respect to elimination orders for {y_{1}, …, y_{m}}. Therefore we expect that also in the general case the conversion strategy works well.

In [Faugè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öbner fan [Mora, Robbiano 1988] of the given ideal.

Assume that the Hilbert-Poincaré series of a homogeneous ideal I is known. This may happen if I is given by a regular sequence or a Gröbner basis. In [Gianni et al. 1993] it is shown how the knowledge of the Hilbert-Poincaré series can be used to speed up Gröbner 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è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.

2 Notations

Throughout this paper let K be a field. The ideal generated by a subset F of the polynomial ring K[x_{1}, …, x_{n}] is denoted by ⟨F ⟩ and the set of power products in x_{1}, …, x_{n} by P P (x_{1}, …, x_{n}). For subsets U, V of P P (x_{1}, …, x_{n}) we define

U · V := {uv | u ∈ U, v ∈ V }.

Let ≺ be an arbitrary admissible order on P P (x_{1}, …, x_{n}). For any non-zero polynomial f ∈ K[x_{1}, …, x_{n}] we denote its leading power product by lpp_{≺}(f) and its total degree in x_{1}, …, x_{n} by deg(f). By convention, lpp_{≺}(0) := 0 and deg(0) := −1. For an ideal I in K[x_{1}, …, x_{n}] we denote the ideal ⟨{lpp_{≺}(f) | f ∈ I}⟩ by I_{≺}.

Let ≪ be an admissible order on P P (x_{1}, …, x_{n}, y_{1}, …, y_{m}). We call ≪ an elimination order for {x_{1}, …, x_{n}} if there exist admissible orders ≪_{1} on P P (x_{1}, …, x_{n}) and ≪_{2} on P P (y_{1}, …, y_{m}) such that for every u_{1}, u_{2} ∈ P P (x_{1}, …, x_{n}) and v_{1}, v_{2} ∈ P P (y_{1}, …, y_{m})

u_{1}v_{1} ≪ u_{2}v_{2} iff v_{1} ≪_{2} v_{2} or (v_{1} = v_{2} and u_{1} ≪_{1} u_{2}).

3 Basis conversion for zero-dimensional ideals

The algorithm in [Faugère et al. 1993] is based on Lemma 1 and the following simple formula. Let I be an ideal in K[x_{1}, …, x_{n}], G a reduced Gröbner basis of I with respect to an arbitrary admissible order, c_{1} …, c_{m} ∈ K and f_{1}, …, f_{m} ∈ K[x_{1}, …, x_{n}]. Then

∑_{j=1}^{m} c_{j}f_{j} ∈ I iff ∑_{j=1}^{m} c_{j}h_{j} = 0,  (1)

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 (1) is that it allows us to test ideal membership incrementally using linear dependence tests.

Lemma 1 Let ≺ be an arbitrary admissible order on P P (x_{1}, …, x_{n}) and I a zerodimensional ideal in K[x_{1}, …, x_{n}]. Then the set P P (x_{1}, …, x_{n}) \ {lpp(f) | f ∈ I \ {0}} is finite.

We now sketch the algorithm. Let < and ≺ be two arbitrary admissible orders on P P (x_{1}, …, x_{n}), I a zero-dimensional ideal in K[x_{1}, …, x_{n}] and F a Gröbner basis of I with respect to <. We assume that F is given and we want to compute the reduced Gröbner basis G of I with respect to ≺. Denote the first power products in M_{1} := P P (x_{1}, …, x_{n}) with respect to ≺ by u_{1} ≺ u_{2} ≺ u_{3} ≺ … Let k be the smallest natural number such that there exists a non-zero polynomial in I which depends on u_{1}, …, u_{k} only. Note that Lemma 1 implies the existence of k. We can compute k using formula (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}, …, c_{k−1} ∈ K with

h_{k} + ∑_{j=1}^{k−1} c_{j}h_{j} = 0.

Furthermore, g_{1} := u_{k} + ∑_{j=1}^{k−1} c_{j}u_{j} is the polynomial in I. Now define

M_{2} := P P (x_{1}, …, x_{n}) \ ({u_{1}, …, u_{k−1}} ∪ ({u_{k}} · P P (x_{1}, …, x_{n})))

and let v_{1} ≺ v_{2} ≺ v_{3} ≺ … be the first power products in M_{2} with respect to ≺. Compute the smallest natural number l such that there exists a polynomial g_{2} in I which depends on u_{1}, …, u_{k−1}, v_{1}, …, v_{l} only. Define

M_{3} := P P (x_{1}, …, x_{n}) \ ({u_{1}, …, u_{k−1}, v_{1}, …, v_{l−1}} ∪ ({u_{k}, v_{l}} · P P (x_{1}, …, 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}, …, g_{i−1}} is the reduced Gröbner basis of I with respect to ≺.

A formalization of this strategy and a complexity analysis can be found in [Faugère et al. 1993] (see also [Hoffmann 1989]). Practical experience shows that using the FGLMalgorithm is generally much faster than is constructing Gröbner bases with respect to elimination orders directly.

4 The Gröbner walk: basis conversion for arbitrary ideals

Let Q denote the rational numbers and ω = (ω_{1}, …, ω_{n}) be an element of the set of weight vectors

Ω^{n} := {(ψ_{1}, …, ψ_{n}) ∈ Q^{n} | ψ_{i} ≥ 0 for every i ∈ {1, …, n}}.

For a power product u = x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} in P P (x_{1}, …, x_{n}) we define its ω-degree by

deg_{ω}(u) := ∑_{j=1}^{n} i_{j}ω_{j}.

The ω-degree of a non-zero polynomial f, abbreviated deg_{ω}(f), is the maximum of the ωdegrees of the power products which occur in f with non-zero coefficients and deg_{ω}(0) := −1. A polynomial f is called ω-homogeneous if all power products in f have the same ω-degree. Note that for ω = (1, …, 1) this notion coincides with standard homogeneity. Obviously, every polynomial f ≠ 0 can be written in the form f = in_{ω}(f) + f′, where in_{ω}(f) is ω-homogeneous and deg_{ω}(in_{ω}(f)) > deg_{ω}(f′). Furthermore, in_{ω}(0) := 0. For the admissible order ≺ and the weight vector ω we define the admissible order _{ω}≺ on P P (x_{1}, …, x_{n}) by

u_{1} _{ω}≺ u_{2} if deg_{ω}(u_{1}) < deg_{ω}(u_{2}) or (deg_{ω}(u_{1}) = deg_{ω}(u_{2}) and u_{1} ≺ u_{2}).

We recall the concept of the Gröbner fan. A subset Q of Q^{n} is called a polyhedral set if Q is the intersection of a finite number of closed halfspaces or Q = Q^{n}. The Gröbner cone of an ideal I ⊆ K[x_{1}, …, x_{n}] with respect to the admissible order ≺ is defined by

cone(≺) := cl({ω ∈ Ω^{n} | {in_{ω}(f) | f ∈ I} generates I_{≺}}),

where cl denotes the usual topological closure in Q^{n}. This notation is justified by the following result (see Theorem 2.7 in [Mora, Robbiano 1988]).

Theorem 1 Let ≺ be an admissible order. Then cone(≺) is a convex polyhedral cone in Q^{n} with a non-empty interior.

We call the set F (I) := {cone(≺) | ≺ an admissible order} the Gröbner fan of I. For a proof of the following result, see Lemma 2.6 in [Mora, Robbiano 1988].

Theorem 2 The Gröbner fan of I has finite cardinality.

Let < and ≪ be two admissible orders and G = {g_{1}, …, g_{r}} the reduced Gröbner basis of I with respect to <. It is easy to show (see Lemma 4.3 in [Collart et al. 1994]) that

cone(<) = cone(≪) iff lpp_{<}(g_{i}) = lpp_{≪}(g_{i}) for every i ∈ {1, …, r}.  (2)

As a consequence we obtain that

cone(<) = cone(≪) implies G = H,

where G is the reduced Gröbner basis of I with respect to < and H is the reduced Gröbner basis of I with respect to ≪. Hence, we can speak about the reduced Gröbner basis of I over cone(<).

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

The basic idea is the following: we move on the line segment

\overline{στ} := \{(1 − a)σ + aτ | 0 ≤ a ≤ 1\}

from σ to τ. Whenever we leave a Gröbner cone C and enter a new cone C′ we transform the reduced Gröbner basis over C into the reduced Gröbner basis over C′. After finitely many conversions we arrive at cone(≪) and obtain the reduced Gröbner basis w.r.t. ≪.

More precisely, let ω be the weight vector with

\overline{σω} = \overline{στ} ∩ cone(<).

ω can be easily computed from σ, τ and G using linear algebra techniques. It can be shown that if τ ≠ ω there exists an ω′ ∈ \overline{ωτ} with ω ≠ ω′ and \overline{ωω′} ⊆ cone(_{ω}≪). Therefore after leaving cone(<) we enter cone(_{ω}≪) and we now have to transform the reduced Gröbner basis G over cone(<) into a Gröbner basis F over cone(_{ω}≪). This can be done in the following way. First of all it is easy to prove that {in_{ω}(g) | g ∈ G} is a basis of ⟨{in_{ω}(f) | f ∈ I}⟩. Using Buchberger’s algorithm we can compute the reduced Gröbner basis {m_{1}, …, m_{s}} of ⟨{in_{ω}(f) | f ∈ I}⟩ with respect to _{ω}≪. In the course of this Gröbner basis computation ω-homogeneous polynomials h_{i1}, …, h_{ir} can be constructed with

m_{i} = ∑_{j=1}^{r} h_{ij}in_{ω}(g_{j}) and deg_{ω}(m_{i}) = deg_{ω}(h_{ij}in_{ω}(g_{j})) for j ∈ {1, …, r} with h_{ij} ≠ 0.

Replacing in_{ω}(g_{j}) by g_{j} we obtain

f_{i} := ∑_{j=1}^{r} h_{ij}g_{j} and F := {f_{1}, …, f_{s}}.

It is shown in [Collart et al. 1994] that F is a Gröbner basis of I with respect to _{ω}≪. Using (2) as termination condition we obtain a Gröbner basis w.r.t. ≪ after finitely many basis conversions.

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

5 Basis conversion for homogeneous ideals using Hilbert functions

Let I be a homogeneous ideal in K[x_{1}, …, x_{n}], G := {g_{1}, …, g_{s}} a basis of I and ≺ an admissible order on P P (x_{1}, …, x_{n}).

Assume that we know the Hilbert function HF_{I} of I. This may happen, for instance, if G is a Gröbner basis with respect to an arbitrary order or g_{1}, …, g_{s} is a regular sequence. Compute the Hilbert function HF_{J} of the monomial ideal J := ⟨{lpp_{≺}(g_{1}), …, lpp_{≺}(g_{s})}⟩. If HF_{I} = HF_{J} then G is a Gröbner basis of I w.r.t ≺. 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

(1) G contains all the elements of degree < m of a Gröbner basis of I and

(2) a Gröbner basis of I contains k further elements of degree m. With this information we can perform the Gröbner bases algorithm, but with the following modification:

(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),

(2) precisely k critical pairs of degree m are useful. When we have found k useful critical pairs of degree m, giving rise to new elements g_{s+1}, …, g_{s+k} in the Gröbner basis, we recompute the new Hilbert function, and proceed in the algorithm. For efficiently computing Hilbert functions resp. Hilbert-Poincaré series, consult [Bigatti et al. 1991].

6 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}, …, p_{n}) ∈ K[y_{1}, …, y_{m}]^{n}

is given. Then P := {f ∈ K[x_{1}, …, x_{n}] | f(p_{1}, …, p_{n}) = 0} is the elimination ideal I ∩ K[x_{1}, …, x_{n}], where I := ⟨{x_{1}−p_{1}, …, x_{n}−p_{n}}⟩. Note that G := {x_{1}−p_{1}, …, x_{n}−p_{n}} is already a Gröbner basis with respect to any elimination order for {y_{1}, …, 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}, …, 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 P P (x_{1}, …, x_{n}) w.r.t. a total degree order ≺ by u_{1} ≺ u_{2} ≺ u_{3} ≺ … and test linear dependence between the normal forms of the u_{j} modulo the Gröbner 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öbner walk algorithm: since G is a Gröbner basis with respect to any elimination order for {y_{1}, …, y_{m}} the Gröbner walk algorithm can be used for successively transforming G into a Gröbner basis with respect to an elimination order for {x_{1}, …, x_{n}}.

Assume that the p_{i} are homogeneous of degree d_{i}. We can make x_{1} − p_{1}, …, x_{n} − p_{n} homogeneous by giving weight d_{i} to variable x_{i}. Since the sequence x_{1} − p_{1}, …, x_{n} − p_{n} is regular we already know that the Poincaré series of K[x_{1}, …, x_{n}, y_{1}, …, y_{m}]/I is

∏(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.

If the given parametrization

(p_{1}/q_{1}, …, p_{n}/q_{n}) ∈ K(y_{1}, …, y_{m})^{n}

is not polynomial but rational the situation is slightly more complicated: the ideal P := {f ∈ K[x_{1}, …, x_{n}] | f(p_{1}/q_{1}, …, p_{n}/q_{n}) = 0} is the elimination ideal J ∩ K[x_{1}, …, x_{n}], where J is the ideal generated by {q_{1}x_{1} −p_{1}, …, q_{n}x_{n} −p_{n}, (∏_{i=1}^{n} q_{i})z −1} in the polynomial ring K[x_{1}, …, x_{n}, y_{1}, …, y_{m}, z]. The set G := {q_{1}x_{1}−p_{1}, …, q_{n}x_{n}−p_{n}, (∏_{i=1}^{n} q_{i})z− 1} is usually not a Gröbner basis. Hence before we can apply the FGLM-algorithm or the Gröbner walk we have to compute a Gröbner basis G′ of P with respect to an arbitrary order. In general, elimination orders for {y_{1}, …, 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

(∏_{i=1}^{n} q_{i})z − 1, q_{1}x_{1} − p_{1}, …, q_{n}x_{n} − p_{n}.

It is easy to see that the homogenized sequence is regular. Therefore we know the Poincaré series of K[x_{1}, …, x_{n}, y_{1}, …, y_{m}, z]/J′, where J′ is the ideal generated by the homogenized sequence, and we proceed as in the case of polynomial parametrizations.

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öbner 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.

References

[Arnon, Sederberg 1984] Arnon, D.S.; Sederberg, T.W.: Implicit equation for a parametric surface by Gröbner basis. Proc. 1984 MACSYMA User’s Conference, 431–436, General Electric, Schenectady, New York (1984). [Bigatti et al. 1991] Bigatti, A.M.; Caboara, M.; Robbiano L.: On the computation of Hilbert-Poincaré series. Applicable Algebra in Engineering, Communication and Computing 2, 21–33 (1991).

[Buchberger 1987] Buchberger, B.: Applications of Gröbner bases in non-linear computational geometry. Proc. Workshop on Scientific Software, 59–88, IMA, Minneapolis, USA (1987).

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

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

[Faugère et al. 1993] Faugère, J.C.; Gianni, P.; Lazard, D.; Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation 16, 329–344 (1993).

[Gao, Chou 1991] Gao, X.S.; Chou S.C.: Computations with parametric equations. Proc. ISSAC’91, 122–127 (1991).

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

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

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

[Kalkbrener 1990] Kalkbrener, M.: Implicitization of rational curves and surfaces. Proc. AAECC-8, 249–259, Tokyo, Japan (1990).

[Manocha, Canny 1992] Manocha, D.; Canny, J.F.: Implicit representation of parametric surfaces. Journal of Symbolic Computation 13, 485–510 (1992).

[Licciardi, Mora 1994] Licciardi, S.; Mora, T.: Implicitization of hypersurfaces and curves by the Primbasissatz and basis conversion. Proc. ISSAC’94, 191–196 (1994).

[Mora, Robbiano 1988] Mora, T.; Robbiano, L.: The Gröbner fan of an ideal. Journal of Symbolic Computation 6, 183–208 (1988).

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

[Robbiano 1985] Robbiano, L.: Term orderings on the polynomial ring. Proc. EUROCAL’85, 513–517 (1985).

[Sederberg et al. 1984] Sederberg, T.W.; Anderson, D.C.; Goldman, R.N.: Implicit representation of parametric curves and surfaces. Computer Vision, Graphics, and Image Processing 28, 72–84 (1984).