Campus Event Calendar
Event Entry
What and Who
On Classical Real Root Isolation and its Complexity Analysis
Arno Eigenwillig
Max-Planck-Institut für Informatik - AG 1
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5
MPI Audience
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 4 May 2006
13:00
-- Not specified --
E1 3 - Hörsaal Gebäude
16
Saarbrücken
Abstract
Consider a polynomial f(x) with real coefficients.
The problem of real root isolation asks to find a
set of non-intersecting intervals such that each
interval contains exactly one real root of f(x).
In this talk, I will gently introduce the root
counting methods of Descartes-Jacobi and Sturm and
the bisection algorithms for real root isolation
resulting from them (with a brief unexpected guest
performance of Bézier curves).
As far as time permits, I will then outline the main
common ingredient of the complexity analyses of both
methods, namely the almost tight bound on the size
of the recursion tree resulting directly from the
Davenport-Mahler inequality. For the Descartes
method, this is a new result and will be presented
at this year's ISSAC (joint work by V. Sharma, C. Yap,
and myself).
The problem of real root isolation asks to find a
set of non-intersecting intervals such that each
interval contains exactly one real root of f(x).
In this talk, I will gently introduce the root
counting methods of Descartes-Jacobi and Sturm and
the bisection algorithms for real root isolation
resulting from them (with a brief unexpected guest
performance of Bézier curves).
As far as time permits, I will then outline the main
common ingredient of the complexity analyses of both
methods, namely the almost tight bound on the size
of the recursion tree resulting directly from the
Davenport-Mahler inequality. For the Descartes
method, this is a new result and will be presented
at this year's ISSAC (joint work by V. Sharma, C. Yap,
and myself).
Contact
--email hidden
passcode not visible
logged in users only
Veronika Weinand, 04/26/2006 14:28
Veronika Weinand, 04/26/2006 14:21 -- Created document.
Veronika Weinand, 04/26/2006 14:21 -- Created document.