Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:Smale's Fundamental Theorem of Algebra Reconsidered
Autor:Armentano, D.; Shub, M.
Filiación:Centro de Matemática, Universidad de la República, Iguá 4225, Montevideo, 11400, Uruguay
CONICET, IMAS, Universidad de Buenos Aires, Ciudad Universitaria, Buenos Aires, C1428EGA, Argentina
Palabras clave: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
Año:2014
Volumen:14
Número:1
Página de inicio:85
Página de fin:114
DOI: http://dx.doi.org/10.1007/s10208-013-9155-y
Título revista:Foundations of Computational Mathematics
Título revista abreviado:Found. Comput. Math.
ISSN:16153375
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v14_n1_p85_Armentano

Referencias:

  • Artin, E., (1964) The Gamma Function, , New York: Holt, Rinehart and Winston
  • Abraham, R., Robbin, J., (1967) Transversal Mappings and Flows, , New York: Benjamin
  • Arnold, V.I., Gusein-Zade, S.M., Varchenko, A.N., (1985) Singularities of Differentiable Maps, 1. , Basel: Birkhäuser
  • Beltrán, C., A continuation method to solve polynomial systems and its complexity (2011) Numer. Math., 117 (1), pp. 89-113
  • Beltrán, C., Pardo, L.M., Smale's 17th problem: average polynomial time to compute affine and projective solutions (2009) J. Am. Math. Soc., 22 (2), pp. 363-385
  • Beltrán, C., Pardo, L.M., Fast linear homotopy to find approximate zeros of polynomial systems (2011) Found. Comput. Math., 11 (1), pp. 95-129
  • Beltrán, C., Shub, M., A note on the finite variance of the averaging function for polynomial system solving (2010) Found. Comput. Math., 10 (1), pp. 115-125
  • Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , New York: Springer
  • Bürgisser, P., Cucker, F., On a problem posed by Steve Smale (2011) Ann. Math., 174 (3), pp. 1785-1836
  • Dedieu, J.-P., Malajovich, G., Shub, M., Adaptative step size selection for homotopy methods to solve polynomial equations (2013) Imajna, 33 (1), pp. 1-29
  • Fernandez, M., Pardo, L.M., An arithmetic Poisson formula for the multi-variate resultant (2013) J. Complexity, , doi:10.1016/j.jco.2013.04.005
  • Kim, M.-H., Martens, M., Sutherland, S., (2011) Bounds for the cost of root finding, , arXiv: 0903. 3674
  • Renegar, J., On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials (1987) Math. Oper. Res., 12 (1), pp. 121-148
  • Shub, M., Complexity of Bezout's theorem. VI. Geodesics in the condition (number) metric (2009) Found. Comput. Math., 9 (2), pp. 171-178
  • Shub, M., Smale, S., Complexity of Bézout's theorem. I. Geometric aspects (1993) J. Am. Math. Soc., 6 (2), pp. 459-501
  • Shub, M., Smale, S., Complexity of Bezout's theorem. II. Volumes and probabilities (1993) Computational Algebraic Geometry, 109, pp. 267-285. , Nice1992Progr. Math, Boston: Birkhäuser
  • Shub, M., Smale, S., Complexity of Bezout's theorem. III. Condition number and packing (1993) J. Complex., 9 (1), pp. 4-14
  • Shub, M., Smale, S., Complexity of Bezout's theorem. IV. Probability of success; extensions (1996) SIAM J. Numer. Anal., 33 (1), pp. 128-148
  • Smale, S., The fundamental theorem of algebra and complexity theory (1981) Bull., New Ser., Am. Math. Soc., 4 (1), pp. 1-36
  • Smale, S., (2000) Mathematical Problems for the Next Century, Mathematics: Frontiers and Perspectives, pp. 271-294. , Providence: Amer. Math. Soc
  • Weyl, H., (1939) The Classical Groups. Their Invariants and Representations, , Princeton: Princeton University Press

Citas:

---------- APA ----------
Armentano, D. & Shub, M. (2014) . Smale's Fundamental Theorem of Algebra Reconsidered. Foundations of Computational Mathematics, 14(1), 85-114.
http://dx.doi.org/10.1007/s10208-013-9155-y
---------- CHICAGO ----------
Armentano, D., Shub, M. "Smale's Fundamental Theorem of Algebra Reconsidered" . Foundations of Computational Mathematics 14, no. 1 (2014) : 85-114.
http://dx.doi.org/10.1007/s10208-013-9155-y
---------- MLA ----------
Armentano, D., Shub, M. "Smale's Fundamental Theorem of Algebra Reconsidered" . Foundations of Computational Mathematics, vol. 14, no. 1, 2014, pp. 85-114.
http://dx.doi.org/10.1007/s10208-013-9155-y
---------- VANCOUVER ----------
Armentano, D., Shub, M. Smale's Fundamental Theorem of Algebra Reconsidered. Found. Comput. Math. 2014;14(1):85-114.
http://dx.doi.org/10.1007/s10208-013-9155-y