A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
type: Item
instance of: scholarly article
title: A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
zbMATH Open document ID: 1383.65043
author: Ruben Becker
author: Michael Sagraloff
author: Vikram Sharma
author: Chee K. Yap
published in: Journal of Symbolic Computation
publication date: 2017-11-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/1509.06231
Mathematics Subject Classification ID: 65H04
Mathematics Subject Classification ID: 65E05
Mathematics Subject Classification ID: 30C15
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 6811340
zbMATH Keywords: root finding
zbMATH Keywords: root isolation
zbMATH Keywords: approximate arithmetic
zbMATH Keywords: certified computation
zbMATH Keywords: complexity analysis
zbMATH Keywords: complex roots
zbMATH Keywords: subdivision methods
zbMATH Keywords: algorithm
zbMATH Keywords: error bound
zbMATH Keywords: quadtree construction of Weyl
zbMATH Keywords: Pellet's theorem
zbMATH Keywords: Graeffe iteration
zbMATH Keywords: quadratic convergence
describes a project that uses: ISOLATE
describes a project that uses: Eigensolve
describes a project that uses: SqFreeEVAL
describes a project that uses: na20
describes a project that uses: ANewDsc
MaRDI profile type: Publication
OpenAlex ID: W2964285479
arXiv ID: 1509.06231
cites work: Quadratic interval refinement for real roots
cites work: Q3535915
cites work: Notes on the Graeffe Method of Root Squaring
cites work: Design, analysis, and implementation of a multiprecision polynomial rootfinder
cites work: Solving secular and polynomial equations: a multiprecision algorithm
cites work: SqFreeEVAL: An (almost) optimal real-root isolation algorithm
cites work: Continued fraction real root isolation using the Hong root bound
cites work: Q4234241
cites work: Q3447174
cites work: Computer Algebra in Scientific Computing
cites work: An iterated eigenvalue algorithm for approximating roots of univariate polynomials
cites work: On location and approximation of clusters of zeros of analytic functions
cites work: Q4072022
cites work: Dandelin, Lobacevskii, or Graeffe
cites work: Root refinement for real polynomials using quadratic interval refinement
cites work: Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
cites work: Computing Real Roots of Real Polynomials ... and now For Real!
cites work: A 2002 update of the supplementary bibliography on roots of polynomials
cites work: Numerical methods for roots of polynomials. Part I
cites work: Efficient polynomial root-refiners: a survey and new record efficiency estimates
cites work: Numerical methods for roots of polynomials. II
cites work: From approximate factorization to root isolation with application to cylindrical algebraic decomposition
cites work: On the complexity of isolating real roots and computing with certainty the topological degree
cites work: An efficient algorithm for the complex roots problem
cites work: Solving a Polynomial Equation: Some History and Recent Progress
cites work: Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
cites work: Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
cites work: On the boolean complexity of real root refinement
cites work: Accelerated approximation of the complex roots of a univariate polynomial
cites work: The location of the zeros of the higher order derivatives of a polynomial
cites work: An Exact Method for Finding the Roots of a Complex Polynomial
cites work: Q4779788
cites work: On the worst-case arithmetic complexity of approximating zeros of polynomials
cites work: Efficient isolation of polynomial's real roots.
cites work: When Newton meets Descartes
cites work: A near-optimal algorithm for computing real roots of sparse polynomials
cites work: On the complexity of the Descartes method when using approximate arithmetic
cites work: Computing real roots of real polynomials
cites work: A simple but exact and efficient algorithm for complex root isolation
cites work: Q3325040
cites work: Complexity of real root isolation using continued fractions
cites work: Near optimal subdivision algorithms for real root isolation
cites work: Real root isolation for exp-log-arctan functions

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: Improved bounds for the CF algorithm

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: On the complexity of real root isolation using continued fractions

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: Q3333131

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: Q4406533

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: Finding a cluster of zeros of univariate polynomials

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: Q4953977

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (cites work)
cites work: Analytic Root Clustering: A Complete Algorithm Using Soft Zero Tests

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (DOI)
DOI: 10.1016/J.JSC.2017.03.009