hide
Free keywords:
Computer Science, Symbolic Computation, cs.SC
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.
