Complexity Analysis of Root Clustering for a Complex Polynomial

DOI10.1145/2930889.2930939MaRDI QIDQ2985810zbMATH OpenOpenAlexFDO

Authors

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

complexity of rootsGraeffe iterationlocal complexityNewton methodPellet testroot clusteringroot findingroot isolation

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) Numerical computation of roots of polynomial equations (65H04) Complexity and performance of numerical algorithms (65Y20) Programming involving graphs or networks (90C35)

Abstract: Let $F(z)$ be an arbitrary complex polynomial. We introduce the local root clustering problem, to compute a set of natural $varepsilon$-clusters of roots of $F(z)$ in some box region $B_0$ in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified subdivision algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters. Our computational model assumes that arbitrarily good approximations of the coefficients of $F$ are provided by means of an oracle at the cost of reading the coefficients. Our algorithmic techniques come from a companion paper (Becker et al., 2018) and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Sch"onhage's splitting circle method. Our algorithm is relatively simple and promises to be efficient in practice.

Recommendations

• Root clustering for convex combination of complex polynomials
• Roots of composite polynomials - an application to root clustering
• Implementation of a near-optimal complex root clustering algorithm
• Computing clustered close-roots of univariate polynomials
• On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
• New Practical Advances in Polynomial Root Clustering
• Clustering complex zeros of triangular systems of polynomials
• Root clustering of interval polynomials in the left-sector
• On the complexity of computing real radicals of polynomial systems
• On the cost of approximating all roots of a complex polynomial

Cited in

(18)

• Implementation of a near-optimal complex root clustering algorithm
• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• Clustering complex zeros of triangular systems of polynomials
• Accelerated subdivision for clustering roots of polynomials given by evaluation oracles
• Positive root isolation for poly-powers by exclusion and differentiation
• �ber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise
• New Practical Advances in Polynomial Root Clustering
• On \(\mu\)-symmetric polynomials
• Analytic root clustering: a complete algorithm using soft zero tests
• Isolating clusters of zeros of analytic systems using arbitrary-degree inflation
• A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
• Counting solutions of a polynomial system locally and exactly
• Root-Squaring for Root-Finding
• Complexity of a root clustering algorithm for holomorphic functions
• A new fast root-finder for black box polynomials
• Novel range functions via Taylor expansions and recursive Lagrange interpolation with application to real root isolation
• Rational cubic clipping with linear complexity for computing roots of polynomials
• Root radii and subdivision for polynomial root-finding

This page was built for publication: Complexity Analysis of Root Clustering for a Complex Polynomial

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