.

APPLICATIONS OF GRÖBNER BASES IN NON-LINEAR COMPUTATIONAL GEOMETRY

BRUNO BUCHBERGER^{1}

Abstract

Gröbner bases are certain finite sets of multivariate polynomials. Many problems in polynomial ideal theory (algebraic geometry, non-linear computational geometry) can be solved by easy algorithms after transforming the polynomial sets involved in the specification of the problems into Gröbner basis form. In this paper we give some examples of applying the Gröbner bases method to problems in non-linear computational geometry (inverse kinematics in robot programming, collision detection for superellipsoids, implicitization of parametric representations of curves and surfaces, inversion problem for parametric representations, automated geometrical theorem proving, primary decomposition of implicitly defined geometrical objects). The paper starts with a brief summary of the Gröbner bases method.

1 Introduction

Traditionally, computational geometry deals with geometrical and combinatorial problems on linear objects and simple non-linear objects, see for example (Preparata, Shamos 1985). These methods are not appropriate for recent advanced problems arising in geometrical modeling, computer-aided design, and robot programming, which are more algebraic in nature and involve non-linear geometrical objects. Real and complex algebraic geometry is the natural framework for most of these non-linear problems. Unfortunately, in the past decades, algebraic geometry was very little concerned with the algorithmic solution of problems. Rather, non-constructive proofs of certain geometrical phenomena and mere existence proofs for certain geometrical objects was, and still is, the main emphasis.

The method of Gröbner bases is an algorithmic method that can be used to attack a wide range of problems in commutative algebra (polynomial ideal theory) and (complex) algebraic geometry. It is based on the concept of Gröbner bases and on an algorithm for constructing Gröbner bases introduced in (Buchberger 1965, 1970). In recent years the method has been refined and analyzed and more applications have been studied. (Buchberger 1985) is a tutorial and survey on the Gröbner bases method.

1RISC-LINZ (Research Institute for Symbolic Computation) Johannes Kepler University, A4040 Linz, Austria. This research is supported by a grant from VOEST-ALPINE, Linz, (Dipl. Ing. H.

Exner), and a grant from SIEMENS, München, (Dr. H. Schwärtzel)

The present paper starts with a brief summary of the basic concepts and results of Gröbner bases theory ( Section 2). If the reader accepts these basic concepts and results as black boxes, the main part of the paper is self-contained. The internal details of the black boxes together with extensive references to the literature are given in the tutorial (Buchberger 1985).

The main part of the paper explains various applications of the Gröbner bases method for problems in non-linear computational geometry as motivated by advanced applications in computer-aided design, geometrical modeling and robot programming. The sequence for the presentation of these applications is quite random. Each of them relies on one or several of the basic properties of Gröbner bases summarized in Section 2.

2 Summary of the Gröbner Bases Method

The reader who is interested only in the applications may skip this section and come back in case he needs a specific notation, concept or theorem.

2.1 General Notation

N set of natural numbers including zero Q set of rational numbers R set of real numbers C set of complex numbers K typed variable for arbitrary fields \overline{K} algebraic closure of K i, j, k, l, m, n typed variables for natural numbers K[x_{1}, …, x_{n}] ring of n-variate polynomials

over the coefficient field K

K(x_{1}, …, x_{n}) field of n-variate rational rational expressions

over the coefficient field K

a, b, c, d typed variables for elements in coefficient fields f, g, h, p, q typed variables for polynomials s, t, u typed variables for power products,

i. e. polynomials of the form x_{1}^{i_{1}} … x_{n}^{i_{n}}

C(f, u) the coefficient at power product u in polynomial f F, G typed variables for finite sets of polynomials H typed variable for finite sequences of polynomials Ideal(F) the ideal generated by F,

i. e. the set {∑_{i} h_{i}.f_{i} | h_{i} ∈ K[x_{1}, …, x_{n}], f_{i} ∈ F }

Radical(F) the radical of the ideal generated by F, i. e. {f | f vanishes on all common zeros of F } or, equivalently, {f | f^{k} ∈ Ideal(F) for some k}

f ≡_{F} g f is congruent to g modulo Ideal(F) K[x_{1}, …, x_{n}]/Ideal(F) the residue class ring modulo Ideal(F) [f]_{F} the residue class of f modulo Ideal(F)

In the definition of Ideal(F), it is sometimes necessary to explicitly indicate the polynomial ring from which the h_{i} are taken. If the polynomial ring is not clear from the context, we will use an index:

Ideal_{K[x_{1},...,x_{n}]}(F)

In the definition of Radical(F), by a common zero of the polynomials in F we mean a common zero in the algebraic closure of the coefficient field.

2.2 Polynomial Reduction

The basic notion of Gröbner bases theory is polynomial reduction. The notion of polynomial reduction depends on a linear ordering on the set of power products that can be extended to a partial ordering on the set of polynomials. The set of “admissible orderings” that can be used for this purpose can be characterized by two easy axioms. The lexical ordering and the total degree ordering are the two admissible orderings used most often in examples. These two orderings are completely specified by fixing a linear ordering on the set of indeterminates x_{1}, …, x_{n} in the polynomial ring. Roughly, f reduces to g modulo F iff g results from f by subtracting a suitable multiple a.u.h of a polynomial h ∈ F such that g is lower in the admissible ordering than f. Reduction may be conceived as a generalization of the subtraction step that appears in univariate polynomial division. For all details, see (Buchberger 1985). We use the following notation:

≻ typed variable for admissible orderings LP(f) leading power product of f (w. r. t. ≻) LC(f) leading coefficient of f (w. r. t. ≻) MLP(F) the set of “multiples of leading powerproducts in F ”,

i. e. {u | (∃f ∈ F)(u is a multiple of LP(f)}

f →_{F} g f reduces to g modulo F →_{F}^{∗} reflexive-transitive closure of →_{F} ↔_{F}^{∗} reflexive-symmetric-transitive closure of →_{F} \underline{f}_{F} f is in normal form modulo F, i. e.

there does not exist any g such that f →_{F} g

A binary relation → on a set M is called “noetherian” iff there does not exist any infinite sequence x_{1} → x_{2} → x_{3} → … of elements x_{i} in M.

Lemma 2.2.1 (Basic Properties of Reduction) (Noetherianity)

For all F: →_{F} is noetherian. (Reduction Closure = Congruence)

For all F: ≡_{F} =↔_{F}^{∗}. (Normal Form Algorithm)

There exists an algorithm NF (“Normal Form”) such that for all F, g:

(NF1) g →_{F}^{∗} NF(F, g),

(NF2) \underline{NF(F, g)}_{F}. (Cofactor Algorithm)

There exists an algorithm COF (“cofactors”) such that for all F, g:

COF(F, g) is a sequence H of polynomials indexed by F satisfying g = NF(F, g) + ∑_{f∈F} H_{f}.f.

Note that, for fixed F, f, there may exist many different g such that f →_{F}^{∗} g and \underline{g}_{F} i. e. , in general, “normal forms for polynomials f are not unique modulo F ”. A normal form algorithm NF, by successive reduction steps, singles out one of these g for each F and f.

COF proceeds by “collecting” the multiples a.u.h of polynomials h ∈ F that are subtracted in the reduction steps when applying the normal form algorithm NF to g. Actually, COF can be required to satisfy additional properties, for examples, certain restrictions on the leading power products of the polynomials H_{f}.f.

2.3 Gröbner Bases and the Main Theorem

Definition 2.3.1 (Buchberger 1965, 1970) F is a Gröbner basis (w. r. t. ≻) iff

“normal forms modulo F are unique”, i.e.

for all f, g_{1}, g_{2}:

if f →_{F}^{∗} g_{1}, f →_{F}^{∗} g_{2}, \underline{g_{1}}_{F} , \underline{g_{2}}_{F}, then g_{1} = g_{2}.

Note that →_{F} depends on the underlying admissible ordering ≻ on the power products. Therefore, also the definition of Gröbner basis depends on the underlying ≻. Whenever ≻ is clear from the context, we will not explicitly mention ≻. Gröbner bases whose polynomials are monic (i. e. have leading coefficient 1) and are in normalform modulo the remaining polynomials in the basis are called “reduced Gröbner bases”. As we will see, Gröbner bases have a number of useful properties that establish easy algorithms for important problems in polynomial ideal theory. Therefore the main question is how Gröbner bases can be algorithmically constructed. The algorithm needs the concept of “S-polynomials”. The S- polynomial of two polynomials f and g is the difference of certain multiples u.f and v.g. For details see (Buchberger 1985). We use the notation

SP(f, g) the S-polynomial of f and g.

Theorem 2.3.1 (Main Theorem, Buchberger 1965, 1970) (Algorithmic Characterization of Gröbner Bases)

F is a Gröbner basis iff

for all f, g ∈ F : NF(F, SP(f, g)) = 0. (Algorithmic Construction of Gröbner Bases)

There exists an algorithm GB such that for all F (GB1) Ideal(F) = Ideal(GB(F)) (GB2) GB(F) is a (reduced) Gröbner basis.

The proof of the (Algorithmic Characterization) is completely combinatorial and quite involved. The whole power of the Gröbner bases method is contained in this proof. The algorithm GB is based on the (Algorithmic Characterization), i. e. it involves successive computation of normal forms of S-polynomials. This algorithm is structurally simple. However, it is complex in terms of time and space consumed. In some sense, this is necessarily so because the problems that can be solved by the Gröbner bases method are intrinsically complex as has been shown by various authors. Still, the algorithm allows to tackle interesting and non-trivial practical problems for which no feasible solutions were known by other methods. Also, various theoretical and practical improvements of the algorithm have enhanced the scope of applicability.

2.4 The Gröbner Bases Algorithm in Software Systems

The Gröbner bases algorithm GB is available in almost all major computer algebra systems, notably in the SAC-2, SCRATCHPAD II, REDUCE, MAPLE, MACSYMA and muMATH systems. The introduction of (Buchberger, Collins, Loos 1982) contains the addresses of institutions from which these systems can be obtained. In these systems at least the algorithms SP, NF, (COF,) and GB are accessible to the user. In most systems, also a number of other auxiliary routines and variants of these basic algorithms are available and the user can experiment with different coefficient domains, admissible orderings and strategies for tuning the algorithms.

The implementations vary drastically in their efficiency mostly because of the varying amount of theory that has been taken into account. Also, computation time and space depends drastically on the admissible orderings used, on permutations of variables, on treating indeterminates as ring or field variables, on strategies for selecting pairs in the consideration of S-polynomials and on many other factors. Thus if one seriously considers solving problems of the type described in this paper one should try different systems and various orderings, strategies etc.

The rest of the paper is written with the goal in mind that the reader should be able to apply the methods as soon as he has access to an implementation of the basic algorithms NF, COF, SP, and GB viewed as “black boxes”.

2.5 Properties of Gröbner Bases

In the following theorem we summarize the most important properties of Gröbner bases on which the algorithmic solution of many fundamental problems in polynomial ideal theory (algebraic geometry, non-linear computational geometry) can be based. Actually, not all of these properties are used in the later sections of the paper. However, since the results on Gröbner bases are quite scattered in the literature, the summary may help the reader who perhaps wants to try the Gröbner bases method on new problems. Many of the properties listed in the theorem were already proven in (Buchberger 1965, 1970). Actually the problems that can be solved with the (Residue Class Ring) properties were the starting point for Gröbner bases theory in (Buchberger 1965). The property (Elimination Ideals) is due to (Trinks 1978). The property (Inverse Mappings) is a recent contribution by (Van den Essen 1986) that solves a decision problem that has been open since 1939. (Algebraic Relations) and (Syzygies) seem to have been known already to (Spear 1977). However, it is hard to trace were the proofs appeared for the first time. More references are given in (Buchberger 1985). Most of the proofs of the properties below are immediate consequences of the definition of Gröbner bases, the property (Reduction Closure = Congruence), and some well known algebraic lemmas in polynomial ideal theory. The proofs of the properties (Syzygies) and (Inverse Mappings) are more involved. The existence of the algorithm GB based on the above Main Theorem is the crux for the algorithmic character of the properties.

In the following, let K[x_{1}, …, x_{n}] be arbitrary but fixed. F and G are used as typed variables for finite subsets of K[x_{1}, …, x_{n}]. If not otherwise stated, ≻ is arbitrary. When we say “y is a new indeterminate” we mean that y is different from x_{1}, …, x_{n}. By “F is solvable” we mean that there exists an n-tuple (a_{1}, …, a_{n}) of elements a_{i} in the algebraic closure \overline{K} such that f(a_{1}, …, a_{n}) = 0 for all f ∈ F. Similarly, the expression “F has finitely many solutions” and similar expressions always refer to solutions over the algebraic closure of K.

Theorem 2.5.1 (General Properties of Gröbner Bases) (Ideal Equality, Uniqueness of Reduced Gröbner Bases)

For all F, G: Ideal(F) = Ideal(G) iff GB(F) = GB(G). (Idempotency of GB)

For all reduced Gröbner bases G: GB(G) = G. (Ideal Membership)

For all F, f: f ∈ Ideal(F) iff NF(GB(F), f) = 0. (Canonical Simplification)

For all F, f, g: f ≡_{F} g iff NF(GB(F), f) = NF(GB(F), g). (Radical Membership)

For all F, f:

f ∈ Radical(F) iff 1 ∈ GB(F ∪ {y.f − 1}), (where y is a new indeterminate). (Computation in Residue Class Rings)

For all F:

The residue class ring K[x_{1}, …, x_{n}]/Ideal(F) is isomorphic to the algebraic structure whose carrier set is \{f | \underline{f}_{F} \} and whose addition and multiplication operations, ⊕ and ⊗, are defined as follows:

f ⊕ g := NF(GB(F), f + g),

f ⊗ g := NF(GB(F), f.g).

(Note that the carrier set is a decidable set and ⊕ and ⊗ are computable!). (Residue Class Ring, Vector Space Basis)

For all F:

The set {[u]_{F} | u ∉ MLP(GB(F))} is a linearly independent basis for K[x_{1}, …, x_{n}]/Ideal(F) considered as a vector space over K.

(Residue Class Ring, Structure Constants)

For all F, u, v:

if u, v ∉ MLP(GB(F)), then [u]_{F} .[v]_{F} = ∑_{w∉MLP(GB(F))} a_{w}.[w]_{F},

where, for all w, a_{w} := C(NF(GB(F), u.v), w).

(The a_{w} ∈ K, appearing in these representations of products of the basis elements as linear combinations of the basis elements are the “structure constants” of K[x_{1}, …, x_{n}]/Ideal(F) considered as an associative algebra.)

(Leading Power Products)

For all F: MLP(Ideal(F)) = MLP(GB(F)).

(Principal Ideal)

For all F:

Ideal(F) is principal (i. e. has a one-element ideal basis) iff GB(F) has exactly one element.

(Trivial Ideal)

For all F: Ideal(F) = K[x_{1}, …, x_{n}] iff GB(F) = {1}.

(Solvability of Polynomial Equations)

For all F: F is solvable iff 1 ∉ GB(F).

(Finite Solvability of Polynomial Equations)

For all F:

F has only finitely many solutions iff for all 1 ≤ i ≤ n there exists an f ∈ GB(F) such that

LP(f) is a power of x_{i}.

(Number of Solutions of Polynomial Equations)

For all F with finitely many solutions:

the number of solutions of F (with multiplicities and solutions at infinity) = = cardinality of {u | u ∉ MLP(GB(F))}.

(Minimal Polynomial)

For all F and all finite sets U of power products: There exists an f ∈ Ideal(F) in which only power products from U occur iff {NF(GB(F, u)) | u ∈ U} is linearly dependent over K.

(By applying this property successively to the powers 1, x_{i}, x_{i}^{2}, x_{i}^{3}, … one can algorithmically find, for example, the univariate polynomial in x_{i} of minimal degree in Ideal(F) if it exists. On this algorithm a general method for solving arbitrary system of polynomial equations can be based, see (Buchberger 1970), which works for arbitrary ≻ whereas the elimination method mentioned below works only for lexical orderings.)

(Syzygies)

Let F be a (reduced) Gröebner basis and define for all f, g ∈ F:

P^{(f,g)} := COF(F, SP(f, g)), u and v such that SP(f, g) = u.f − v.g, S^{(f,g)} is a sequence of polynomials indexed by F, S_{f}^{(f,g)} := u − P_{f}^{(f,g)}, S_{g}^{(f,g)} := −v − P_{g}^{(f,g)}, S_{h}^{(f,g)} := −P_{h}^{(f,g)}, for all h ∈ F − {f, g}.

Then,

{S^{(f,g)} | f, g ∈ F } is a set of generators for the K[x_{1}, …, x_{n}]-module of all sequences H of polynomials (indexed by F) that are solutions (“syzygies”) of the linear diophantine equation

∑_{h∈F} H_{h}.h = 0.

(This solution method for linear diophantine equations over K[x_{1}, …, x_{n}] whose coefficients form a Gröbner basis F can be easily extended to the case of arbitrary F and to systems of linear diophantine equations, see (Buchberger 1985), (Winkler 1986)).

Theorem 2.5.2 (Properties of Gröbner Bases for Particular Orderings)

(Hilbert Function)

Let ≻ be a total degree ordering. Then, for all F:

The value H(d, F) of the Hilbert function for d and F, i. e. the number of modulo Ideal(F) linearly independent polynomials in K[x_{1}, …, x_{n}]of degree ≤ d, is equal to

( n^{d+n}) - cardinality of {u of degree ≤ d | u ∉ MLP(GB(F))}.

(Elimination Ideals, Solution of Polynomial Equations)

Let ≻ be the lexical ordering defined by x_{1} ≺ x_{2} ≺ … ≺ x_{1}. Then, for all F, 1 ≤ i ≤ n:

The set GB(F) ∩ K[x_{1}, …, x_{i}]) is a (reduced) Gröbner basis for the “i-th elimination ideal” generated by F, i. e. for Ideal_{K[x_{1},...,x_{n}]}(F)∩K[x_{1}, …, x_{i}].

(This property leads immediately to a general solution method, by “successive substitution”, for arbitrary systems of polynomial equations with finitely many solutions, which is formally described in (Buchberger 1985). We will demonstrate this method in the examples in the application section of this paper.)

(Continuation of Partial Solutions)

Let ≻ be a lexical ordering. For all F:

If F := {f_{1}, …, f_{k}} is a Gröbner basis with respect to ≻, f_{1} ≺ ⋯ ≺ f_{k}, and f_{1}, …, f_{l}(1 ≤ l ≤ k) are exactly those polynomials in F that depend only on the indeterminates x_{1}, …, x_{i}, then every common solution (a_{1}, …, a_{i}) of {f_{1}, …, f_{l}} can be continued to a common solution (a_{1}, …, a_{n}) of F. (For a correct statement of this property some terminology about solutions at infinity would be necessary.)

(Independent Variables Modulo an Ideal)

For all F and 1 < i_{1} < … < i_{m} < n:

The indeterminates x_{i_{1}}, …, x_{i_{m}} are independent modulo Ideal(F) (i. e. there is no polynomial in Ideal(F) that depends only on x_{i_{1}}, …, x_{i_{m}}) iff GB(F) ∩K[x_{i_{1}}, …, x_{i_{m}}] = {0}, where the ≻ used must be a lexical ordering satisfying x_{i_{1}} ≺ ⋯ ≺ x_{i_{m}} ≺ all other indeterminates. (This property yields immediately an algorithm for determining the dimension of a polynomial ideal (algebraic variety).)

(Ideal Intersection)

Let ≻ be the lexical ordering defined by x_{1} ≺ x_{2} ≺ … ≺ x_{n} ≺ y, y a new variable. Then, for all F, G:

GB({y.f | f ∈ F } ∪ {(y − 1).g | g ∈ G}) ∩ K[x_{1}, …, x_{n}] is a (reduced) Gröbner basis for Ideal(F) ∩ Ideal(G).

(This property yields also an algorithm for quotients of finitely generated ideals because the determination of such quotients can be reduced to the determination of intersections.)

(Algebraic Relations)

For all F:

Let F = {f_{1}, …, f_{m}}, let y_{1}, …, y_{m} be new indeterminates and let ≻ be the lexical ordering defined by y_{1} ≺ … ≺ y_{m} ≺ x_{1} ≺ … ≺ x_{n}. Then, GB({y_{1} − f_{1}, …, y_{m} − f_{m}}) ∩ K[y_{1}, …, y_{m}] is a (reduced) Gröbner basis for the “ideal of algebraic relations” over F, i. e. for the set {g ∈ K[y_{1}, …, y_{m}] | g(f_{1}, …, f_{m}) = 0}.

(Inverse Mapping)

For all F:

Let F = {f_{1}, …, f_{n}}, let y_{1}, …, y_{n} be new indeterminates and let ≻ be the lexical ordering defined by y_{1} ≺ … ≺ y_{n} ≺ x_{1} ≺ … ≺ x_{n}. Then, the mapping from \overline{K}^{n} into \overline{K}^{n} defined by F is bijective iff GB(\{y_{1}−f_{1}, …, y_{n}− f_{n}}) has the form {x_{1} − g_{1}, …, x_{1} − g_{n}} for certain g_{j} ∈ K[y_{1}, …, y_{n}].

The properties stated in the above theorem can be read as the algorithmic solution of certain problems specified by polynomial sets F. Each of these ”algorithms” requires that, for solving the problem for an arbitrary F, one first transforms F into the corresponding (reduced) Gröbner basis GB(F) and then performs some algorithmic actions on GB(F). For example, for the decision problem “f ≡_{F} g?”, (Canonical Simplification) requires that one first transforms F into GB(F) and then checks, by applying algorithm NF, whether or not the normal forms of f and g are identical modulo GB(F). Actually, most of the above properties (algorithms) are correct also if, instead of transforming F into a corresponding reduced Gröbner basis, one transforms F into an arbitrary equivalent Gröbner basis G. (We say “F is equivalent to G” iff Ideal(F) = Ideal(G).) In practice, however, this makes very little difference because the computation of Gröbner bases is not significantly easier if one relaxes the requirement that the Gröbner basis must be reduced.

Alternatively, by (Idempotency of GB), the properties stated in the above theorem can also be read as properties of (reduced) Gröbner bases — and algorithms for solving problems for (reduced) Gröbner bases. For example, introducing the additional assumption that F is a (reduced) Gröbner basis, (Canonical Simplification) reads as follows:

For all (reduced) Gröbner bases F, and polynomials f, g: f ≡_{F} g iff NF(F, f) = NF(F, g).

Some of the properties stated in the above theorem are characteristic for Gröbner bases, i. e. if the property holds for a set F then F is a Gröbner basis. For example, (Leading Power Products) is a characteristic property, i. e. if MLP(Ideal(F)) = MLP(F) then F is a Gröbner basis.

Let us carry through one more exercise for reading the above properties as algorithms. For deciding whether

(Question)

for all a_{1}, …, a_{n} ∈ \overline{K}, for which f_{1}(a_{1}, …, a_{n}) = ⋯ = f_{m}(a_{1}, …, a_{n}) = 0, also g(a_{1}, …, a_{n}) = 0, i. e. for deciding whether g ∈ Radical({f_{1}, …, f_{m}}), because of (Radical Membership), it suffices to perform the following steps:

1. Compute the (reduced) Gröbner basis G for {f_{1}, …, f_{m}, y.g − 1}), where y is a new indeterminate.

2. The (Question) has a positive answer iff 1 ∈ G.

3 Application: Inverse Robot Kinematics

The problem of inverse robot kinematics is the problem of determining, for a given robot, the distances at the prismatic joints and the angles at the revolute joints that will result in a given position and orientation of the end-effector. The mathematical description of this problem leads to a system of multivariate polynomial equations (after representing angles α by their sine and cosine and adding sin^{2} α + cos^{2} α = 1 to the set of equations), see (Paul 1981).

Let us consider, for example, the following robot having two revolute joints (two “degrees of freedom”).

We introduce the following variables:

l_{1}, l_{2} lengths of the two robot arms px, py, pz x-, y−, and z-coordinate of the position of the end-effector ϕ, θ, ψ Euler angles of the orientation of the end effector

(Euler angles are one way of describing orientation)

δ_{1}, δ_{2} angles describing rotation at the revolute joints

We introduce the sines and cosines of the angles occuring in the above description as separate variables: s_{1}, c_{1} sine and cosine of δ_{1} s_{2}, c_{2} sine and cosine of δ_{2} sf, cf sine and cosine of ϕ st, ct sine and cosine of θ sp, cp sine and cosine of ψ

The interrelation of the physical entities described by the above variables is expressed in the following system of equations:

c_{1} · c_{2} − cf · ct · cp + sf · sp = 0, s_{1} · c_{2} − sf · ct · cp − cf · sp = 0, s_{2} + st · cp = 0, −c_{1} · s_{2} − cf · ct · sp + sf · cp = 0, −s_{1} · s_{2} + sf · ct · sp − cf · cp = 0, c_{2} − st · sp = 0, s_{1} − cf · st = 0, −c_{1} − sf · st = 0, ct = 0, l_{2} · c_{1} · c_{2} − px = 0, l_{2} · s_{1} · c_{2} − py = 0, l_{2} · s_{2} + l_{1} − pz = 0, c_{1}^{2} + s_{1}^{2} − 1 = 0, c_{2}^{2} + s_{2}^{2} − 1 = 0, cf^{2} + sf^{2} − 1 = 0, ct^{2} + st^{2} − 1 = 0, cp^{2} + sp^{2} − 1 = 0.

Let us call those variables that describe the geometrical realization of the robot “geometrical variables” (for example, the variables l_{1}, l_{2}). Let us also call those variables that describe position and orientation of the end-effector shortly “position variables” (px, …, sf, cf, …). The other variables (s_{1}, c_{1}, …) are the “joint variables”.

In the case of more complicated robots (with six degrees of freedom), one can specify values for the geometrical variables and the position variables and, with certain restrictions, will always be able to determine appropriate values of the joint variables that yield the given position and orientation of the end-effector. In the above example robot, with only two degrees of freedom however one can only independently choose the value of two position variables, for example px and pz. The value of all the other variables, notably of the other position variables py, sf, cf, …, and the joint variables will then be determined by the above system of algebraic equations.

The problem can be considered in three different versions of increasing generality.

(Real Time Version)

• The value of the geometrical variables are numerically given.

• The value of those position variables that can be independently chosen (e. g. px, pz) are numerically given.

• The solution of the problem consists in determining appropriate numerical values for the (remaining position variables and) the joint variables.

(Off-Line Version, Concrete Robot)

• The value of the geometrical variables are numerically given.

• The value of those position variables that can be independently chosen are left open as parameters.

• By a ”solution of the problem”, in this version, one means symbolic expressions involving the position parameters that describe, in “closed form”, the dependence of the (remaining position variables and) the joint variables from the position parameters. Of course, a “symbolic closed form solution” of this kind will not always be possible. It is possible for certain classes of robots, see (Paul 1981), and it is possible in a modified sense also in the general case by using Gröbner bases.

(Off-Line Version, Robot Class)

• The value of the geometrical variables are left open as parameters.

• The value of those position variables that can be independently chosen are left open as parameters.

• By a ”solution of the problem”, in this version, one means symbolic expressions involving the geometrical and the position parameters that describe, in “closed form”, the dependence of the (remaining position variables and) the joint variables on the geometrical and position parameters.. A “symbolic closed form solution” in this general sense is even more difficult. Again, it is possible for certain classes of robots and, as we shall see, it is possible in a modified sense also in the general case by using Gröbner bases.

A symbolic solution of the inverse kinematics problem in the (Off-Line Version), can be contrasted to a numerical approach:

(Symbolic Approach)

• Derivation of the symbolic expressions for the solution of the problem in the (Off-Line Version).

• Numerical specification of the parameters.

• Numerical evaluation of the symbolic expressions using the numerical values of the parameters.

(Numerical Approach)

• Numerical specification of the parameters.

• Solution of the problem in the (Real-Time Version) by numerical iteration methods.

It is clear that a symbolic solution of the problem in the (Off-Line Version) can have practical advantages over the purely numerical approach (as long as the resulting symbolic expressions describing the solutions are not too complicated) because the numerical evaluation of the symbolic solution expressions in real-time situations may be faster than a direct iterative numerical solution of the (Real Time Version) of the problem. Also, of course, the symbolic solution may give “insight” into the problem that can not be gained by a numerical solution.

For the above example, we show the solution of the problem in the (Off-Line Version, Roboter Class) by using Gröbner bases. In this version, the geometrical variables l_{1}, l_{2} and the position variables px, pz are considered as symbolic parameters.

The solution method uses property (Elimination Ideals) of Gröbner bases. This property, read as an algorithm, tells us that we first have to compute the Gröbner bases of the set F of input polynomials. Since l_{1}, l_{2}, px, pz are to be treated as symbolic parameters, we work over the field Q(l_{1}, l_{2}, px, pz) as coefficient field. This is perfectly possible, because the Gröbner bases method works over arbitrary fields (whose arithmetic is algorithmic). Furthermore, we must specify an ordering on the remaining variables, for example c_{1} ≺ c_{2} ≺ s_{1} ≺ s_{2} ≺ py ≺ cf ≺ ct ≺ cp ≺ sf ≺ st ≺ sp. These variables are treated as ring variables, i.e. the Gröbner basis will be computed considering the input polynomials as polynomials in the ring Q(l_{1}, l_{2}, px, pz)[c_{1}, …, sp]. The resulting Gröbner basis has the following form:

c_{1}^{2} + \frac{px^{2}}{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}} = 0,

c_{2} + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{l_{2}} · px · c_{1} = 0, s_{1}^{2} − \frac{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}} = 0, s_{2} − \frac{pz−l_{1}}{l_{2}} = 0, py + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{px} · c_{1} · s_{1} = 0, cf^{2} − \frac{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}} = 0, ct = 0, cp + \frac{pz^{3}−3·l_{1}·pz^{2}−l_{2}^{2}·pz+3·l_{1}^{2}·pz+l_{1}·l_{2}^{2}−l_{1}^{3}}{l_{2}·pz^{2}−2·l_{1}·l_{2}·pz+l_{2}·px^{2}−l_{2}^{3}+l_{1}^{2}·l_{2}} · s_{1} · cf = 0,

sf + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}} · c_{1} · s_{1} · cf = 0,

st + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}} · s_{1} · cf = 0,

sp + \frac{pz^{4}−4·l_{1}·pz^{3}−2·l_{2}^{2}·pz^{2}+6·l_{1}^{2}·pz^{2}+4·l_{1}·l_{2}^{2}·pz−4·l_{1}^{3}·pz+l_{2}^{4}−2·l_{1}^{2}·l_{2}^{2}+l_{1}^{4}}{l_{2}·px·pz^{2}−2·l_{1}·l_{2}·px·pz+l_{2}·px^{3}−l_{2}^{3}·px+l_{1}^{2}·l_{2}·px} · c_{1} · s_{1} · cf = 0.

The above Gröbner basis has a remarkable structure:

• The geometrical parameters l_{1} and l_{2} and the position parameters px and pz are still available as symmbolic parameters in the polynomials of the Gröbner basis. Thus, the system is still “general”. The Gröbner basis is in “closed form”.

• In accordance with property (Elimination Ideals), the system is “triangularized”. In this example, this means that the first polynomial of the basis depends only on c_{1}, the second on c_{1}, c2, the third on c_{1}, c_{2}, s_{1}, . . .. After substitution of numerical values for the parameters l_{1}, l_{2}, px, pz, we can therefore numerically determine the possible values for c_{1} from the first equation then, for each of the values of c_{1}, determine the value of c_{2} from the second equation then, for each of the values of c_{1}, c_{2}, determine the value of s_{1} from the third equation etc.

• Actually, the degrees of the polynomials in this basis are quite low. This is in general not true for the first polynomial in Gröbner bases. The first polynomial, which, in case the solution set is finite, is always univariate, tends to have quite a high degree in general. The degrees of the other polynomials, however, tend to be very low (most times even linear) also in the general case because the polynomial sets describing realistic physical or geometrical situations often define prime ideals, for which linearity in the second, third … variable can be proven theoretically. This phenomenon needs closer study, however. For numerical practice, low degrees in the second, third … variable implies that numerical errors from the determination of the value of the first value will not drastically accumulate. In the case where the second, third … equation is linear, the Gröbner basis has the form {p_{1}(x_{1}), x_{2} − p_{2}(x_{1}), …, x_{n} − p_{n}(x_{1})}. In this case, the errors introduced by the numerical solution of p_{1} will not accumulate at all.

• The above method of numerical backward substitution based on the Gröbner basis, by property (Elimination Ideals), is guaranteed to yield all (real and complex) solutions of the system.

• Again by (Elimination Ideals), no “extraneous” solutions of the system are produced. (Other algebraic methods, for example the resultant method, may produce extraneous solutions.)

The above Gröbner basis was produced in 62 sec on an IBM 4341 using an implementation of the Gröbner basis method by R. Gebauer and H. Kredel in the SAC-2 computer algebra system. The computation time is increasing drastically when more complicated robot types are investigated. We are far from being able to treat the most general robot of six degrees of freedom. However, so far, only very little research effort has been dedicated to this possible application of Gröbner bases. Using the special structure of the problem it may well be that more theoretical results can be derived that allow to drastically speed up the general algorithm in this particular application.

4 Application: Intersection of Superellipsoids

Superellipsoids (Barr 1981) are surfaces in 3D space that have a compact implicit representation as the set of points (x, y, z) such that

((\frac{x}{a})^{2/ϵ_{3}} + (\frac{y}{b})^{2/ϵ_{2}})^{ϵ_{3}/ϵ_{1}} + (\frac{z}{c})^{2/ϵ_{1}} − 1 = 0

Superellipsoids are topologically equivalent to spheres. They can be considered as ellipsoids with axes a, b, c whose curvature in the x−, y−, z− directions is distorted by the influence of the exponents ϵ_{1}, ϵ_{2}, ϵ_{3}. (The above equation is the implicit equation for the case where the superellipsoid is in standard position with its midpoint at the origin.) The exponents ϵ_{1}, ϵ_{2}, ϵ_{3} open an enormous flexibility for adjusting the shape of superellipsoids in order to approximate real objects. Some basic problems in geometric modeling, for example, the problem of deciding whether a point is inside or outside an object can be easily solved for superellipsoids. Recently, superellipsoids have been proposed for approximating parts of robots and obstacles in order to test for collision. The collision detection problem of robots is thereby reduced to an intersection test for superellipsoids.

Unfortunately, for general superellipsoids, no good intersection tests are known. In this section we report on first attempts to apply Gröbner bases for this question. We restrict our attention to the case of a sphere (with midpoint (A, B, C) and radius R) and a superellipsoid (in standard position) whose exponents satisfy ϵ_{1} = ϵ_{2} = ϵ_{3} < 2 (a convex superellipsoid). In this case, the two objects intersect iff the minimal distance between the midpoint of the sphere and the superellipsoid is less or equal to the radius of the sphere. Using Lagrange factors, this approach leads to the following system of equations for the coordinates (x, y, z) of the point on the superellipsoid having minimal distance to (A, B, C):

(Equations for Minimal Distance)

(\frac{x}{a})^{2/ϵ} + (\frac{y}{b})^{2/ϵ} + (\frac{z}{c})^{2/ϵ} − 1 = 0 (x − A) + λ.\frac{1}{ϵ.a}.(\frac{x}{a})^{(2/ϵ−1)} = 0 (y − B) + λ.\frac{1}{ϵ.b}.(\frac{y}{b})^{(2/ϵ−1)} = 0 (z − C) + λ.\frac{1}{ϵ.c}.(\frac{z}{c})^{(2/ϵ−1)} = 0

If ϵ is of the form 1/k (which is sufficiently general for practical purposes), this (System for Minimal Distance) is an algebraic system. We consider a, b, c,A, B, C as parameters, i. e. we work over K(a, b, c, A, B, C)[x, y, z, λ]. For computing the Gröbner bases, we use the lexical ordering defined by x ≺ y ≺ z ≺ λ. For ϵ = 1 (which is, actually, the ellipsoid case) we get the Gröbner basis

(Gröbner Basis for Minimal Distance)

x^{6} − p(x) = 0

y − q(x) = 0

z − r(x) = 0

λ − s(x) = 0.

Here, p(x), q(x), r(x), s(x) are univariate polynomials in x of degree 5 with coefficients that are rational expressions in the parameters a, b, c, A, B, C. The equation for λ is not interesting for the problem at hand and may be dropped. The printout of these rational expressions consumes approximately 2 pages. (Some simplification by extracting common subexpressions would be possible.) Again, the Gröbner basis has all the advantageous features described in the inverse kinematics application. Note in particular that, in this Gröbner basis, the second, third and fourth equations are linear in the variables y, z, λ, respectively. Therefore the Gröbner basis presents an explicit symbolic solution to the problem as soon as the solution value for x is numerically determined from the first equation, which is univariate in x.

If we change ϵ to 1/2, the resulting Gröbner basis will again have the structure displayed in (Gröbner Basis for Minimal Distance). The only difference is that the degree of the univariate polynomials p(x), q(x), r(x), s(x) will be 11. We conjecture that the structure of the system will stay unchanged for arbitrary ϵ of the form 1/k.

The problem with this approach is, again, computation time. While the Gröbner basis computation for ϵ = 1 needs 15 minutes (on an IBM 4341 in the SAC-2 implementation of the Gröbner bases method), the computation already needs 19 hours for ϵ = 1/2. At the moment, this excludes practical applicability of the method. However, one should take into account that the source of complexity seems to be the extraneous extremal solutions that enter through the Lagrange factor method. Actually, the first equation in the Gröbner basis describes the x-coordinate of all relative extremal points on the surface and not only the x-coordinates of the minimal point. This raises the degree of the first polynomial and, hence, also of the other polynomials. More systematic study is necessary. Furthermore, it seems to be possible to guess and subsequently prove the general structure of the polynomials p(x), q(x), r(x), s(x) from the Gröbner bases computations for two or three different ϵ values. This could make the Gröbner basis computation superfluous in the future. As with other symbolic computation methods, Gröbner bases computations can be applied on very different levels including the level of producing and supporting mathematical conjectures.

5 Application: Implicitization of Parametric Objects

As has been pointed out repeatedly, the automatic transition between implicit and parametric representation of curves and surfaces is of fundamental importance in geometric modeling, see for example (Sederberg, Anderson 1984). The reason for this is that the implicit and the parametric representation are appropriate for different classes of problems. For example, for generating points along curves or surfaces, the parametric representation is most convenient whereas, for deciding whether a given point lies on a specific curve or surface, the implicit representation is most natural. It is also well known that implicitization of parametric surfaces is of importance for deriving a representation of the intersection curve of two surfaces. This problem has a satisfactory solution in case one of the surfaces is expressed parametrically and the other implicitly. In this case, the parameter representation x(s, t), y(s, t), z(s, t) for the first surface can be substituted into the implicit equation f(x, y, z) of the other surface. This results in the implicit representation f(x(s, t), y(s, t), z(s, t)) of the intersection curve in parameter space.

Actually, for some time, the problem of implicitization has been deemed unsolvable in the CAD literature. (Sederberg, Anderson 1984), however, presented a solution of the implicitization problem using resultants. The solution is spelled out for surfaces in 3D and curves in 2D. In the general case of (n − 1)-dimensional hypersurfaces, I guess, the method could yield implicit equations that introduce non-trivial extraneous solutions, see also the remarks in (Arnon, Sederberg 1984). In (Arnon, Sederberg 1984) it is shown how Gröbner bases can be used for the general implicitization problem of (n−1)-dimensional hypersurfaces. The authors sketch a correctness proof for the method that relies on (Algebraic Relations). In this section, we review their method and generalize it to the most general case of hypersurfaces of arbitrary dimension in n-dimensional space. Still, much research will be needed to assess the efficiencies of the methods and to determine their range of practical applicability. Also some theoretical details are not yet completely covered in the literature.

(General Implicitization Problem)

Given: p_{1}, …, p_{m} ∈ K[x_{1}, …, x_{n}].

Find: f_{1}, …, f_{k} ∈ K[y_{1}, …, y_{m}],

such that for all a_{1}, …, a_{m}:

f_{1}(a_{1}, …, a_{m}) = ⋯ = f_{k}(a_{1}, …, a_{m}) = 0 iff
a_{1} = p_{1}(b_{1}, …, b_{n}), …, a_{m} = p_{m}(b_{1}, …, b_{n}) for some b_{1}, …, b_{n}.

The problem requires to construct k polynomials implicitly defining hypersurfaces whose intersection is the hypersurface described by the parameter representation.

(Implicitization Algorithm)

{f_{1}, …, f_{k}} := GB({y_{1} − p_{1}, …, y_{m} − p_{m}}) ∩ K[y_{1}, …, y_{m}], where GB has to be computed using the lexical ordering determined by y_{1} ≺ ⋯ ≺ y_{m} ≺ x_{1} ≺ ⋯ ≺ x_{n}.

Correctness Proof: Let g_{1} ≺ … ≺ g_{l} be the polynomials in

GB({y_{1} − p_{1}, …, y_{m} − p_{m}}) − K[y_{1}, …, y_{m}].

{y_{1} − p_{1}, …, y_{m} − p_{m}} and the Gröbner basis {f_{1}, …, f_{k}, g_{1}, …, g_{l}} have the same common zeros. If

f_{1}(a_{1}, …, a_{m}) = ⋯ = f_{k}(a_{1}, …, a_{m}) = 0

then, by (Continuation of Partial Solutions), there exist (b_{1}, …, b_{n}) such that

g_{1}(a_{1}, …, a_{m}, b_{1}, …, b_{n}) = ⋯ = g_{l}(a_{1}, …, a_{m}, b_{1}, …, b_{n}) = 0.

Hence, also

a_{1} − p_{1}(b_{1}, …, b_{n}) = 0, …, a_{1} − p_{1}(b_{1}, …, b_{n}) = 0.

The converse is clear.

Example: Let us consider the 3D surface defined by the following parametric representation

(Parametric Representation)

x = r.t

y = r.t^{2}

z = r^{2}

Roughly, this surface has the shape of a ship hull whose keel is the y-axis and whose bug is the z-axis. Applying algorithm GB to {x − r.t, y − r.t^{2}, z − r^{2}} with respect to the ordering z ≺ y ≺ x ≺ t ≺ r yields the following Gröbner basis:

(Gröbner Basis)

x^{4} − y^{2}.z

t.x − y

t.y.z − x^{3}

t^{2}.z − x^{2}

r.y − x^{2}

r.x − t.z

r.t − x

r^{2} − z

The polynomial depending only on x, y, z is an implicit equation for the surface defined by (Parameter Representation).

By close inspection one will detect that, actually, the implicit equation occurring in the above (Gröbner Basis) does not strictly meet the specification of the (Implicitization Problem). The y-axis is a solution to the implicit equation whereas it does not appear in the surface defined by the (Parameter Representation). This is not a deficiency of the Gröbner basis method but has to do with the particular (Parameter Representation) which, in some sense, is not “general enough” or, stated differently, in the (Continuation of Partial Solutions) property, solutions at infinity have to be taken into account. This question deserves some further detailed study. (Sturmfels 1987) has already sketched some analysis of this phenomenon. He proposes the following parameter presentation, which includes the y-axis and whose implicit equation is again x^{4} − y^{2}.z.

(Parametric Representation)

x = u.v

y = v^{2}

z = u^{4}

This example was computed in 4 sec on an IBM AT in the author’s research implementation of the Gröbner basis method in the muMATH system. Other examples with more complicated coefficients and similar degree characteristics had computing times in the range of several seconds. I guess that the examples occuring in practice should be well tractible by the method.

Example: The method can also be used for rational parametric representations. We consider the example of a circle in the plane.

(Rational Parametric Representation)

x = \frac{1−s^{2}}{1+s^{2}}

y = \frac{2.s}{1+s^{2}}

In the case of rational parametric representations, we first clear denominators. In the example, the input to GB should therefore be {x + x.s^{2} − 1 + s^{2}, y + y.s^{2} − 2.s}. The result is, of course, x^{2} + y^{2} − 1.

6 Application: Inversion of Parametric Representations

The inversion problem for parametric representations is defined as follows:

(Inversion Problem for Parametric Representations)

Given: p_{1}, …, p_{m} ∈ K[x_{1}, …, x_{n}] and a point (a_{1}, …, a_{m}) on the hypersurface

parametrically defined by p_{1}, …, p_{m}.

Find: {(b_{1}, …, b_{n}) | a_{1} = p_{1}(b_{1}, …, b_{n}), …, a_{m} = p_{m}(b_{1}, …, b_{n})}.

This problem is closely connected with the (Implicitization Problem). In fact, the (Inversion Problem) is just a special case of the general problem of solving systems of polynomial equations, which is completely solved by the Gröbner basis method based on the (Elimination Ideals) property or based on the (Minimal Polynomial) property. For solving the (Inversion Problem), the general Gröbner bases solution method can be applied to the system {y_{1} − p_{1}(x_{1}, …, x_{n}), …, y_{m} − p_{m}(x_{1}, …, x_{n})}, i. e. we have the following algorithm.

(Inversion Algorithm for Parametric Representations)

G := GB({y_{1} − p_{1}(x_{1}, …, x_{n}), …, y_{m} − p_{m}(x_{1}, …, x_{n})}, where GB has to be computed using the lexical ordering determined by y_{1} ≺ ⋯ ≺ y_{m} ≺ x_{1} ≺ ⋯ ≺ x_{n}.

{f_{1}, …, f_{k}} := G ∩ K[y_{1}, …, y_{m}]. (If, for some 1 ≤ i ≤ k, f_{i}(a_{1}, …, a_{m}) ≠ 0, then “Input Error”.) Substitute a_{i} for y_{i} in G and solve the system G, which is “triangularized”.

In fact, the steps necessary in this algorithm include the steps of the (Implicitization Algorithm). Therefore, when we apply the Gröbner bases method to the (Implicitization Problem), we automatically get also a solution for the (Inversion Problem) and vice versa.

Example: We use again the example of Section 5.

(Parametric Representation)

x = r.t y = r.t^{2} z = r^{2}

Suppose we want to determine the parameter values defining the point (2, 2, 4) on the surface. Application of GB yields

(Gröbner Basis)

x^{4} − y^{2}.z t.x − y t.y.z − x^{3} t^{2}.z − x^{2} r.y − x^{2} r.x − t.z rt − x r^{2} − z

The first polynomial is the implicit equation, which can be used to check whether (2, 2, 4) is, in fact, on the surface: 2^{4} − 2^{2}.4 = 0. Substituting (2, 2, 4) in the second, third, and fourth polynomial of the Gröbner basis (and making all polynomials monic) yields the system

(Gröbner Basis After First Substitution)

t − 1 t − 1 t^{2} − 1

This system of univariate polynomials, by the property (Continuation of Partial Solutions) must always have a common zero that can be determined by forming the greatest common divisor, g := t − 1, of the three polynomials and solving for t. This leads to t = 1.

Substituting (2, 2, 4, 1) in the fifth, …,eights polynomial of the Gröbner basis (and making all polynomials monic) yields the system r − 2 r − 2 r − 2 r^{2} − 4

Again, this system of univariate polynomials, by the property (Continuation of Partial Solutions) must have a common zero that can be determined by forming the greatest common divisor, h := r − 2, of the four polynomials and solving for r. This leads to r = 2.

Actually, it has been shown recently in (Kalkbrener 1987) and, independently, in (Gianni 1987) that the computation of greatest common divisors is not necessary in the above procedure. Rather, as can be verified in the above example, for each of the univariate systems the first non-zero polynomial will always be the greatest common divisor of the system. This is a drastic simplification of the general procedure for solving arbitrary systems of polynomial equations by the Gröbner bases method.

7 Application: Detection of Singularities

In tracing implicitly given planar curves, numerical methods work well except when tracing curves through singular points, see (Hofmann 1987). (Hofmann 1987a) has pointed out that Göbner bases yield an immediate approach to detect all singular points of implicitly given planar curves. The singular points of a planar curve given by f(x, y) = 0 are exactly the points (a, b) that are common zeros of f, f_{x}, and f_{y}. Hence, the problem of determining the set S of singular points of a planar curve f can be treated by the following algorithm.

(Algorithm for Detection of Singularities)

G := GB({f, f_{x}, f_{y}}), where f_{x}, f_{y} are the partial derivatives of f w. r. t. x and y respectively and GB has to be computed w. r. t. a lexical ordering of x, y.

S := set of common zeros of G determined by the successive substitution method.

Example: Let us consider the following planar curve

[figure: x; y; 1]

This curve has 9 singular points. We detect them by applying GB to {f, f_{x}, f_{y}}, where (Four Circle Curve)

f := (x^{2} + y^{2} − 1).((x − 1)^{2} + y^{2} − 1)((x + 1)^{2} + y^{2} − 1)(x^{2} + (y − 1)^{2} − 1).

Application of GB, using the lexical ordering determined by x ≻ y, yields

(Gröbner Basis for Four Circle Curve)

y^{5}.p(y),

x.y.p(y),

x^{2} − y^{4}.q(y),

where p(y) := y^{4} − \frac{3}{2}y^{3} − \frac{1}{4}y^{2} − \frac{9}{8}y − \frac{3}{8},

q(y) := \frac{2558}{27}y^{4} − \frac{823}{9}y^{3} − \frac{3895}{54}y^{2} + \frac{823}{12}y + \frac{5}{4}.

One sees that, for any solution y of the first polynomial in the Gröbner basis, the second polynomial vanishes identically whereas the third equation yields at most two different values for x. Proceeding by the general substitution method for Gröbner bases, we obtain the following singular points:

(−1, 1), (1, 1),

(−1/2, \sqrt{3}/2), (1/2, \sqrt{3}/2),

(−\sqrt{3}/2, 1/2), (\sqrt{3}/2, 1/2),

(0, 0),

(−1/2, −\sqrt{3}/2), (1/2, −\sqrt{3}/2),

In accordance with the picture, we obtained five different values for y and, altogether, nine singular points. The computation took 78 sec in the author’s muMATH Gröbner bases package on an Apollo workstation emulation of an IBM AT.

8 Application: Geometrical Theorem Proving

Automated Geometrical Theorem Proving is intriguing in two ways. First, it is a playground for developing and studying new algorithmic techniques for automated mathematics and, second, it becomes more and more important for advanced geometric modeling, which requires to check plausibility and consistency of inaccurate and numerically distorted geometrical objects and to derive and restore their consistent shape, see for example (Kapur 1987). Apart from older approaches to geometrical theorem proving based on heuristics, recently there have been developed three systematic approaches based on three different algorithmic methods in computer algebra, namely Collins’ cylindrical algebraic decomposition method (Collins 1975), Wu’s method of characteristic sets (Wu 1978) and the Gröbner basis method. (Kutzler 1987) compares the three methods. The use of Gröbner bases for automated geometrical theorem proving has been independently introduced by B. Kutzler and D. Kapur, see for example (Kutzler, Stifter 1986) and (Kapur 1986). In this section we give an outline of the main idea how Gröbner bases can be used for proving geometrical theorems. We start with an example of a geometrical theorem. For simplicity, we present Kapur’s approach, Kutzler’s approach is slightly different.

Example: Apollonios’ Circle Theorem.

The altitude pedal of the hypotenuse of a right-angled triangle and the midpoints of the three sides of the triangle lie on a circle.

After introducing coordinates, a possible algebraic formulation of this problem is as follows:

(Hypotheses)

h_{1} := 2y_{3} − y_{1} = 0 (E is midpoint of CA),

h_{2} := 2y_{4} − y_{1} = 0 (F is midpoint of AB, 1st coordinate), h_{3} := 2y_{5} − y_{2} = 0 (F is midpoint of AB, 2nd coordinate), h_{4} := 2y_{6} − y_{2} (G is midpoint of BC), h_{5} := (y_{7} − y_{3})^{2} + y_{8}^{2} − (y_{7} − y_{4})^{2}−

−(y_{8} − y_{5})^{2} = 0 (length EM = length F M), h_{6} := (y_{7} − y_{3})^{2} + y_{8}^{2} − (y_{8} − y_{6})^{2}−

−y_{7}^{2} = 0 (length EM = length GM), h_{7} := (y_{9} − y_{1})y_{2} + y_{1}y_{10} = 0 (H lies on AB), h_{8} := −y_{1}y_{9} + y_{2}y_{10} = 0 (CH is perpendicular to AB).

(Conclusion)

c := (y_{7} − y_{3})^{2} + y_{8}^{2} − (y_{7} − y_{9})^{2}− −(y_{8} − y_{10})^{2} = 0 (length EM = length HM).

To prove the theorem means to show that

for all a_{1}, …, a_{10} ∈ R:

if h_{1}(a_{1}, …, a_{10}) = 0, …, h_{8}(a_{1}, …, a_{10}) = 0,

then c(a_{1}, …, a_{10}) = 0.

All expressions h_{i} and c occurring in this proposition are polynomial expressions. If one replaces R by C, the proposition, by definition, is just the proposition “c ∈ Radical({h_{1}, …, h_{8}})”. However, by (Radical Membership), arbitrary radical membership questions “c ∈ Radical({h_{1}, …, h_{m}})?” can be decided by deciding “1 ∈ GB({h_{1}, …, h_{m}, z.c − 1})?”, where z must be a new indeterminate.

This method is totally general and automatic for all geometrical theorems whose hypothesis and conclusions are polynomial equations. In fact, it is also efficient. Hundreds of non-trivial theorems have been proven by this approach, most of them in only several seconds of computing time, see (Kutzler, Stifter 1986), (Kapur 1986) and (Kutzler 1987) for extensive statistics.

Two remarks are appropriate. First, replacing R by C slightly distorts the problem. Of course, if a geometrical theorem holds over C then it also holds over R. The reverse is not true in general. It turns out, however, that the geometrical theorems occuring in the mathematical literature are generally true over C. Still, one must bear in mind that, if a negative answer is produced by this method for a given proposition, this does not necessarily mean that the proposition is false over R. It is false over C, it could be still true over R.

Second, most geometrical theorems are only true for the “general” case. It may well happen that they are false for “degenerate” situations, for examples, when circles have zero radius, angles become zero, lines become parallel etc. Geometric theorem proving based on the Gröbner bases method can handle degenerate situations automatically in a very strong sense.

1. In situations where the degenerate situations can be described in the form d(x_{1}, …, x_{n}) ≠ 0, d a polynomial, one can again use a new indeterminate to transform the question into an ideal (and, hence, Gröbner basis) membership question. Namely,

∀z((h(z) = 0 ∧ s(z) ≠ 0) ⟹ c(z) = 0)

is equivalent to

∃z, u, v((h(z) = 0 ∧ u.s(z) = 1 ∧ v.c(z) = 1)

is equivalent to

1 ∈ GB(h, u.s − 1, v.c − 1).

Using this wellknown transformation technique one can actually show that the Gröbner basis method yields a decision algorithm for the following general class of formulae:

(quantifiers)(arbitrary boolean combination of polynomial equations)

where either all the quantifiers must be existential or they must be universal, and the formulae must be closed, i. e. no free variables may occur.

2. The Gröbner bases approach to geometrical theorem proving can also be modified in such a way that, in case a proposition does not hold in general, the method automatically produces a set of polynomials describing the degenerate cases in which the proposition may be false. Roughly, this can be done, for example, by analyzing the denominators of the coefficients that are produced when Gröbner bases are computed over rational function coefficient fields. Quite some research has been devoted to this question, see (Kutzler 1986) and (Kapur 1986).

9 Application: Primary Decomposition

A polynomial ideal is “decomposable” iff it can be represented as the non-trivial intersection of two other polynomial ideals. Geometrically, this corresponds to a representation of the algebraic manifold (set of zeros) of the ideal as the non-trival union of two algebraic manifolds. It is well known in polynomial ideal theory that every polynomial ideal can be decomposed into finitely many ideals that can not be decomposed further (“irreducible components”) and that this decomposition is essentially unique. This is the content of the famous Lasker-Noether decomposition theorem, see for example (Van der Waerden 1953). However, the proof of this theorem is non-constructive, i. e. no general algorithmic method is provided that would find, for a polynomial ideal given by a finite basis F, the finite bases for its irreducible components.

In more detail, the primary decomposition of a polynomial ideal (algebraic manifold) I (algebraic manifold) not only gives its irreducible parts (the corresponding “prime ideals”) P_{i} but also information about the “multiplicity” of these irreducible parts. This information is contained in the “primary ideals” Q_{i} corresponding to the prime ideals. Each prime ideal and its corresponding primary ideal implicitly describe the same irreducible algebraic manifold. However, the prime ideal and a corresponding primary ideal may be different. In this case, the primary ideal tells us “how often” the irreducible manifold defined by the prime ideal occurs in the algebraic manifold defined by the given ideal I. Summarizing, the algorithmic version of the primary decomposition problem has the following specification (where we use Z(F) for “set of common zeros of F”):

(Primary Decomposition Problem)

Given: F.

Find: G_{i}, H_{i} such that the Ideal(G_{i}) are primary, the Ideal(H_{i}) are the prime ideals corresponding to Ideal(G_{i}), Ideal(F) = ⋂_{i} Ideal(G_{i}), (i. e. Z(F) = ⋃_{i} Z(G_{i})), and some minimality conditions are satisfied.

Note that the problem depends on the underlying coefficient field. For example, x^{2} + 1 is irreducible over R but reducible over C.

Recently the problem of algorithmic primary decomposition has been completely solved using Gröbner bases. Still, the algorithm for the most general case is not yet implemented in a software system. Complete implementations may be expected for the very near future. A number of papers, of different generality and level of detail, contributed to the recent progress in this area: (Kandri-Rody 1984), (Lazard 1985), (Gianni, Trager, Zacharias 1985), (Kredel 1987).

An exact formulation of the problem and a detailed description of the algorithms, which are quite involved, is beyond the scope of this paper. It should be clear that automatic decomposition of algebraic manifolds (e. g. intersection curves of 3D objects) should be of utmost importance for geometrical modeling where the global analysis of finitely represented objects, as opposed to a mere local numerical evaluation, is more and more desirable in advanced applications. All the algorithms invented for the solution of the primary decomposition problem heavily rely on the basic properties of Gröbner bases as compiled in Theorem 2.5.1 and Theorem 2.5.2, notably on the properties (Elimination Ideals), (Ideal Membership) and properties derived from these properties as, for example, (Intersection Ideal).

For bringing this important research to the attention of the geometric modeling community we present a simple example showing the kind of information obtainable from a primary decomposition.

Example: Primary Decomposition of Cylinder/Sphere Intersection.

Let us consider the intersection of a cylinder with radius r_{1} whose axis coincides with the x_{3}-axis and a sphere with radius r_{2} and midpoint at the origin. The intersection curve consists of the common zeros of the following two polynomials:

F := {x_{1}^{2} + x_{2}^{2} − r_{1}^{2}, x_{1}^{2} + x_{2}^{2} + x_{3}^{2} − r_{2}^{2}}.

Depending on whether r_{1} < r_{2}, r_{1} = r_{2}, or r_{1} > r_{2}, the primary decomposition algorithm, over R, yields the following representation of Ideal(F) as the intersection of primary ideals:

Case r_{1} < r_{2}:

Ideal(F) = Ideal(x_{3} + r, x_{2}^{2} + x_{1}^{2} − r_{1}^{2})∩ Ideal(x_{3} − r, x_{2}^{2} + x_{1}^{2} − r_{1}^{2}),

where r := \sqrt{r_{2}^{2} − r_{1}^{2}}.

The two primary components are, in fact, prime. Case r_{1} = r_{2}:

Ideal(F) = Ideal(x_{3}^{2}, x_{2}^{2} + x_{1}^{2} − r_{1}^{2}).

The ideal is already primary with corresponding prime ideal

Ideal(x_{3}, x_{2}^{2} + x_{1}^{2} − r_{1}^{2}).

Case r_{1} > r_{2}:

Ideal(F) = Ideal(x_{3}^{2} − r_{2}^{2} + r_{1}^{2}, x_{2}^{2} + x_{1}^{2} − r_{1}^{2}).

The ideal is already primary and identical to the corresponding prime ideal.

In geometrical terms, the above outcome of the primary decomposition algorithm gives us the following information:

Case r_{1} < r_{2}: The manifold decomposes in two irreducible components, namely, two horizontal circles of radius r_{1} with midpoints (0, 0, ±r). The multiplicity of these circles is one (the primary ideals are identical to their corresponding prime ideals).

Case r_{1} = r_{2}: The manifold does not decompose. It consists of the horizontal circle with radius r_{1} with midpoint (0, 0, 0). However, this circle has to be “counted twice” because, in the primary ideal, there appears the term x_{3}^{2} whereas in the prime ideal, which defines the “shape” (i. e. point set) of the manifold, x_{3} appears only linearly. This corresponds to the geometrical intuition that the intersection curve results from merging, in the limit, the two horizontal circles of case r_{1} < r_{2}.

Case r_{1} > r_{2}: The manifold does not decompose (over R!). In fact it has no real points. In contrast to the case r_{1} = r_{2}, the manifold has multiplicity one because the primary ideal coincides with the prime ideal.

10 Conclusions

The Gröbner bases method provides an algorithmic approach to many problems in polynomial ideal theory. We tried to provide some first evidence that the method could be a valuable tool for the progressing needs of geometrical engineering (geometric modeling, image processing, robotics, CAD etc.).

Further research should concentrate on two areas:

• The theoretical problems (for example, solutions at infinity in paremtric representations) occuring in the application of the method to geometrical problems must be completely studied.

• The computational behavior of the method must be improved by obtaining new mathematical results that could hold in the special situations (e. g. kinematics of certain robot classes) in which the method is applied.

Research on efficiency aspects and on geometrical applications of the Gröbner basis method is only at the beginning.

Acknowledgement. I am indebted to C. Hofmann, and B. Sturmfels for personal communications I used in this paper. Thanks also to B. Kutzler, R. Michelic-Birgmayr, and S. Stifter for helping in the preparation of some of the examples.

REFERENCES

D. S. Arnon, T. W. Sederberg, 1984. Implicit Equation for a Parametric Surface by Gröbner Bases. In: Proceedings of the 1984 MACSYMA User’s Conference (V. E. Golden ed.), General Electric, Schenectady, New York, 431–436.

A. H. Barr, 1981. Superquadrics and Angle-Preserving Transformations. IEEE Computer Graphics and Applications, 1/1, 11–23.

B. Buchberger, 1965. An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal (German). Ph. D. Thesis, Univ. of Innsbruck (Austria), Dept. of Mathematics.

B. Buchberger, 1970. An Algorithmic Criterion for the Solvability of Algebraic Systems of Equations (German). Aequationes Mathematicae 4/3, 374–383.

B. Buchberger, G. E. Collins, R. Loos, 1982. “Computer Algebra: Symbolic and Algebraic Computation”. Springer-Verlag, Vienna - New York.

B. Buchberger, 1985. Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory. In: Multidimensional Systems Theory (N. K. Bose ed.), D. Reidel Publishing Company, Dordrecht - Boston - Lancaster, 184–232.

G. E. Collins, 1975. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. 2nd GI Conference on Automata Theory and Formal Languages, Lecture Notes in Computer Science 33, 134–183.

P. Gianni, 1987. Properties of Gröbner Bases Under Specialization. Proc. of the EUROCAL ’87 Conference, Leipzig, 2–5 June 1987, to appear.

P. Gianni, B. Trager, G. Zacharias, 1985. Gröbner Bases and Primary Decomposition of Polynomial Ideals. Submitted to J. of Symbolic Computation. Available as manuscript, IBM T. J. Watson Research Center, Yorktown Heights, New York.

C. Hofmann, 1987. Algebraic Curves. This Volume. Institute for Mathematics and its Applications, U of Minneapolis.

C. Hofmann, 1987a. Personal Communication. Purdue University, West Lafayette, IN 47907, Computer Science Dept.

M. Kalkbrener, 1987. Solving Systems of Algebraic Equations by Using Gröbner Bases. Proc. of the EUROCAL ’87 Conference, Leipzig, 2–5 June 1987, to appear.

D. Kapur, 1986. A Refutational Approach to Geometry Theorem Proving. In: Proceedings of the Workshop on Geometric Reasoning, Oxford University, June 30 - July 3, 1986, to appear in Artificial Intelligence.

D. Kapur, 1987. Algebraic Reasoning for Object Construction from Ideal Images. Lecture Notes, Summer Program on Robotics: Computational Issues in Geometry, August 24–28, Institute for Mathematics and its Applications, Univ. of Minneapolis.

A. Kandri-rody, 1984. Effective Methods in the Theory of Polynomial Ideals. Ph. D. Thesis, Rensselaer Polytechnic Institute, Troy, New York, Dept. of Computer Science.

H. Kredel, 1987. Primary Ideal Decomposition. Proc of the EUROCAL ’87 Conference, Leipzig, 2–5 June 1987, to appear.

B. Kutzler, 1987. Implementation of a Geometry Proving Package in SCRATCH-PAD II. Proceedings of the EUROCAL ’87 Conferenc, Leipzig, 2–5 June, 1987, to appear.

B. Kutzler, S. Stifter, 1986. On the Application of Buchberger’s Algorithm to Automated Geometry Theorem Proving. J. of Symbolic Computation, 2/4, 389–398.

D. Lazard, 1985. Ideal Bases and Primary Decomposition: Case of Two Variables. J. of Symbolic Computation 1/3, 261–270.

R. P. Paul, 1981. “ Robot Manipulators: Mathematics, Programming, and Control”. The MIT Press, Cambridge (Mass.), London.

F. P. Preparata, M. I. Shamos, 1985. “Computational Geometry”. Springer-Verlag, New York, Berlin, Heidelberg.

T. W. Sederberg, D. C. Anderson, 1984. Implicit Representation of Parametric Curves and Surfaces. Computer Vision, Graphics, and Image Processing 28, 72–84.

D. Spear, 1977. A Constructive Approach to Ring Theory. Proc. of the MACSYMA Users’ Conference, Berkeley, July 1977 (R. J. Fateman ed.), The MIT Press, 369–376.

B. Sturmfels, 1987. Private Communication. Institute for Mathematics and its Applications.

W. Trinks, 1978. On B. Buchberger’s Method for Solving Systems of Algebraic Equations (German). J. of Number Theory 10/4, 475–488.

A. Van den Essen, 1986. A Criterion to Decide if a Polynomial Map is Invertible and to Compute the Inverse. Report 8653, Catholic University Nijmegen (The Netherlands), Dept. of Mathematics.

B. L. Van der Waerden, 1953. “Modern Algebra I, II”, Frederick Ungar Publ. Comp., New York.

F. Winkler, 1986. Solution of Equations I: Polynomial Ideals and Gröbner Bases. Proc. of the Conference on Computers and Mathematics, Stanford University, July 30 - August 1, 1986, to appear.

W. T. Wu , 1978. On the Decision Problem and the Mechanization of Theorem Proving in Elementary Geometry. Scientia Sinica 21, 150-172.