TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Inhalt des Dokuments

zur Navigation

Search for Publication

Suche nach Publikationen

All Publications

Condition length and complexity for the solution of polynomial systems
Zitatschlüssel ABBCS-Condition-Length-And-Complexity-For-The-Solution-Of-Polynomial-Systems
Autor Diego Armentano and Carlos Beltrán and Peter Bürgisser and Felipe Cucker and Michael Shub
Seiten 1401–1422
Jahr 2016
ISSN 1615-3383
DOI 10.1007/s10208-016-9309-9
Journal Found. Comput. Math.
Jahrgang 16
Nummer 6
Monat 03
Zusammenfassung Smale's 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale's problem is Beltrán-Pardo (2011) and Bürgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of Bürgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe