A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
From MaRDI portal
Publication:1680157
DOI10.1016/j.jsc.2017.03.009zbMath1383.65043arXiv1509.06231OpenAlexW2964285479MaRDI QIDQ1680157
Michael Sagraloff, Ruben Becker, Vikram Sharma, Chee-Keng Yap
Publication date: 22 November 2017
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.06231
algorithmerror boundquadratic convergencecomplexity analysisroot findingcomplex rootsroot isolationsubdivision methodsapproximate arithmeticcertified computationGraeffe iterationPellet's theoremquadtree construction of Weyl
Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)
Related Items
Affine equivalences of trigonometric curves, Root radii and subdivision for polynomial root-finding, On μ-symmetric polynomials, Polynomials Whose Zeros Are Powers of a Given Polynomial’s Zeros, A symbolic-numerical algorithm for isolating real roots of certain radical expressions, Fast Cauchy sum algorithms for polynomial zeros and matrix eigenvalues, Isolating clusters of zeros of analytic systems using arbitrary-degree inflation, Fast evaluation and root finding for polynomials with floating-point coefficients, Clustering complex zeros of triangular systems of polynomials, Certified Hermite Matrices from Approximate Roots - Univariate Case, New Practical Advances in Polynomial Root Clustering, Accelerated subdivision for clustering roots of polynomials given by evaluation oracles, Bounds for polynomials on algebraic numbers and application to curve topology
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved bounds for the CF algorithm
- Efficient polynomial root-refiners: a survey and new record efficiency estimates
- Root refinement for real polynomials using quadratic interval refinement
- Computing real roots of real polynomials
- Continued fraction real root isolation using the Hong root bound
- SqFreeEVAL: An (almost) optimal real-root isolation algorithm
- An iterated eigenvalue algorithm for approximating roots of univariate polynomials
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- On the complexity of isolating real roots and computing with certainty the topological degree
- Real root isolation for exp-log-arctan functions
- Numerical methods for roots of polynomials. Part I
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)]
- Efficient isolation of polynomial's real roots.
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Finding a cluster of zeros of univariate polynomials
- A 2002 update of the supplementary bibliography on roots of polynomials
- Numerical methods for roots of polynomials. II
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Solving secular and polynomial equations: a multiprecision algorithm
- Complexity of real root isolation using continued fractions
- On the complexity of the Descartes method when using approximate arithmetic
- On the complexity of real root isolation using continued fractions
- On location and approximation of clusters of zeros of analytic functions
- An efficient algorithm for the complex roots problem
- Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
- Accelerated approximation of the complex roots of a univariate polynomial
- Near Optimal Subdivision Algorithms for Real Root Isolation
- On the boolean complexity of real root refinement
- Computing Real Roots of Real Polynomials ... and now For Real!
- Dandelin, Lobacevskii, or Graeffe
- A near-optimal algorithm for computing real roots of sparse polynomials
- An Exact Method for Finding the Roots of a Complex Polynomial
- A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
- The location of the zeros of the higher order derivatives of a polynomial
- Solving a Polynomial Equation: Some History and Recent Progress
- When Newton meets Descartes
- A simple but exact and efficient algorithm for complex root isolation
- Quadratic interval refinement for real roots
- Analytic Root Clustering: A Complete Algorithm Using Soft Zero Tests
- Computer Algebra in Scientific Computing
- Notes on the Graeffe Method of Root Squaring
