Optimal and nearly optimal algorithms for approximating polynomial zeros
From MaRDI portal
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.
Recommendations
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- An Optimization Framework for Polynomial Zerofinders
- On the zero-free polynomial approximation problem
- On computational efficiency of the iterative methods for the simultaneous approximation of polynomial zeros
- On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
- Simultaneous zero-free approximation and universal optimal polynomial approximants
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Algorithms for near solutions to polynomial equations
- On the zeros of polynomials of best approximation
- On Halley-Like Algorithms for Simultaneous Approximation of Polynomial Complex Zeros
Cites work
- A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
- A Generalization of a Theorem of Bôcher
- A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
- A Numerical Method for Locating the Zeros of an Analytic Function
- A quadtree algorithm for template matching on a pyramid computer
- Complexity of Bezout's Theorem I: Geometric Aspects
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Complexity of parallel matrix computations
- Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
- Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
- Fast multiplication of large numbers
- How to multiply matrices faster
- scientific article; zbMATH DE number 1003257 (Why is no real title available?)
- scientific article; zbMATH DE number 1003258 (Why is no real title available?)
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 432841 (Why is no real title available?)
- scientific article; zbMATH DE number 3161517 (Why is no real title available?)
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- scientific article; zbMATH DE number 3965444 (Why is no real title available?)
- scientific article; zbMATH DE number 4088853 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3471577 (Why is no real title available?)
- scientific article; zbMATH DE number 3489473 (Why is no real title available?)
- scientific article; zbMATH DE number 3566175 (Why is no real title available?)
- scientific article; zbMATH DE number 3613366 (Why is no real title available?)
- scientific article; zbMATH DE number 1263253 (Why is no real title available?)
- scientific article; zbMATH DE number 1263338 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- scientific article; zbMATH DE number 1142306 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3214539 (Why is no real title available?)
- scientific article; zbMATH DE number 3279131 (Why is no real title available?)
- scientific article; zbMATH DE number 3290249 (Why is no real title available?)
- scientific article; zbMATH DE number 3309631 (Why is no real title available?)
- scientific article; zbMATH DE number 3383473 (Why is no real title available?)
- scientific article; zbMATH DE number 3039704 (Why is no real title available?)
- scientific article; zbMATH DE number 3096281 (Why is no real title available?)
- Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
- New Resultant Inequalities and Complex Polynomial Factorization
- On the Complexity of Polynomial Zeros
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Optimal Size Integer Division Circuits
- Parallel solution of Toeplitzlike linear systems
- Parametrization of Newton's iteration for computations with structured matrices and applications
- Polynomial division and its computational complexity
- Polynomial Root-Finding Algorithms and Branched Covers
- Power Sum Method and the Approximative Solution of Algebraic Equations
- Quasi-gcd computations
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- Simple algorithms for approximating all roots of a polynomial with real roots
- Specified precision polynomial root isolation is in NC
- The fundamental theorem of algebra and complexity theory
- The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
- Upperbounds for roots of polynomials
- Weyl's quadtree algorithm for the unsymmetric eigenvalue problem
- Über das Newtonsche Verfahren
Cited in
(52)- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Parallel computation of polynomial GCD and some related parallel computations over abstract fields
- Fast algorithms for zero-dimensional polynomial systems using duality
- Computation of approximate polynomial GCDs and an extension
- Polynomial factorization through Toeplitz matrix computations
- On zeros of a complex polynomial
- Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Lifting/descending processes for polynomial zeros.
- First-order orbit queries
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- The polynomial pivots as initial values for a new root-finding iterative method
- The amended DSeSC power method for polynomial root-finding
- Sorting-based localization and stable computation of zeros of a polynomial. II.
- Sorting-based localization and stable computation of zeros of a polynomial. I.
- A family of root-finding methods with accelerated convergence
- An efficient higher order family of root finders
- A higher order family for the simultaneous inclusion of multiple zeros of polynomials
- Sigmoid-like functions and root finding methods
- Near optimal subdivision algorithms for real root isolation
- Rigorous uniform approximation of D-finite functions using Chebyshev expansions
- scientific article; zbMATH DE number 1003257 (Why is no real title available?)
- scientific article; zbMATH DE number 440790 (Why is no real title available?)
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- On the Complexity of Polynomial Zeros
- Complexity of path-following methods for the eigenvalue problem
- On the isotopic meshing of an algebraic implicit surface
- Efficient polynomial root-refiners: a survey and new record efficiency estimates
- Approximate Zeros of Quadratically Convergent Algorithms
- New Resultant Inequalities and Complex Polynomial Factorization
- scientific article; zbMATH DE number 1929302 (Why is no real title available?)
- Root refinement for real polynomials using quadratic interval refinement
- Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs.
- scientific article; zbMATH DE number 7559115 (Why is no real title available?)
- The big-O problem
- Three New Rapidly Convergent Algorithms for Finding a Zero of a Function
- Computing a Hurwitz factorization of a polynomial
- On the geometry of Graeffe iteration
- Rigid continuation paths II. structured polynomial systems
- Inverse functions of polynomials and its applications to initialize the search of solutions of polynomials and polynomial systems
- Root-Squaring for Root-Finding
- SqFreeEVAL: An (almost) optimal real-root isolation algorithm
- Root-finding by expansion with independent constraints
- A new fast root-finder for black box polynomials
- A fast and stable algorithm for splitting polynomials
- Root finding with threshold circuits
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- Nearly optimal refinement of real roots of a univariate polynomial
- On the convergence condition of generalized root iterations for the inclusion of polynomial zeros
- On new higher order families of simultaneous methods for finding polynomial zeros
- Zero-clusters of polynomials: best approach in supercomputing era
This page was built for publication: Optimal and nearly optimal algorithms for approximating polynomial zeros
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1921261)
