Campus Event Calendar
Event Entry
What and Who
Root Isolation of Polynomials with Black-Box Coefficients
Prof. Dr. Kurt Mehlhorn
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 30 June 2005
13:00
-- Not specified --
45
016
Saarbrücken
Abstract
In the EXACUS (exact computation with curves and surfaces) project,
we have
the need for an efficient algorithm for computing the real roots
of polynomials with real coefficients (like 7 or $\pi$ or $\sqrt{19}$.
The Descartes method is an algorithm for isolating the
real roots of square-free polynomials with real coefficients. We assume
that coefficients are given as (potentially infinite) bit-streams. In other
words, coefficients can be approximated to any desired accuracy, but are not
known exactly. We show that
a variant of Descartes algorithm can cope with bit-stream
coefficients. To isolate the real roots of a
square-free real polynomial $q(x) = q_nx^n+\ldots+q_0$ with root
separation $\rho$, coefficients $\abs{q_n}\ge1$ and $\abs{q_i} \le 2^\tau$,
it needs coefficient approximations to $O(n(\log(1/\rho) + \tau))$
bits after the binary point and has an expected cost of
$O(n^4 (\log(1/\rho) + \tau)^2)$ bit operations.
I discuss the background in computational geometry and then discuss Descartes
algorithm. There are no prerequesites in computer algebra.
we have
the need for an efficient algorithm for computing the real roots
of polynomials with real coefficients (like 7 or $\pi$ or $\sqrt{19}$.
The Descartes method is an algorithm for isolating the
real roots of square-free polynomials with real coefficients. We assume
that coefficients are given as (potentially infinite) bit-streams. In other
words, coefficients can be approximated to any desired accuracy, but are not
known exactly. We show that
a variant of Descartes algorithm can cope with bit-stream
coefficients. To isolate the real roots of a
square-free real polynomial $q(x) = q_nx^n+\ldots+q_0$ with root
separation $\rho$, coefficients $\abs{q_n}\ge1$ and $\abs{q_i} \le 2^\tau$,
it needs coefficient approximations to $O(n(\log(1/\rho) + \tau))$
bits after the binary point and has an expected cost of
$O(n^4 (\log(1/\rho) + \tau)^2)$ bit operations.
I discuss the background in computational geometry and then discuss Descartes
algorithm. There are no prerequesites in computer algebra.
Contact
--email hidden
passcode not visible
logged in users only
Bahareh Kadkhodazadeh, 06/28/2005 12:47
Bahareh Kadkhodazadeh, 04/07/2005 15:55 -- Created document.
Bahareh Kadkhodazadeh, 04/07/2005 15:55 -- Created document.