Complexity Analysis of Root Clustering for a Complex Polynomial
| Autor: | Vikram Sharma, Ruben Becker, Juan Xu, Chee Yap, Michael Sagraloff |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Computer Science - Symbolic Computation
Computational Geometry (cs.CG) FOS: Computer and information sciences Discrete mathematics Settore INF/01 - Informatica 010102 general mathematics Splitting circle method 010103 numerical & computational mathematics Symbolic Computation (cs.SC) 01 natural sciences Oracle Combinatorics symbols.namesake Simple (abstract algebra) ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION symbols Computer Science - Computational Geometry 0101 mathematics Cluster analysis Newton's method Complex plane Root-finding algorithm Mathematics Complex conjugate root theorem |
| Zdroj: | ISSAC |
| DOI: | 10.1145/2930889.2930939 |
| Popis: | Let $F(z)$ be an arbitrary complex polynomial. We introduce the local root clustering problem, to compute a set of natural $\varepsilon$-clusters of roots of $F(z)$ in some box region $B_0$ in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified subdivision algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters. Our computational model assumes that arbitrarily good approximations of the coefficients of $F$ are provided by means of an oracle at the cost of reading the coefficients. Our algorithmic techniques come from a companion paper (Becker et al., 2018) and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Sch\"onhage's splitting circle method. Our algorithm is relatively simple and promises to be efficient in practice. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|