Campus Event Calendar
Event Entry
What and Who
Almost Tight Recursion Tree Bounds for the Descartes Method
Arno Eigenwillig
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 7 July 2006
13:30
30 Minutes
E1 4
023
Saarbrücken
Abstract
Joint work with V. Sharma and C. K. Yap.
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} less than 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.
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} less than 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.
Contact
Arno Eigenwillig
-129
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Polynomial real root isolation, Descartes method, Descartes rule of signs, Bernstein basis, Davenport-Mahler bound.
This is a practice talk for a conference.
Carina Schmitt, 07/03/2006 14:03
Arno Eigenwillig, 06/28/2006 17:49
Arno Eigenwillig, 06/27/2006 10:33 -- Created document.
Arno Eigenwillig, 06/28/2006 17:49
Arno Eigenwillig, 06/27/2006 10:33 -- Created document.