# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Efficiently Computing Real Roots of Sparse Polynomials

##### 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.

Cite as: https://hdl.handle.net/11858/00-001M-0000-002D-8AD1-7

##### Abstract

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.