Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt





On the Complexity of the Descartes Method when Using Approximate Arithmetic


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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

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.

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.