Computing the (real) roots of polynomial is an important problem in mathematics and theoretical computer science. We propose an efficient algorithm to compute the real roots of a sparse polynomial having k non-zero real-valued coefficients. It is known that even for 4-nomials, one can not hope for a polynomial (in the input size) time algorithm for isolating the real roots. Therefore we propose a slightly relaxed notion of isolation of real roots. For a given positive integer L, our algorithm returns disjoint disks D1,D2,…,Ds with s<2k, centred at the real axis and of radius less than 2−L together with positive integers u1,…,us such that each disk Di contains exactly ui roots of f counted with multiplicity. In addition, it is ensured that each real root of f is contained in one of the disks. If f has only simple real roots, our algorithm can also be used to isolate all real roots.The bit complexity of our algorithm is polynomial in k and log(n),and near-linear in L and τ, where 2−τ and 2τ constitute lower and upper bounds on the absolute values of the non-zero coefficients of f, and n is the degree of f. For root isolation, the bit complexity is polynomial in k and log(n), and near-linear in τ and log(1/σ), where σ denotes the separation of the real roots. We also show that the roots of integer trinomials are well separated (this was also independently proved by Koiran). By using our algorithm, it follows that the real roots of trinomials can be isolated in polynomial time.
This is joint work with Michael Sagraloff (Max-Planck-Institut für Informatik and University of Applied Sciences Landshut).
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
