Smale's Fundamental Theorem of Algebra Reconsidered

In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton's method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Smale...

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2014
Materias:	Fundamental Theorem of Algebra Homotopy methods Polynomial system solving Smale's 17th problem Complex variable Complexity theory Fundamental theorems Homotopy method Newton's methods Polynomial equation Smale's 17th problems Algorithms Cost benefit analysis Newton-Raphson method Polynomials Theorem proving
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v14_n1_p85_Armentano http://hdl.handle.net/20.500.12110/paper_16153375_v14_n1_p85_Armentano
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_16153375_v14_n1_p85_Armentano
record_format	dspace
spelling	paper:paper_16153375_v14_n1_p85_Armentano2025-07-30T19:00:59Z Smale's Fundamental Theorem of Algebra Reconsidered Fundamental Theorem of Algebra Homotopy methods Polynomial system solving Smale's 17th problem Complex variable Complexity theory Fundamental theorems Homotopy method Newton's methods Polynomial equation Polynomial system solving Smale's 17th problems Algorithms Cost benefit analysis Newton-Raphson method Polynomials Theorem proving In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton's method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Smale's upper bound estimate was infinite average cost. Ours is polynomial in the Bézout number and the dimension of the input. Hence it is polynomial for any range of dimensions where the Bézout number is polynomial in the input size. In particular it is not just for the case that Smale considered but for a range of dimensions as considered by Bürgisser-Cucker, where the max of the degrees is greater than or equal to n 1+ε for some fixed ε{lunate}. It is possible that Smale's algorithm is polynomial cost in all dimensions and our main theorem raises some problems that might lead to a proof of such a theorem. © 2013 SFoCM. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v14_n1_p85_Armentano http://hdl.handle.net/20.500.12110/paper_16153375_v14_n1_p85_Armentano
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Fundamental Theorem of Algebra Homotopy methods Polynomial system solving Smale's 17th problem Complex variable Complexity theory Fundamental theorems Homotopy method Newton's methods Polynomial equation Polynomial system solving Smale's 17th problems Algorithms Cost benefit analysis Newton-Raphson method Polynomials Theorem proving
spellingShingle	Fundamental Theorem of Algebra Homotopy methods Polynomial system solving Smale's 17th problem Complex variable Complexity theory Fundamental theorems Homotopy method Newton's methods Polynomial equation Polynomial system solving Smale's 17th problems Algorithms Cost benefit analysis Newton-Raphson method Polynomials Theorem proving Smale's Fundamental Theorem of Algebra Reconsidered
topic_facet	Fundamental Theorem of Algebra Homotopy methods Polynomial system solving Smale's 17th problem Complex variable Complexity theory Fundamental theorems Homotopy method Newton's methods Polynomial equation Polynomial system solving Smale's 17th problems Algorithms Cost benefit analysis Newton-Raphson method Polynomials Theorem proving
description	In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton's method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Smale's upper bound estimate was infinite average cost. Ours is polynomial in the Bézout number and the dimension of the input. Hence it is polynomial for any range of dimensions where the Bézout number is polynomial in the input size. In particular it is not just for the case that Smale considered but for a range of dimensions as considered by Bürgisser-Cucker, where the max of the degrees is greater than or equal to n 1+ε for some fixed ε{lunate}. It is possible that Smale's algorithm is polynomial cost in all dimensions and our main theorem raises some problems that might lead to a proof of such a theorem. © 2013 SFoCM.
title	Smale's Fundamental Theorem of Algebra Reconsidered
title_short	Smale's Fundamental Theorem of Algebra Reconsidered
title_full	Smale's Fundamental Theorem of Algebra Reconsidered
title_fullStr	Smale's Fundamental Theorem of Algebra Reconsidered
title_full_unstemmed	Smale's Fundamental Theorem of Algebra Reconsidered
title_sort	smale's fundamental theorem of algebra reconsidered
publishDate	2014
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v14_n1_p85_Armentano http://hdl.handle.net/20.500.12110/paper_16153375_v14_n1_p85_Armentano
_version_	1840322919571390464

Smale's Fundamental Theorem of Algebra Reconsidered

Ejemplares similares