Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation

DOI10.1007/978-3-319-56932-1_23zbMATH Open1397.65069arXiv1705.00729OpenAlexW2963014696MaRDI QIDQ4610020FDOQ4610020

Victor Y. Pan

Publication date: 5 April 2018

Published in: Applications of Computer Algebra (Search for Journal in Brave)

Abstract: We propose a new simple but nearly optimal algorithm for the approximation of all sufficiently well isolated complex roots and root clusters of a univariate polynomial. Quite typically the known root-finders at first compute some crude but reasonably good approximations to well-conditioned roots (that is, those isolated from the other roots) and then refine the approximations very fast, by using Boolean time which is nearly optimal, up to a polylogarithmic factor. By combining and extending some old root-finding techniques, the geometry of the complex plane, and randomized parametrization, we accelerate the initial stage of obtaining crude to all well-conditioned simple and multiple roots as well as isolated root clusters. Our algorithm performs this stage at a Boolean cost dominated by the nearly optimal cost of subsequent refinement of these approximations, which we can perform concurrently, with minimum processor communication and synchronization. Our techniques are quite simple and elementary; their power and application range may increase in their combination with the known efficient root-finding methods.

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

zbMATH Keywords

polynomialsroot-findingroot isolationroot radii

Mathematics Subject Classification ID

Numerical computation of roots of polynomial equations (65H04)

Cites Work

• An efficient algorithm for determining the convex hull of a finite planar set
• Numerical methods for roots of polynomials. II
• Tangent Graeffe iteration
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
• Recherches sur la méthode de Graeffe et les zéros des polynômes et des séries de Laurent
• On the boolean complexity of real root refinement
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• Nearly optimal refinement of real roots of a univariate polynomial
• Upperbounds for roots of polynomials
• Accelerated approximation of the complex roots of a univariate polynomial
• Dandelin, Lobacevskii, or Graeffe
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• Polynomial Real Root Isolation by Means of Root Radii Approximation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Accelerated approximation of the complex roots of a univariate polynomial
• Optimizing a particular real root of a polynomial by a special cylindrical algebraic decomposition
• Nearly optimal refinement of real roots of a univariate polynomial

This page was built for publication: Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation

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