Buscar

Estamos realizando la búsqueda. Por favor, espere...

Condition Length and Complexity for the Solution of Polynomial Systems

Abstract: Smale?s 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale in Mathematical problems for the next century, American Mathematical Society, Providence, 2000). The main progress on Smale?s problem is Beltrán and Pardo (Found Comput Math 11(1):95?129, 2011) and Bürgisser and Cucker (Ann Math 174(3):1785?1836, 2011). In this paper, we will improve on both approaches and prove an interesting intermediate result on the average value of the condition number. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán and Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser and Cucker (2011), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last theorem is similar to the main result of Bürgisser and Cucker (2011) but relies only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser and Cucker (2011). We build on methods developed in Armentano et al. (2014). © 2016, SFoCM.

 Fuente: Foundations of Computational Mathematics Volume 16, Issue 6, 1 December 2016, Pages 1401-1422

 Editorial: Springer New York LLC

 Año de publicación: 2016

 Nº de páginas: 22

 Tipo de publicación: Artículo de Revista

 DOI: 10.1007/s10208-016-9309-9

 ISSN: 1615-3375,1615-3383

 Proyecto español: MTM2010-16051 ; MTM2014-57590-P

 Url de la publicación: https://doi.org/10.1007/s10208-016-9309-9

Autoría

ARMENTANO, DIEGO

BÜRGISSER, PETER

JUAN FELIPE CUCKER FARKAS

SHUB, MICHAEL