Campus Event Calendar
Event Entry
What and Who
Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs
Arno Eigenwillig
Max-Planck-Institut für Informatik - D1
Promotionskolloquium
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 15 May 2008
15:00
60 Minutes
E1 1 - Informatik
407 - Konferenzraum
Saarbrücken
Abstract
The Descartes Method (Collins/Akritas, 1976) isolates the real roots of a univariate polynomial by recursive interval subdivision, using Descartes' Rule of Signs as termination criterion. The thesis to be presented provides an improved estimate for the resulting subdivision tree based on the theorem of Davenport and Mahler, from which the best known bitcomplexity bounds for integral input polynomials follow at once. Furthermore, it describes and analyzes a variant of the method that works correctly for so-called "bitstream" coefficients, which can be approximated arbitrarily well but cannot be determined exactly.
Contact
Arno Eigenwillig
-129
--email hidden
passcode not visible
logged in users only
Arno Eigenwillig, 05/09/2008 10:22 -- Created document.