Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: New data structure for univariate polynomial approximation and
  applications to root isolation, numerical multipoint evaluation, and other
  problems   We present a new data structure to approximate accurately and efficiently a
polynomial $f$ of degree $d$ given as a list of coefficients. Its properties
allow us to improve the state-of-the-art bounds on the bit complexity for the
problems of root isolation and approximate multipoint evaluation. This data
structure also leads to a new geometric criterion to detect ill-conditioned
polynomials, implying notably that the standard condition number of the zeros
of a polynomial is at least exponential in the number of roots of modulus less
than $1/2$ or greater than $2$.Given a polynomial $f$ of degree $d$ with
$\|f\|_1 \leq 2^\tau$ for $\tau \geq 1$, isolating all its complex roots or
evaluating it at $d$ points can be done with a quasi-linear number of
arithmetic operations. However, considering the bit complexity, the
state-of-the-art algorithms require at least $d^{3/2}$ bit operations even for
well-conditioned polynomials and when the accuracy required is low. Given a
positive integer $m$, we can compute our new data structure and evaluate $f$ at
$d$ points in the unit disk with an absolute error less than $2^{-m}$ in
$\widetilde O(d(\tau+m))$ bit operations, where $\widetilde O(\cdot)$ means
that we omit logarithmic factors. We also show that if $\kappa$ is the absolute
condition number of the zeros of $f$, then we can isolate all the roots of $f$
in $\widetilde O(d(\tau + \log \kappa))$ bit operations. Moreover, our
algorithms are simple to implement. For approximating the complex roots of a
polynomial, we implemented a small prototype in \verb|Python/NumPy| that is an
order of magnitude faster than the state-of-the-art solver \verb/MPSolve/ for
high degree polynomials with random coefficients.

5
The categories of this paper are: gr-qc
24
The categories of this paper are: dg-ga
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
23
The categories of this paper are: solv-int
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex
26
The categories of this paper are: bayes-an
10
The categories of this paper are: q-bio
34
The categories of this paper are: chem-ph
4
The categories of this paper are: cond-mat
18
The categories of this paper are: econ
8
The categories of this paper are: hep-ex
22
The categories of this paper are: chao-dyn
21
The categories of this paper are: adap-org
11
The categories of this paper are: hep-lat