Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
From MaRDI portal
Publication:1977146
DOI10.1006/jcom.1999.0532zbMath1041.65043OpenAlexW2076304423MaRDI QIDQ1977146
Publication date: 2000
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/262f1db608908da5a69d07fd20b83563ca0b1b45
Analysis of algorithms (68W40) 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) Real rational functions (26C15)
Related Items
Root radii and subdivision for polynomial root-finding, Near optimal subdivision algorithms for real root isolation, A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration, Fast Cauchy sum algorithms for polynomial zeros and matrix eigenvalues, Fast evaluation and root finding for polynomials with floating-point coefficients, The complexity of subdivision for diameter-distance tests, 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, Nearly optimal refinement of real roots of a univariate polynomial, Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation, A generic position based method for real root isolation of zero-dimensional polynomial systems, A new and novel method for computing an upper bound on the distance of an approximate zero from an exact zero of a univariate polynomial, Univariate real root isolation in an extension field and applications, Generalizations of Gershgorin disks and polynomial zeros, Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding, New progress in real and complex polynomial root-finding, A new proximity test for polynomial zeros, On the stability of computing polynomial roots via confederate linearizations, Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions, New Practical Advances in Polynomial Root Clustering, Accelerated subdivision for clustering roots of polynomials given by evaluation oracles, On the efficient global dynamics of Newton’s method for complex polynomials, 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
Uses Software
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
- Simple algorithms for approximating all roots of a polynomial with real roots
- Über das Newtonsche Verfahren
- Multiplication is the easiest nontrivial arithmetic function
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Unified complexity analysis for Newton LP methods
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)]
- A bibliography on roots of polynomials
- Complexity of Bezout's theorem. V: Polynomial time
- A quadtree algorithm for template matching on a pyramid computer
- The DQR algorithm, basic theory, convergence, and conditional stability
- A modified fast Fourier transform for polynomial evaluation and the Jenkins-Traub algorithm
- Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros
- Weyl's quadtree algorithm for the unsymmetric eigenvalue problem
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Bisection acceleration for the symmetric tridiagonal eigenvalue problem
- On isolation of real and nearly real zeros of a univariate polynomial and its splitting into factors
- Complexity of Bezout's theorem. III: Condition number and packing
- A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
- Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
- Circular arithmetic and the determination of polynomial zeros
- An efficient algorithm for determining the convex hull of a finite planar set
- Generalizations of Laguerre’s Method: Higher Order Methods
- A Machine Method for Solving Polynomial Equations
- A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
- Complexity of Computations with Matrices and Polynomials
- Complexity of Bezout's Theorem I: Geometric Aspects
- Evaluating Polynomials at Fixed Sets of Points
- Some modifications of Laguerre's method
- Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real
- Polynomial Root-Finding Algorithms and Branched Covers
- Remark on Algorithms to Find Roots of Polynomials
- Solving a Polynomial Equation: Some History and Recent Progress
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- A Numerical Method for Locating the Zeros of an Analytic Function
- The Simultaneous Newton Improvement of a Complete Set of Approximate Factors of a Polynomial
- A root-finding algorithm based on Newton's method
