An algorithm to decide the existence of real roots of sparse univariate integer polynomials

DANIEL PERRUCCI

Ouessant, Francia

Workshop; Workshop on Algorithms in Real Algebraic Geometry and Applications; 2005

Let f in Z[X] be a polynomial of degree D.The existing algorithms that decide whether f has a real rootrely on Sturm's algorithm and work in O(D^2) operations.Here we present an algorithm that takes into account the number ofmonomials in f in order to decide the vanishing in R ofgeneric sparse polynomials. More specifically, if we call m thenumber of non-zero coefficients in f and ||f||_1 the sum ofthe absolute valuesof these coefficients, the number of operations it requires is bounded by O(log D + log ||f||_1)^(2m).In particular, for fixedm, we get an algorithm to decide the existence of real roots ofm-nomials within complexity polynomial in log D andlog||f||_1. This is joint work with Juan Sabia (in progress).