On the worst-case arithmetic complexity of approximating zeros of polynomials
type: Item
instance of: scholarly article
title: On the worst-case arithmetic complexity of approximating zeros of polynomials
zbMATH Open document ID: 0642.65031
DOI: 10.1016/0885-064X(87)90022-7
author: James Renegar
published in: Journal of Complexity
publication date: 1987-01-01T00:00:00Z
review text: 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.
reviewed by: S.Filippi
Mathematics Subject Classification ID: 65H05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4046964
zbMATH Keywords: zeros of polynomials
zbMATH Keywords: worst-case computational complexity
zbMATH Keywords: Newton's method
zbMATH Keywords: Schur-Cohn algorithm
zbMATH Keywords: upper bounds
MaRDI profile type: MaRDI publication profile
cites work: Q4190138
cites work: An Algorithm for the Machine Calculation of Complex Fourier Series
cites work: Q4072022
cites work: Q5590393
cites work: A Generalization of a Theorem of Bôcher
cites work: Numerics of analytic functions and complexity
cites work: The fundamental theorem of algebra and complexity theory
cites work: On the efficiency of algorithms of analysis
cites work: Q4720691
cites work: Q5601336
Recommended article: On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
Recommended article: Sequential and parallel complexity of approximate evaluation of polynomial zeros
Recommended article: On the Complexity of Polynomial Zeros
Recommended article: Algebraic complexity of computing polynomial zeros
Recommended article: On the cost of computing roots of polynomials
description: scientific article; zbMATH DE number 4046964