Optimal and nearly optimal algorithms for approximating polynomial zeros

DOI10.1016/0898-1221(96)00080-6zbMath0859.65045OpenAlexW2155969572MaRDI QIDQ1921261

Pan, Victor Y.

Publication date: 25 March 1997

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(96)00080-6

zbMATH Keywords

computational complexityparallel algorithmscomplex polynomial zeros

Mathematics Subject Classification ID

Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05) Complexity and performance of numerical algorithms (65Y20)

Related Items

Polynomial factorization through Toeplitz matrix computations, Near optimal subdivision algorithms for real root isolation, The amended DSeSC power method for polynomial root-finding, Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Complexity of path-following methods for the eigenvalue problem, Rigid continuation paths II. structured polynomial systems, Nearly optimal refinement of real roots of a univariate polynomial, On the isotopic meshing of an algebraic implicit surface, Efficient polynomial root-refiners: a survey and new record efficiency estimates, Rigorous uniform approximation of D-finite functions using Chebyshev expansions, Inverse functions of polynomials and its applications to initialize the search of solutions of polynomials and polynomial systems, SqFreeEVAL: An (almost) optimal real-root isolation algorithm, On the convergence condition of generalized root iterations for the inclusion of polynomial zeros, Root-finding by expansion with independent constraints, Root refinement for real polynomials using quadratic interval refinement, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., Lifting/descending processes for polynomial zeros., A fast and stable algorithm for splitting polynomials, On new higher order families of simultaneous methods for finding polynomial zeros, A family of root-finding methods with accelerated convergence, Root finding with threshold circuits, Computing a Hurwitz factorization of a polynomial, An efficient higher order family of root finders, Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding, On the geometry of Graeffe iteration, A higher order family for the simultaneous inclusion of multiple zeros of polynomials, Unnamed Item, Unnamed Item, Sigmoid-like functions and root finding methods, First-order orbit queries, On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond, Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs., Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)], The polynomial pivots as initial values for a new root-finding iterative method, Computation of approximate polynomial GCDs and an extension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple algorithms for approximating all roots of a polynomial with real roots
• Über das Newtonsche Verfahren
• How to multiply matrices faster
• Quasi-gcd computations
• Polynomial division and its computational complexity
• Sequential and parallel complexity of approximate evaluation of polynomial zeros
• Complexity of parallel matrix computations
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Parallel solution of Toeplitzlike linear systems
• Parametrization of Newton's iteration for computations with structured matrices and applications
• Specified precision polynomial root isolation is in NC
• Complexity of Bezout's theorem. V: Polynomial time
• A quadtree algorithm for template matching on a pyramid computer
• Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
• Weyl's quadtree algorithm for the unsymmetric eigenvalue problem
• Complexity of Bezout's theorem. III: Condition number and packing
• Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
• Upperbounds for roots of polynomials
• Fast multiplication of large numbers
• Optimal Size Integer Division Circuits
• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
• The fundamental theorem of algebra and complexity theory
• On the Complexity of Polynomial Zeros
• Complexity of Bezout's Theorem I: Geometric Aspects
• Power Sum Method and the Approximative Solution of Algebraic Equations
• A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
• Polynomial Root-Finding Algorithms and Branched Covers
• New Resultant Inequalities and Complex Polynomial Factorization
• Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• A Numerical Method for Locating the Zeros of an Analytic Function
• A Generalization of a Theorem of Bôcher
• The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis