# Analytic Root Isolation: a complete unconditional Clustering Algorithm

## Chee Yap, Courant Institute, NYU

## October 21, 2014

We address the problem of localizing the zeroes of a complex analytic
function $f$. Here, $f$ is represented by effective interval
functions for $f$ and its higher derivatives. We formulate the "root
clustering problem" as a generalization of root isolation. We
describe an unconditional algorithm based on soft zero tests.

We give a brief overview of recent algorithms of this kind
for algebraic roots, and their complexity analysis.

Testing if $f$ evaluated at a point is equal to zero is not generally
known to be computable. We introduce weaker forms of such tests,
called "soft zero tests". Typically, algorithms with soft tests can
only localize zeroes for functions that are "nice" (e.g.,
non-singular, smooth, Morse, etc). Our algorithm is unconditional in
the sense that no niceness conditions are needed.

Joint Work with V. Sharma (IMSc, Chennai) and M. Sagraloff (MPI, Saarbrücken).