A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties

✍ Scribed by Michael Kalkbrener

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 628 KB
• Volume: 15
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1993.1011

✦ Synopsis

We present an algorithm that computes an unmixed-dimensional decomposition of an arbitrary algebraic variety (V). Each (V_{i}) in the decomposition (V=V_{1} \cup \ldots \cup V_{m}) is given by a finite set of polynomials which represents the generic points of the irreducible components of (V_{i}). The basic operation in our algorithm is the computation of greatest common divisors of univariate polynomials over extension fields. No factorization is needed.

Some of the main problems in polynomial ideal theory can be solved by means of our algorithm: we show how the dimension of an ideal can be computed, systems of algebraic equations can be solved, and radical membership can be decided.

Our algorithm has been implemented in the computer algebra system MAPLE. Timings on well-known examples from computer algebra literature are given.