On the geometry of Graeffe iteration
From MaRDI portal
Abstract: 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- polynomial, each renormalized Graeffe iteration costs arithmetic operations, with memory . 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.
Let \(f\) be a univariate polynomial of degree \(d\). Its Graeffe iterate is defined by \[ Gf(x)=(-1)^d f(\sqrt{x}) f(-\sqrt{x}). \] Using a renormalized variant of Graeffe iteration, the authors design an algorithm which is globally convergent, with probability 1, for finding the absolute values of the roots of univariate complex polynomials.
Recommendations
Cites work
- A fast and stable algorithm for splitting polynomials
- A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
- An efficient algorithm for the complex roots problem
- Complex Dynamics and Renormalization (AM-135)
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Condition number analysis for sparse polynomial systems
- Dandelin, Lobacevskii, or Graeffe
- Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
- Differential Identities
- Graeffe's, Chebyshev-like, and Cardinal's processes for splitting a polynomial into factors
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 4137244 (Why is no real title available?)
- scientific article; zbMATH DE number 4096783 (Why is no real title available?)
- scientific article; zbMATH DE number 3757661 (Why is no real title available?)
- scientific article; zbMATH DE number 53149 (Why is no real title available?)
- scientific article; zbMATH DE number 3489473 (Why is no real title available?)
- scientific article; zbMATH DE number 4124899 (Why is no real title available?)
- scientific article; zbMATH DE number 467146 (Why is no real title available?)
- scientific article; zbMATH DE number 503393 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- scientific article; zbMATH DE number 1049347 (Why is no real title available?)
- scientific article; zbMATH DE number 953013 (Why is no real title available?)
- scientific article; zbMATH DE number 953017 (Why is no real title available?)
- scientific article; zbMATH DE number 953021 (Why is no real title available?)
- scientific article; zbMATH DE number 953047 (Why is no real title available?)
- scientific article; zbMATH DE number 846277 (Why is no real title available?)
- scientific article; zbMATH DE number 3291602 (Why is no real title available?)
- Newton iteration towards a cluster of polynomial zeros
- On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
- On isolation of real and nearly real zeros of a univariate polynomial and its splitting into factors
- On the cost of approximating all roots of a complex polynomial
- On the Problem of Runs
- On the Reduction of Number Range in the Use of the Graeffe Process
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Polynomial Roots from Companion Matrix Eigenvalues
- Pseudozeros of polynomials and pseudospectra of companion matrices
- Quantitative universality for a class of nonlinear transformations
- Remark on Algorithms to Find Roots of Polynomials
- Resultant Procedure and the Mechanization of the Graeffe Process
- Solving a Polynomial Equation: Some History and Recent Progress
- Solving special polynomial systems by using structured matrices and algebraic residues
- Topological complexity of zero-finding
Cited in
(16)- A geometric interpretation of Darroch and Ratcliff's generalized iterative scaling
- Comment on ``Nonlinear differential algorithm to compute all the zeros of a generic polynomial [J. Math. Phys. 57, 083508 (2016)]
- A generalized Graeffe's iteration for evaluating polynomials and rational functions
- On finding the largest root of a polynomial
- Application of Baker's method to the Dandelin-Graeffe's method
- scientific article; zbMATH DE number 4124899 (Why is no real title available?)
- scientific article; zbMATH DE number 810968 (Why is no real title available?)
- New progress in real and complex polynomial root-finding
- Approximate calculation of sums. II: Gaussian type quadrature
- Tangent Graeffe iteration
- High probability analysis of the condition number of sparse polynomial systems
- Fast evaluation and root finding for polynomials with floating-point coefficients
- Root-Squaring for Root-Finding
- Fast evaluation and root finding for polynomials with floating-point coefficients
- A new fast root-finder for black box polynomials
- A geometric construction of iterative formulas of order three
This page was built for publication: On the geometry of Graeffe iteration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5949383)
