Efficiently Computing Real Roots of Sparse Polynomials

We propose an efficient algorithm to compute the real roots of a sparse polynomial f∈R[x] having k non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the non-zero coefficients are given by means of a coefficient oracle. For a given positive integer L, our algorithm returns disjoint disks Δ 1 ,...,Δ s ⊂C, with s -L together with positive integers μ 1 ,...,μ s such that each disk Δ i contains exactly μ i 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.