Almost tight recursion tree bounds for the descartes method

Arno Eigenwillig, Vikram Sharma, Chee K. Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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) = ∑i=0 n aiXi with integer coefficients |a i| < 2L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(log n), and we use it to derive the best known bit complexity bound for the integer case.

Original languageEnglish (US)
Title of host publicationProceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006
PublisherAssociation for Computing Machinery (ACM)
Pages71-78
Number of pages8
ISBN (Print)1595932763, 9781595932761
DOIs
StatePublished - 2006
EventInternational Symposium on Symbolic and Algebraic Computation, ISSAC 2006 - Genova, Italy
Duration: Jul 9 2006Jul 12 2006

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
Volume2006

Other

OtherInternational Symposium on Symbolic and Algebraic Computation, ISSAC 2006
CountryItaly
CityGenova
Period7/9/067/12/06

Keywords

  • Bernstein basis
  • Davenport-Mahler bound
  • Descartes method
  • Descartes rule of signs
  • Polynomial real root isolation

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Almost tight recursion tree bounds for the descartes method'. Together they form a unique fingerprint.

  • Cite this

    Eigenwillig, A., Sharma, V., & Yap, C. K. (2006). Almost tight recursion tree bounds for the descartes method. In Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC 2006 (pp. 71-78). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1145768.1145786