Theory Seminars at the Courant Institute
New York University

Title: Robust Approximate Zeros for Newton's Method.

Speaker: Vikram Sharma (CIMS)

Abstract:

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