Name
Abstract | ||
|---|---|---|
Smale’s notion of an approximate zero of an analytic function f: C →C 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∈ C satisfies α(f,z0)z0 is a robust approximate zero, with the associated zero z* lying in the closed disc ${\overline B}(z_{0},\frac{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 z0, in time O[dM(n+d2(L+lg d)lg(n+L))], where M(n) is the complexity of multiplying n-bit integers. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11561071_77 | ESA |
Keywords | Field | DocType |
n-bit integer,stronger notion,point estimate,n-bit absolute approximation,corresponding robust point estimate,approximate zero,robust approximate zero,l-bit integer square-free polynomial,bigfloat z0,c satisfies,satisfiability,analytic function,point estimation | Integer,Discrete mathematics,Combinatorics,Pointer machine,Polynomial,Analytic function,Operator (computer programming),Mathematics,Newton's method | Conference |
Volume | ISSN | ISBN |
3669 | 0302-9743 | 3-540-29118-0 |
Citations | PageRank | References |
7 | 0.49 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikram Sharma | 1 | 229 | 20.35 |
| Zilin Du | 2 | 23 | 1.95 |
| Chee-Keng Yap | 3 | 1996 | 395.32 |