Cálculo de proyecciones para sistemas de ecuaciones polinomiales ralas genéricas

MARÍA ISABEL HERRERO; GABRIELA JERONIMO; JUAN SABIA

Rosario

Congreso; LXII Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2013

Unión Matemática Argentina

El cálculo de la clausura de la proyección lineal de una variedad algebraica es un problema clásico de teoría de eliminación. La eliminación de cuantificadores algorítmica sobre cuerpos algebraicamente cerrados fue extensamente estudiada (ver por ejemplo [2], [1] y [4]). La complejidad de los algoritmos conocidos depende de la cantidad de polinomios que definen la variedad, sus grados y el número de variables que involucran. En esta comunicación presentamos un algoritmo probabilístico simbólico para resolver el problema en el caso de sistemas de ecuaciones polinomiales ralas genéricas teniendo en cuenta la estructura de los soportes. Esto es, dada una variedad definida por un sistema ralo genérico de m polinomios en n variables, el algoritmo calcula la clausura de Zariski de su proyección a las primeras ℓ coordenadas (con ℓ < n). La complejidad del algoritmo es polinomial en invariantes combinatorios asociados al conjunto de los soportes de los polinomios del input. La idea del algoritmo es, usando la descomposición de la variedad definida por los polinomios del sistema probada en [3], reducir el problema en primer lugar al caso de variedades equidimensionales tales que todas sus componentes tienen algún punto de coordenadas no nulas. Para cada una de estas variedades equidimensionales, calcular la resolución geométrica de una variedad asociada respecto a un subconjunto apropiado de variables libres. Finalmente y a partir de esta resolución geométrica, obtener una resolución geométrica de la clausura de la proyección buscada. Referencias [1] A. L. Chistov, D. Y. Grigor´ev, Complexity of quantifier elimination in the theory of algebraically closed fields. Mathematical foundations of computer science, 1984 (Prague, 1984), 17-31, Lecture Notes in Comput. Sci., vol. 176, Springer, Berlin, 1984. [2] J. Heintz, Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comput. Sci. 24 (1983), no. 3, 239-277. [3] M.I. Herrero, G. Jeronimo, J. Sabia. Affine solution sets of sparse polynomial systems. Journal of Symbolic Computation 51 (2013), pp. 34-54. [4] S. Puddu, J. Sabia, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs. J. Pure Appl. Algebra 129 (1998), no. 2, 173-200.