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).