Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
Authors:
- M. ShubMSM. Shub
- S. SmaleSSS. Smale
- 1 February 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (1) , 145-161
Abstract
This paper deals with traditional algorithms, Newton’s method and a higher order generalization due to Euler. These iterations schemes and their modifications have had a great success in solving nonlinear systems of equations. We give some understanding of this phenomenon by giving estimates of efficiency. The problem we focus on is that of finding a zero of a complex polynomial.Keywords
This publication has 6 references indexed in Scilit:
- Computational complexity. On the geometry of polynomials and a theory of cost. IAnnales Scientifiques de lʼÉcole Normale Supérieure, 1985
- The Problem of the Average Speed of the Simplex Method1983
- Complexity of linear programmingOperations Research Letters, 1982
- The fundamental theorem of algebra and complexity theoryBulletin of the American Mathematical Society, 1981
- On Algorithms for Solving f(x)=0Communications on Pure and Applied Mathematics, 1979
- Fast Algorithms for Manipulating Formal Power SeriesJournal of the ACM, 1978