Accelerated approximation of the complex roots and factors of a univariate polynomial

DOI10.1016/j.tcs.2017.03.030zbMath1375.65066arXiv1501.05392OpenAlexW2962978702MaRDI QIDQ2357367

Elias P. Tsigaridas, Pan, Victor Y.

Publication date: 13 June 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexityalgorithmrootsnumerical stabilitycomplexity boundpolynomial equationpower sumsroot-findingcomplex univariate polynomialroot-refinement

Mathematics Subject Classification ID

Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)

Related Items

\texttt{PTOPO}: computing the geometry and the topology of parametric curves, Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation, An adaptive subdivision method for root finding of univariate polynomials, A nearly optimal algorithm to decompose binary forms, Multilinear polynomial systems: root isolation and bit complexity, Real polynomial root-finding by means of matrix and polynomial iterations

Uses Software

• na20
• na10
• Eigensolve

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient polynomial root-refiners: a survey and new record efficiency estimates
• Numerical computation of polynomial zeros by means of Aberth's method
• An iterated eigenvalue algorithm for approximating roots of univariate polynomials
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Numerical methods for roots of polynomials. Part I
• Nearly optimal refinement of real roots of a univariate polynomial
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Convergence conditions of some methods for the simultaneous computation of polynomial zero
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)]
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• A 2002 update of the supplementary bibliography on roots of polynomials
• Numerical methods for roots of polynomials. II
• A fast version of the Schur-Cohn algorithm.
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• Solving secular and polynomial equations: a multiprecision algorithm
• Real and Complex Polynomial Root-Finding by Means of Eigen-Solving
• On the boolean complexity of real root refinement
• A Newton-Raphson method for moving-average spectral factorization using the Euclid algorithm
• Dandelin, Lobacevskii, or Graeffe
• The Euclid algorithm and the fast computation of cross-covariance and autocovariance sequences
• Fast approximate computations with Cauchy matrices and polynomials
• Factorization of the Covariance Generating Function of a Pure Moving Average Process