General Workshop of the European Community's

ACS Project

May 8-11, 2006
Athens, Greece.

Conference Program:

(ACS=Algorithms for Complex Shapes)

New Bounds in the Analysis of Subdivision Algorithms for Real Root Isolation
Chee Yap, Courant Institute


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.