On the Geometry of Graeffe Iteration
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
1999
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908600157339648 |
|---|---|
| author | Malajovich, Gregorio Zubelli, Jorge P. |
| author_facet | Malajovich, Gregorio Zubelli, Jorge P. |
| contents | A new version of the Graeffe algorithm for finding all the roots of univariate complex polynomials is proposed. It is obtained from the classical algorithm by a process analogous to renormalization of dynamical systems. This iteration is called Renormalized Graeffe Iteration.
It is globally convergent, with probability 1. All quantities involved in the computation are bounded, once the initial polynomial is given (with probability 1). This implies remarkable stability properties for the new algorithm, thus overcoming known limitations of the classical Graeffe algorithm. If we start with a degree-$d$ polynomial, each renormalized Graeffe iteration costs $O(d^2)$ arithmetic operations, with memory $O(d)$. A probabilistic global complexity bound is given. The case of univariate real polynomials is briefly discussed. A numerical implementation of the algorithm presented herein allowed us to solve random polynomials of degree up to 1000. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_9908149 |
| institution | arXiv |
| publishDate | 1999 |
| record_format | arxiv |
| spellingShingle | On the Geometry of Graeffe Iteration Malajovich, Gregorio Zubelli, Jorge P. Numerical Analysis A new version of the Graeffe algorithm for finding all the roots of univariate complex polynomials is proposed. It is obtained from the classical algorithm by a process analogous to renormalization of dynamical systems. This iteration is called Renormalized Graeffe Iteration. It is globally convergent, with probability 1. All quantities involved in the computation are bounded, once the initial polynomial is given (with probability 1). This implies remarkable stability properties for the new algorithm, thus overcoming known limitations of the classical Graeffe algorithm. If we start with a degree-$d$ polynomial, each renormalized Graeffe iteration costs $O(d^2)$ arithmetic operations, with memory $O(d)$. A probabilistic global complexity bound is given. The case of univariate real polynomials is briefly discussed. A numerical implementation of the algorithm presented herein allowed us to solve random polynomials of degree up to 1000. |
| title | On the Geometry of Graeffe Iteration |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/math/9908149 |