Effective equidimensional descomposition of algebraic varieties

Presentamos algoritmos para el cálculo de la descomposición equidimensional de una variedad algebraica afín a partir (le un conjunto finito de polinomios que la define: En primer lugar, se prueba la existencia de un algoritmo dcterminístico no uniforme que calcula en tiempo polinomial una descripción de la componente equidimensional de dimensión máxima de una variedad algebraica. Aplicando este algoritmo se obtiene un procedimiento para decidir si una variedad es equidimensional o no. A continuación, se construye un algoritmo probabilistico que (la en tiempo polinomial, para cada componente equidimensional de una variedad dada, un conjunto Íinito de polinomios que la define. Para terminar, se desarrolla otro algoritmo probabilístico, que calcula la forma de Chow de cada una de las componentes equidimensionales de una variedad. La cota para la complejidad de este algoritmo también es —en el peor caso- polinomial en el tamaño del input. Sin embargo, bajo ciertas condiciones genéricas, puede darse una cota para su complejidad secuencial en términos del grado geométrico del sistema de polinomios que define la variedad y, por lo tanto, puede ser de orden muy inferior. Palabras clave: Sistemas de ecuaciones polinomiales, algoritmos, complejidad, variedades equidimensionales, descomposición equidimensional, forma de Chow.We present algorithms for the computation of the equidimensional decomposition of an alline algebraic variety from a finite set of polynomials defining it: First, we prove the existence of a non-uniform deterministic algorithm which computes a description of the equidimensional component of maximal dimension of an algebraic variety in polynomial time. Applying this algorithm we obtain a procedure to determine whether a variety is equidimensional or not. Then, we construct a probabilistic algorithm which gives a finite set of polynomials defining each equidimensional component of a given variety in polynomial time. Finally, another probabilistic algorithn is developed. It computes the Chow form of each equidimensional component of a variety. The complexity bound for this algorithm —in the worst case- is also polynomial in the input size. IIowever, under certain genericity conditions, a complexity estimate in terms of the geometric degree of the polynomial system defining the variety can be given and, therefore, it may result in a much lower complexity order. Key words: Polynomial equation systems, algorithms, complexity, equidimensional varieties, equidimensional decomposition, Chow form.Fil:Talí Jerónimo, Gabriela. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina