Tangent Graeffe iteration

DOI10.1007/S002110100278MaRDI QIDQ5952132zbMATH OpenOpenAlexFDO

Authors Gregorio Malajovich, J. P. Zubelli

Publication date 29 September 2002

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9908150

zbMATH Keywords

root of polynomialtangent Graeffe algorithmunivariate complex polynomial

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Direct numerical methods for linear systems and matrix inversion (65F05) Numerical computation of solutions to single equations (65H05)

Abstract: Graeffe iteration was the choice algorithm for solving univariate polynomials in the XIX-th and early XX-th century. In this paper, a new variation of Graeffe iteration is given, suitable to IEEE floating-point arithmetics of modern digital computers. We prove that under a certain generic assumption the proposed algorithm converges. We also estimate the error after N iterations and the running cost. The main ideas from which this algorithm is built are: classical Graeffe iteration and Newton Diagrams, changes of scale (renormalization), and replacement of a difference technique by a differentiation one. The algorithm was implemented successfully and a number of numerical experiments are displayed.

Review text

The authors present a version of renormalized Graeffe's algorithm, also considered in their previous paper [J. Complexity 17, No. 3, 541-573 (2001; reviewed above)], for solving real and complex univariate polynomials. Recall that Graeffe iteration maps a degree \(d\) polynomial \(f(x)\) into the degree \(d\) polynomial \[ Gf(x)=(-1)^d f(\sqrt{x}) f(-\sqrt{x}). \] and that, if \(\zeta_1,\zeta_2,\ldots,\zeta_d\) are the roots of \(f\), then the roots of \(Gf\) are \(\zeta_1^2,\zeta_2^2,\ldots,\zeta_d^2.\)

Recommendations

• On the geometry of Graeffe iteration
• scientific article; zbMATH DE number 810968
• Implementing the tangent Graeffe root finding method
• A generalized Graeffe's iteration for evaluating polynomials and rational functions
• scientific article; zbMATH DE number 4124899

Cited in

(14)

• Computations with infinite Toeplitz matrices and polynomials
• Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots
• Real polynomial root-finding by means of matrix and polynomial iterations
• A generalized Graeffe's iteration for evaluating polynomials and rational functions
• Deterministic root finding over finite fields using Graeffe transforms
• Simple and nearly optimal polynomial root-finding by means of root radii approximation
• Implementing the tangent Graeffe root finding method
• Computing one billion roots using the tangent Graeffe method
• On the geometry of 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
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding

This page was built for publication: Tangent Graeffe iteration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5952132)