hide
Free keywords:
Computer Science, Symbolic Computation, cs.SC,Computer Science, Numerical Analysis, cs.NA,Mathematics, Numerical Analysis, math.NA
Abstract:
Computing the real roots of a polynomial is a fundamental problem of
computational algebra. We describe a variant of the Descartes method that
isolates the real roots of any real square-free polynomial given through
coefficient oracles. A coefficient oracle provides arbitrarily good
approximations of the coefficients. The bit complexity of the algorithm matches
the complexity of the best algorithm known, and the algorithm is simpler than
this algorithm. The algorithm derives its speed from the combination of
Descartes method with Newton iteration. Our algorithm can also be used to
further refine the isolating intervals to an arbitrary small size. The
complexity of root refinement is nearly optimal.
