Inhalt des Dokuments
Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Publikationen
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). |
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe
Hilfsfunktionen
Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.