On the worst-case arithmetic complexity of approximating zeros of polynomials
From MaRDI portal
Publication:1101184
DOI10.1016/0885-064X(87)90022-7zbMath0642.65031MaRDI QIDQ1101184
Publication date: 1987
Published in: Journal of Complexity (Search for Journal in Brave)
upper boundsNewton's methodzeros of polynomialsSchur-Cohn algorithmworst-case computational complexity
Analysis of algorithms and problem complexity (68Q25) Numerical computation of solutions to single equations (65H05)
Related Items
How to be sure of finding a root of a complex polynomial using Newton's method, A tight bound for approximating the square root, Near optimal subdivision algorithms for real root isolation, Finding the number of roots of a polynomial in a plane region using the winding number, 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, 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, Complexity of path-following methods for the eigenvalue problem, 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, Nearly optimal refinement of real roots of a univariate polynomial, Fast linear homotopy to find approximate zeros of polynomial systems, Efficient polynomial root-refiners: a survey and new record efficiency estimates, A geometric algorithm for winding number computation with complexity analysis, Geometry of polynomials and root-finding via path-lifting, Complexity of functions: Some questions, conjectures, and results, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., An adaptive subdivision method for root finding of univariate polynomials, Computing real roots of real polynomials, On the evaluation of the eigenvalues of a banded Toeplitz block matrix, Practical improvement of the divide-and-conquer eigenvalue algorithms, From approximate factorization to root isolation with application to cylindrical algebraic decomposition, Newton's method and the Computational Complexity of the Fundamental Theorem of Algebra, Complexity and algorithms for nonlinear optimization problems, Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding, On solving univariate sparse polynomials in logarithmic time, Probabilistic analyses of condition numbers, Kronecker's and Newton's approaches to solving: a first comparison, A note on the finite variance of the averaging function for polynomial system solving, Average-case results for zero finding, General local convergence theory for a class of iterative processes and its applications to Newton's method, A new solution method for the finite-horizon discrete-time EOQ problem, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, Simple algorithms for approximating all roots of a polynomial with real roots, 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, 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, On the convergence of Halley's method for multiple polynomial zeros, On simple double zeros and badly conditioned zeros of analytic functions of 𝑛 variables, 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
Cites Work
- Numerics of analytic functions and complexity
- On the efficiency of algorithms of analysis
- The fundamental theorem of algebra and complexity theory
- An Algorithm for the Machine Calculation of Complex Fourier Series
- A Generalization of a Theorem of Bôcher
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
