de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Almost Tight Recursion Tree Bounds for the Descartes Method

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44369

Eigenwillig,  Arno
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45466

Sharma,  Vikram
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Eigenwillig, A., Sharma, V., & Yap, C. K. (2006). Almost Tight Recursion Tree Bounds for the Descartes Method. In ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation (pp. 71-78). New York, USA: ACM.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-21EB-9
Abstract
We give a unified ("basis free") framework for the Descartes method for real root isolation of square-free real polynomials. This framework encompasses the usual Descartes' rule of sign method for polynomials in the power basis as well as its analog in the Bernstein basis. We then give a new bound on the size of the recursion tree in the Descartes method for polynomials with real coefficients. Applied to polynomials $A(X) = \sum_{i=0}^n a_iX^i$ with integer coefficients $\abs{a_i} < 2^L$, this yields a bound of $O(n(L + \log n))$ on the size of recursion trees. We show that this bound is tight for $L = \Omega(\log n)$, and we use it to derive the best known bit complexity bound for the integer case.