Condition Length and Complexity for the Solution of Polynomial Systems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

4 Scopus Citations
View graph of relations

Author(s)

  • Diego Armentano
  • Carlos Beltrán
  • Peter Bürgisser
  • Felipe Cucker
  • Michael Shub

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1401-1422
Journal / PublicationFoundations of Computational Mathematics
Volume16
Issue number6
Publication statusPublished - 1 Dec 2016

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).

Research Area(s)

  • Complexity estimates, Homotopy methods, Polynomial systems

Citation Format(s)

Condition Length and Complexity for the Solution of Polynomial Systems. / Armentano, Diego; Beltrán, Carlos; Bürgisser, Peter; Cucker, Felipe; Shub, Michael.

In: Foundations of Computational Mathematics, Vol. 16, No. 6, 01.12.2016, p. 1401-1422.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal