Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

On the Complexity of the Descartes Method when Using Approximate Arithmetic


Sagraloff,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Sagraloff, M. (2014). On the Complexity of the Descartes Method when Using Approximate Arithmetic. Journal of Symbolic Computation, 65, 79-110. doi:10.1016/j.jsc.2014.01.005.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-3671-9
In this paper, we introduce a variant of the Descartes method to isolate the real roots of a square-free polynomial F ( x ) = ∑ i = 0 n A i x i with arbitrary real coefficients. It is assumed that each coefficient of F can be approximated to any specified error bound. Our algorithm uses approximate arithmetic only, nevertheless, it is certified, complete and deterministic. We further provide a bound on the complexity of our method which exclusively depends on the geometry of the roots and not on the complexity of the coefficients of F. For the special case, where F is a polynomial of degree n with integer coefficients of maximal bitsize τ, our bound on the bit complexity writes as O ˜ ( n 3 τ 2 ) . Compared to the complexity of the classical Descartes method from Collins and Akritas (based on ideas dating back to Vincent), which uses exact rational arithmetic, this constitutes an improvement by a factor of n. The improvement mainly stems from the fact that the maximal precision that is needed for isolating the roots of F is by a factor n lower than the precision needed when using exact arithmetic.