Chee K. Yap, professor of computer science at New York University, will give a colloquium titled, "Recent Results on Exact Root Isolation and their Complexity" at 4:00 PM in 127 Hayes-Healy Center.
Abstract
The problem of finding roots of functions is a highly classical problem that is central to computational mathematics and many applications of computer science. The critical task here is root isolation: to isolate all roots in a given real or complex domain. We consider “exact methods” which provide a priori, global guarantees of correctness. These are usually contrasted with numerical approaches which has no such guarantees.
Traditionally, exact methods rely on strong algebraic principles like Sturm Sequences. Such methods are non-adaptive and cannot be used to isolate non-algebraic roots. Moreover, they are much slower than numerical approaches. Most adaptive numerical approaches are iterative, and complexity analysis of such algorithms are lacking.
We will survey three sets of results on “exact” methods. They are based on a family of subdivision algorithms that use purely numerical primitives:
- EVAL is an iterative algorithm for isolating all real roots in a given interval. We introduce the notion of “continuous amortization” and prove the near optimality tree size for EVAL on square-free integer polynomials.
- CEVAL is the analogue of EVAL for isolating all the complex roots in a box region. We prove that it has bit complexity that matches the best algebraic algorithms.
- AEVAL is the analogue of CEVAL but for analytic functions. We give the first complete numerical solution for the root clustering problem for analytic functions.
Prof. Yap will conclude with prospects of such approaches for other nonlinear problems of Computational Geometry.
Abstract
Originally published at acms.nd.edu.