On the worst-case arithmetic complexity of approximating zeros of polynomials
From MaRDI portal
For complex polynomials \(P_ d(R)\) of degree \(d\geq 2\) with all zeros \(z_ i\) satisfying \(| z_ i| \leq R\) it is shown that the worst- case computational complexity of obtaining an \(\epsilon\)-approximation for the zeros of \(P_ d(R)\) is O(log log(R/\(\epsilon)\)). Further a new algorithm, based on Newton's method, and using the Schur-Cohn algorithm, giving upper bounds is derived.
Recommendations
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- On the Complexity of Polynomial Zeros
- Algebraic complexity of computing polynomial zeros
- On the cost of computing roots of polynomials
Cites work
- A Generalization of a Theorem of Bôcher
- An Algorithm for the Machine Calculation of Complex Fourier Series
- scientific article; zbMATH DE number 3489473 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 3992817 (Why is no real title available?)
- scientific article; zbMATH DE number 3309631 (Why is no real title available?)
- scientific article; zbMATH DE number 3321949 (Why is no real title available?)
- Numerics of analytic functions and complexity
- On the efficiency of algorithms of analysis
- The fundamental theorem of algebra and complexity theory
Cited in
(59)- A new solution method for the finite-horizon discrete-time EOQ problem
- Algebraic complexity of computing polynomial zeros
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- Complexity of functions: Some questions, conjectures, and results
- On the evaluation of the eigenvalues of a banded Toeplitz block matrix
- Practical improvement of the divide-and-conquer eigenvalue algorithms
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Complexity lower bounds for approximation algebraic computation trees
- 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
- An adaptive subdivision method for root finding of univariate polynomials
- On solving univariate sparse polynomials in logarithmic time
- Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
- Using the method of dual quadratic solutions to solve systems of polynomial equations in the complex domain
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Accelerated subdivision for clustering roots of polynomials given by evaluation oracles
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- A note on the finite variance of the averaging function for polynomial system solving
- On the convergence of Halley's method for multiple polynomial zeros
- Real polynomial root-finding by means of matrix and polynomial iterations
- Accelerated approximation of the complex roots and factors of a univariate polynomial
- Newton's method in practice: finding all roots of polynomials of degree one million efficiently
- Robust approximate zeros in Banach space
- Complexity and algorithms for nonlinear optimization problems
- Near optimal subdivision algorithms for real root isolation
- A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
- A tight bound for approximating the square root
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- scientific article; zbMATH DE number 1003257 (Why is no real title available?)
- Finding the number of roots of a polynomial in a plane region using the winding number
- On the cost of computing roots of polynomials
- On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
- scientific article; zbMATH DE number 3928209 (Why is no real title available?)
- scientific article; zbMATH DE number 4037051 (Why is no real title available?)
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Complexity of path-following methods for the eigenvalue problem
- Efficient polynomial root-refiners: a survey and new record efficiency estimates
- A geometric algorithm for winding number computation with complexity analysis
- On simple double zeros and badly conditioned zeros of analytic functions of 𝑛 variables
- Geometry of polynomials and root-finding via path-lifting
- Computing real roots of real polynomials
- Newton's method and the computational complexity of the fundamental theorem of algebra
- New Practical Advances in Polynomial Root Clustering
- How to be sure of finding a root of a complex polynomial using Newton's method
- Probabilistic analyses of condition numbers
- Average-case results for zero finding
- On the efficient global dynamics of Newton’s method for complex polynomials
- Kronecker's and Newton's approaches to solving: a first comparison
- Fast Cauchy sum algorithms for polynomial zeros and matrix eigenvalues
- Newton's method in practice. II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees
- Rigid continuation paths II. structured polynomial systems
- Fast linear homotopy to find approximate zeros of polynomial systems
- Root-Squaring for Root-Finding
- A new fast root-finder for black box polynomials
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- Simple algorithms for approximating all roots of a polynomial with real roots
- Nearly optimal refinement of real roots of a univariate polynomial
- General local convergence theory for a class of iterative processes and its applications to Newton's method
This page was built for publication: On the worst-case arithmetic complexity of approximating zeros of polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101184)
