Cotas inferiores para la resolución de sistemas de Pham generalizados.

EZEQUIEL DRATMAN; GUILLERMO MATERA; ARIEL WAISSBEIN

UNCUYO. Mendoza. Argentina.

Congreso; UMA 2008; 2008

UNCUYO.

En esta comunicación analizamos la complejidad intrínseca de la resolución de una clase de sistemas de ecuaciones polinomiales de dimensión cero, conocidos como sistemas de Phamgeneralizados. Estos sistemas, también denominados ``intersecciones completas estrictas´´, pueden describirse como el resultado de deformar una singularidad aislada proyectiva e intersección completa, y corresponden a la noción intuitiva de sistemas (de dimensión cero) ``sin puntos en el infinito". En ocasiones nos encontramos con estos sistemas en el análisis de las soluciones estacionarias de ciertas ecuaciones diferenciales parabólicas con términos de reacción y difusión no lineales. Para esto, en lugar de discutir la complejidad de todos los posibles algoritmos que resuelven sistemas de Pham generalizados, vamos a concentrarnos en los algoritmos ``universales´´ y``robustos´´. Un algoritmo universal que resuelve sistemas polinomiales es un algoritmo cuya salida contiene información ``completa´´ sobre el sistema en consideración. Este concepto de universalidad, que se remonta al menos a Kronecker, subyace al diseño de todos los algoritmosconocidos en geometría algebraica computacional. Asimismo, un algoritmo universal se dice ``robusto´´ si resuelve familias de sistemas polinomiales evitando ramificaciones ``innecesarias´´ ypermitiendo la solución de ciertos problemas límites. Los algoritmos universales robustos forman una clase importante de algoritmos que incluye, entre otros, a los algoritmos que utilizan bases de Gröbner ``comprensivas´´ (comprehensive Gröbner bases), los algoritmos que calculan  resultantes y los algoritmos de eliminación de tipo caja negra. En estos términos, demostramos que un algoritmo universal robusto que calcula polinomios minimales de proyecciones lineales genéricas de sistemas de Pham generalizados tiene complejidad de orden $D^{Omega(1)}$, donde $D$ es el número de Bèzout delsistema de entrada. Este resultado es independiente de la representación del polinomio minimal de la proyección lineal en consideración, aunque el tamaño de la constante subyacente a lanotación $Omega$ depende de la representación. En particular, si se usa la habitual representación densa o rala de polinomios multivariados, entonces la complejidad del correspondiente algoritmo es de orden $Omega(D)$, en tanto que si la representación es pormedio de cálculos de evaluación (straight--line programs), la cota inferior es de orden $Omega(D^{1/2})$.