generalization of Ritt's irreducible ascending sets (see Ritt, 1950). The main difference between these two concepts is that no irreducibility condition is imposed on tegular chains. Therefore, regular chains represent unmixed-dimensional varieties instead of irreducible varieties, and no factorization is required to compute them.
In Wu (1986) a modified version of Ritt's decomposition algorithm is presented. FLe-cently Gao and Chou proved that the coarse form decomposition algorithm in Wu (1986), which does not use polynomial factorization either, computes unmixed-dimensional decompositions of varieties (Gao & Chou, 1991).
Regular chains are also similar to triangular sets, a concept introduced by D. Lazard. In Lazard (1992) triangular sets are used for solving zero-dimensional systems of algebraic equations. Without giving a correctness proof, D. Lazard generalized this algorithm to systems of arbitrary dimension in Lazard (1991). Furthermore, the definition of triangular sets given in Lazard (1992) is strengthened in Lazard (1991) in order to guarantee that different triangular sets represent different varieties. Regular chains do not have this "canonical representation" property. Compared to the definition of triangular sets given in Lazard (1991), the definition of regular chains is simpler and more general. Our whole algorithm has a rather simple structure and is easy to implement. Recently, an implementation has been done in MAPLE V.
The basic operation in our algorithm is the computation of greatest common divisors of univariate polynomials over extension fields given by regular chains. Our strategy for computing in these extension fields is similar to the one for computing in algebraic extension fields suggested in Delia Dora et al. (1985) and implemented in Scratchpad under the name D5 (see Dicrescenzo & Duval, 1988).
In Section 2 we introduce the concept of regular chains and state more formally the problem we are concerned with. In Section 3 we show that if a variety is represented by regular chains then it is easy to determine its dimension, to compute the generic points of its irreducible components, and to decide radical membership. In Section 4 algorithms are developed for computing in extension fields given by regular chains. In particular, we present an algorithm for computing the greatest common divisor of univariate polynomials over extension fields given by regular chains. In Section 5 we give an algorithmic solution based on this gcd algorithm for the problem stated in Section 2. In Section 6 timings on well-known examples from computer algebra literature are presented. The termination and correctness of every algorithm presented in this paper are proved in Section 7 or Section 8.
