Theory Seminars at the Courant Institute
New York University

Title: Robust Approximate Zeros for Newton's Method.

Speaker: Vikram Sharma (CIMS)


Smale's notion of an approximate zero of an analytic function F closed on the complex domain is extended to take into account the errors incurred in the evaluation of the Newton operator.  Call this stronger notion a robust approximate zero. We develop a corresponding robust point estimate for such zeros: we prove that if a complex number z_0 satisfies \alpha(F,z_0)<0.02 then z_0 is a robust approximate zero, with the associated zero z* lying in the closed disc centered  at z_0 and of radius \frac{0.07}{\gamma(F,z_0)}. Here \alpha(F,z), \gamma(F,z) are standard functions in point estimates.

Suppose F(z) is a square-free polynomial of degree $d$ and L-bit integer coefficients. Using our new algorithm, we can compute a n-bit absolute approximation of any real root of F(z), starting from a robust approximate zero z_0, in time O(d log(dL) M(d^2(L+log d)) +dM(dn))$, where $M(n)$ is the complexity of multiplying $n$-bit integers.

(Joint work with Zilin Du and Chee Yap, based upon the paper presented at ESA'05.)