Inhalt des Dokuments
Prof. Dr. Peter Bürgisser
- © Peter Bürgisser
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin
Büro
Raum MA 317 (3. OG)
Institut für Mathematik
Sprechstunde
Während der Vorlesungszeit: Mittwochs 1200-1300.
Während der vorlesungsfreien Zeit: Nach Vereinbarung.
Während der Vorlesungszeit: Mittwochs 1200-1300.
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 | 1-22 |
| Jahr | 2016 |
| ISSN | 1615-3383 |
| DOI | 10.1007/s10208-016-9309-9 |
| Journal | Foundations of Computational Mathematics |
| 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