English

# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Efficiently Computing Real Roots of Sparse Polynomials

##### MPS-Authors
/persons/resource/persons123330

Jindal,  Gorav
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45332

Sagraloff,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### External Resource
No external resources are shared
##### Fulltext (restricted access)
There are currently no full texts shared for your IP range.
##### Fulltext (public)

arXiv:1704.06979.pdf
(Preprint), 247KB

##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Jindal, G., & Sagraloff, M. (2017). Efficiently Computing Real Roots of Sparse Polynomials. Retrieved from http://arxiv.org/abs/1704.06979.

We propose an efficient algorithm to compute the real roots of a sparse polynomial $f\in\mathbb{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 $\Delta_{1},\ldots,\Delta_{s}\subset\mathbb{C}$, with $s<2k$, centered at the real axis and of radius less than $2^{-L}$ together with positive integers $\mu_{1},\ldots,\mu_{s}$ such that each disk $\Delta_{i}$ contains exactly $\mu_{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 $\tau$, where $2^{-\tau}$ and $2^{\tau}$ 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 $\tau$ and $\log\sigma^{-1}$, where $\sigma$ denotes the separation of the real roots.