General Workshop of the European Community's
ACS Project
May 8-11, 2006
Athens, Greece.
(ACS=Algorithms for Complex Shapes)
TALK TITLE:
New Bounds in the Analysis of Subdivision Algorithms
for Real Root Isolation
Chee Yap, Courant Institute
ABSTRACT
An important class of algorithms for
isolating real roots of polynomials
is based on the paradigm of subdivision,
basically a form of binary search.
This includes the Sturm algorithm and the Descartes method.
A variant of the latter is applicable for polynomials
in the Bernstein basis. Algorithms
based on the Descartes method is very efficient in practice.
In this talk, we introduce a third class of such algorithms,
based on polynomial evaluation and interval arithmetic,
derived from the work of Plantinga and Vegter on meshing surfaces.
Almost no previous complexity analysis of such algorithms are known.
We describe three recent results in bounding the complexity of such algorithms:
(1) Simplified approach to the efficient evaluation of Sturm sequences.
(2) Almost optimal bounds in the Descartes method.
(3) Complexity analysis of an evaluation-based root isolation algorithm.