Raíces reales en polinomios ralos

DANIEL PERRUCCI; JUAN SABIA

Salta, Pcia. de Salta

Congreso; LV Reunión de Comunicaciones Científicas de la UMA; 2005

UMA

La existencia de raíces reales de un polinomio suele decidirsemediante el algoritmo de Sturm. Dado un polinomio f en Z[X] de grado D, la complejidad de este algoritmo esO(D log^2(D)). Aquí presentamos un nuevo algoritmo quetiene en cuenta la cantidad de monomios que aparecen en lafórmula de definición de f, lo que lo hace conveniente paradecidir la existencia de raíces reales de polinomios ralosbajo ciertas hipótesis. Más especificamente, si llamamos mal número de monomios en f y ||f||_1 a la suma de losvalores absolutos de sus coeficientes, la complejidad de estealgoritmo para decidir la existencia de raíces de f bajolas hipótesis mencionadas  es O(log D + log ||f||_1)^(m). En particular, para m fijo, este algoritmo resultapolinomial en el tamaño de los datos de entrada.