Smale's Fundamental Theorem of Algebra Reconsidered

Mostrar todas las versiones(2)

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
Autores principales:	Armentano, D., Shub, M.
Formato:	JOUR
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:	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	todo:paper_16153375_v14_n1_p85_Armentano
record_format	dspace
spelling	todo:paper_16153375_v14_n1_p85_Armentano2023-10-03T16:28:13Z Smale's Fundamental Theorem of Algebra Reconsidered Armentano, D. Shub, M. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Armentano, D. Shub, M. 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.
format	JOUR
author	Armentano, D. Shub, M.
author_facet	Armentano, D. Shub, M.
author_sort	Armentano, D.
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
url	http://hdl.handle.net/20.500.12110/paper_16153375_v14_n1_p85_Armentano
work_keys_str_mv	AT armentanod smalesfundamentaltheoremofalgebrareconsidered AT shubm smalesfundamentaltheoremofalgebrareconsidered
_version_	1807320150031990784

Smale's Fundamental Theorem of Algebra Reconsidered

Ejemplares similares