## Abstract

Smale's notion of an approximate zero of an analytic function f : ℂ → ℂ 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 z_{0} ∈ ℂ satisfies α(f, z _{0}) < 0.02 then z_{0} is a robust approximate zero, with the associated zero z* lying in the closed disc B̄(z_{0}, 0.07/γ(f, z_{0}). Here α(f, z), γ(f, z) are standard functions in point estimates. Suppose f(z) is an L-bit integer square-free polynomial of degree d. Using our new algorithm, we can compute an n-bit absolute approximation of z* ∈ IR starting from a bigfloat Z _{0}, in time O[dM(n + d^{2}(L + lg d) lg(n + L))], where M(n) is the complexity of multiplying n-bit integers.

Original language | English (US) |
---|---|

Pages (from-to) | 874-886 |

Number of pages | 13 |

Journal | Lecture Notes in Computer Science |

Volume | 3669 |

DOIs | |

State | Published - 2005 |

Event | 13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain Duration: Oct 3 2005 → Oct 6 2005 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)