Optimal and nearly optimal algorithms for approximating polynomial zeros
type: Item
instance of: scholarly article
title: Optimal and nearly optimal algorithms for approximating polynomial zeros
zbMATH Open document ID: 0859.65045
DOI: 10.1016/0898-1221(96)00080-6
publication date: 1997-03-25T00:00:00Z
review text: The author presents a new algorithm for approximating all complex zeros of a polynomial. The new algorithm is shown to be superior to the previous best algorithms -- in fact it is shown to be asymptotically optimal. Parallel aspects are also addressed and, even though no results on a parallel implementation are reported, the algorithm is expected to parallelize well.
Mathematics Subject Classification ID: 65H05
Mathematics Subject Classification ID: 30C15
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 915159
zbMATH Keywords: complex polynomial zeros
zbMATH Keywords: parallel algorithms
zbMATH Keywords: computational complexity
author: Victor Y. Pan
reviewed by: Claus Bendtsen
MaRDI profile type: Publication
full work available at URL: 0898-1221(96)00080-6
OpenAlex ID: W2155969572
cites work: Sequential and parallel complexity of approximate evaluation of polynomial zeros
cites work: Specified precision polynomial root isolation is in NC
cites work: On the Complexity of Polynomial Zeros
cites work: Q4234125
cites work: A quadtree algorithm for template matching on a pyramid computer
cites work: Weyl's quadtree algorithm for the unsymmetric eigenvalue problem
cites work: Q5779155
cites work: Q5572275
cites work: Q5563347
cites work: Q5653524
cites work: Q4072022
cites work: The fundamental theorem of algebra and complexity theory
cites work: Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
cites work: Q4773298
cites work: Q4385522
cites work: Q5590393
cites work: On the worst-case arithmetic complexity of approximating zeros of polynomials
cites work: Q3128886
cites work: Q3128885
cites work: A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
cites work: Simple algorithms for approximating all roots of a polynomial with real roots
cites work: Q3138975
cites work: New Resultant Inequalities and Complex Polynomial Factorization
cites work: A Generalization of a Theorem of Bôcher
cites work: Q5341755
cites work: Fast multiplication of large numbers
cites work: Q4138141
cites work: Q3935355
cites work: Q4314299
cites work: Q3279563
cites work: Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
cites work: Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
cites work: A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
cites work: Q3816922
cites work: Polynomial Root-Finding Algorithms and Branched Covers
cites work: Complexity of Bezout's Theorem I: Geometric Aspects
cites work: Q3135179
cites work: Complexity of Bezout's theorem. III: Condition number and packing
cites work: Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
cites work: Complexity of Bezout's theorem. V: Polynomial time
cites work: Upperbounds for roots of polynomials
cites work: Power Sum Method and the Approximative Solution of Algebraic Equations
cites work: Q5835072
cites work: Quasi-gcd computations
cites work: Q4055156
cites work: How to multiply matrices faster
cites work: Polynomial division and its computational complexity
cites work: A Numerical Method for Locating the Zeros of an Analytic Function
cites work: Über das Newtonsche Verfahren
cites work: Optimal Size Integer Division Circuits
cites work: The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
cites work: Parametrization of Newton's iteration for computations with structured matrices and applications
cites work: Q3732964
cites work: Complexity of parallel matrix computations
cites work: Parallel solution of Toeplitzlike linear systems
cites work: Q4234216
cites work: Q4177796
cites work: Q3359644
published in: Computers & Mathematics with Applications
Recommended article: On the worst-case arithmetic complexity of approximating zeros of polynomials

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: An Optimization Framework for Polynomial Zerofinders
Similarity Score: 0.92622316
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: On the zero-free polynomial approximation problem
Similarity Score: 0.92369634
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: On computational efficiency of the iterative methods for the simultaneous approximation of polynomial zeros
Similarity Score: 0.91886634
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
Similarity Score: 0.9184288
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: Simultaneous zero-free approximation and universal optimal polynomial approximants
Similarity Score: 0.9174029
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
Similarity Score: 0.9165417
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: Algorithms for near solutions to polynomial equations
Similarity Score: 0.9148965
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: On the zeros of polynomials of best approximation
Similarity Score: 0.9135583
Recommender Run: Recommender Run 3

Optimal and nearly optimal algorithms for approximating polynomial zeros (Recommended article)
Recommended article: On Halley-Like Algorithms for Simultaneous Approximation of Polynomial Complex Zeros
Similarity Score: 0.9128035
Recommender Run: Recommender Run 3