Campus Event Calendar
Event Entry
What and Who
When Newton meets Descartes: A simple and fast method to isolate the real roots of a polynomial
Michael Sagraloff
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 28 October 2011
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
I will present a new (simple) subdivision method to isolate the real roots of a polynomial. The current best practical approach is based on Descartes' Rule of Signs and performs bisection in each iteration. In comparison to the asymptotically fast methods from Schoenhage (1980s) and Pan (1990s), its worst case bit complexity is by magnitudes weaker. However, the asymptotically fast algorithms are very difficult to access and to implement, and implementations (if existent at all) have not proven to be efficient in practice.
The main reason for the weaker bit complexity of the Descartes method is its conservative subdivision strategy that allows linear convergence only.
In the new algorithm, we combine Descartes method with Newton iteration. Following this approach, quadratic convergence can be achieved in most iterations. As a result, the size of the induced recursion tree reduces by one magnitude, whereas the bit complexity becomes comparable to that of the known asymptotically fast methods.
Contact
Michael Sagraloff
--email hidden
passcode not visible
logged in users only
Michael Sagraloff, 10/24/2011 15:24 -- Created document.