Robust approximate zeros

Vikram Sharma, Zilin Du, Chee K. Yap

Research output: Contribution to journalConference article

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 z0 ∈ ℂ satisfies α(f, z 0) < 0.02 then z0 is a robust approximate zero, with the associated zero z* lying in the closed disc B̄(z0, 0.07/γ(f, z0). 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 + d2(L + lg d) lg(n + L))], where M(n) is the complexity of multiplying n-bit integers.

Original languageEnglish (US)
Pages (from-to)874-886
Number of pages13
JournalLecture Notes in Computer Science
Volume3669
DOIs
StatePublished - 2005
Event13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain
Duration: Oct 3 2005Oct 6 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Robust approximate zeros'. Together they form a unique fingerprint.

  • Cite this