2017/04/23 by Jindal, Gorav, Sagraloff, Michael · 1 citation
#F.2.1 #FOS: Computer and information sciences #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1704.06979
We propose an efficient algorithm to compute the real roots of a sparse polynomial f∈ℝ[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⊂ℂ, with s<2k, centered at the real axis and of radius less than 2-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.