Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Computing Real Roots of Real Polynomials ... and now For Real!   Very recent work introduces an asymptotically fast subdivision algorithm,
denoted ANewDsc, for isolating the real roots of a univariate real polynomial.
The method combines Descartes' Rule of Signs to test intervals for the
existence of roots, Newton iteration to speed up convergence against clusters
of roots, and approximate computation to decrease the required precision. It
achieves record bounds on the worst-case complexity for the considered problem,
matching the complexity of Pan's method for computing all complex roots and
improving upon the complexity of other subdivision methods by several
magnitudes.
  In the article at hand, we report on an implementation of ANewDsc on top of
the RS root isolator. RS is a highly efficient realization of the classical
Descartes method and currently serves as the default real root solver in Maple.
We describe crucial design changes within ANewDsc and RS that led to a
high-performance implementation without harming the theoretical complexity of
the underlying algorithm.
  With an excerpt of our extensive collection of benchmarks, available online
at http://anewdsc.mpi-inf.mpg.de/, we illustrate that the theoretical gain in
performance of ANewDsc over other subdivision methods also transfers into
practice. These experiments also show that our new implementation outperforms
both RS and mature competitors by magnitudes for notoriously hard instances
with clustered roots. For all other instances, we avoid almost any overhead by
integrating additional optimizations and heuristics.

37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
12
The categories of this paper are: nucl-th
9
The categories of this paper are: nlin
19
The categories of this paper are: eess
24
The categories of this paper are: dg-ga
11
The categories of this paper are: hep-lat
36
The categories of this paper are: cmp-lg
30
The categories of this paper are: q-alg
15
The categories of this paper are: nucl-ex
18
The categories of this paper are: econ
5
The categories of this paper are: gr-qc
27
The categories of this paper are: comp-gas
34
The categories of this paper are: chem-ph
16
The categories of this paper are: stat
14
The categories of this paper are: math-ph