Lektüreseminar »Breaking the Worst Case«
Dozenten:
Folkmar Bornemann,
Caroline Lasser (Sommersemester 2012)
Teilnehmerzahl: 6 (min.) - 12 (max.)
Termin: donnerstags 14:00-15:30 Uhr im Seminarraum 02.08.011
Termine
| Datum |
Diskussionsleitung |
Thema |
| 19.7. |
|
Smoothed Analysis [T, pp. 349-368] |
| 24.5. |
Bergler |
Stochastische Konditionsanalyse [BC, Kapitel 2.2.6, 2.3, 2.4.1] |
| 26.4. |
Bordt |
Normweise Kondition (Charakterisierungen) [BC, Kapitel 1] |
| 19.4. |
Bornemann/Lasser |
Overtüre (Genauigkeit & Kondition) [BC, Kapitel 0] |
| 31.5. |
Gaim |
Vorkonditionierung & Dreieckssysteme [BC, Kapitel 2.4.2-3.1] |
| 03.5. |
Hofmann |
Singulärwertzerlegung und Least Squares [BC,Kapitel 1.4-1.6] |
| 05.7. |
Hofmann |
Methode des steilsten Abstiegs [BC, Kapitel 5.1-5.2] |
| 12.7. |
Keller |
Iterative Verfahren & Smoothed Analysis [BC, Kapitel 5.4; T, pp. 349-368] |
| 14.6. |
Molina |
Dreieckssysteme [BC, Kapitel 3] |
| 21.6. |
Troppmann |
Crash Kurs Stochastik (große Abweichungen, Zufallsmatrizen) [BC, Kapitel 4.1] |
| 10.5. |
Zollner |
Stochastische Konzepte [BC,Kapitel 2.2 ohne 2.2.6] |
| 28.6. |
Zollner |
Allgemeine Konditionsabschätzungen [BC, Kapitel 4.2.-4.4] |
Inhalt
Für eine Reihe wichtiger Algorithmen (wie zum Beispiel das Gaußsche Eliminationsverfahren oder das Simplexverfahren ) weiß man, dass sie für praktisch auftretende Probleme sehr gut einsetzbar
sind, kennt aber auch Worst-Case-Szenarien, in denen diese Algorithmen völlig wertlos sind. Die 2001 von Daniel Spielman und Shang-Hua Teng geschaffene
Smoothed Analysis gilt als wissenschaftlicher
Durchbruch für eine mögliche Erklärung dieses Phänomens. Die Grundidee der Smoothed Analysis ist die gezielte stochastische Störung von Input-Daten, so dass mit hoher Wahrscheinlichkeit der Worst Case
gebrochen wird. Internationale Preise wie der Gödel-Preis 2008 und der Rolf-Nevanlinna-Preis 2010 dokumentieren,
welche Bedeutung dieser neuen Theorie beigemessen wird. Das Seminar wird erklären, wie die Smoothed Analysis den Worst Case des Gaußschen Eliminationsverfahrens bricht. Benötigt werden
Grundkenntnisse aus der linearen Algebra, der Stochastik und der Numerik. Das Seminar wird das faszinierende Wechselspiel, in welches die Smoothed Analysis etwas fortgeschrittenere Elemente dieser mathematischen
Teildisziplinen versetzt, in langsamem und angemessenem Tempo entwickeln.
Ziele
Das Seminar ist ein gemeinsamer Lektüre- und Diskussionskurs des ersten Teils
Adagio des Buchs
Condition von
Peter Bürgisser 
und
Felipe Cucker , welches die Autoren vor seiner Veröffentlichung für diesen Kurs zur Verfügung stellen (der sehr viel schnellere und längere Hauptteil
Allegro des Buchs befasst sich mit der kürzlich von den Autoren erbrachten partiellen Lösung des
17. Problems von Steve Smale mittels Smoothed Analysis). Dieses Adagio schafft gute Voraussetzungen, um als Abschluss des Seminars die
Originalarbeit von Arvind Sankar, Daniel Spielman, Shang-Hua Teng zur Smoothed Analysis der Gaußschen Elimination (2006) zu diskutieren.
Die Teilnehmer sollen im Seminar den eigenständigen Umgang mit wissenschaftlicher mathematischer Literatur erlernen und einüben.
In der gemeinsamen wissenschaftlichen Diskussion der neuen Sachverhalte, Begriffe, Ideen und Argumentationslinien
sollen Unklarheiten bereinigt, das mathematische Verständnis vertieft und eine professionelle Diskussionskultur eingeübt werden.
Ablauf
Pro Seminarsitzung werden die einzelnen Kapitel eingehend von
allen diskutiert. Eine gewisse Selbstdisziplin, stets
gut vorbereitet zu sein und durchgehend aktiv zu bleiben, ist hierzu
zwingend erforderlich: Dazu gehört (a) wirklich
jedes Kapitel auch eingehend studiert zu haben
und (b) Fragen (jeder Art) schon vorab
(hand)schriftlich zu skizzieren. Die Fragesammlungen sind unmittelbar vor
jeder Sitzung
an uns abzugeben und dienen dazu, eine lebendige Diskussion in Gang zu setzen. Jeder Seminarteilnehmer übernimmt für (wenigstens) eine Sitzung
die Diskussionsleitung.
Literatur
- Peter Bürgisser, Felipe Cucker: Condition (Buch-Manuskript, Januar 2012)
- Arvind Sankar, Daniel Spielman, Shang-Hua Teng: Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices, SIAM. J. Matrix Anal. & Appl. 28, pp. 446-476 (31 pages), DOI 10.1137/S0895479803436202
- Shang-Hua Teng: Numerical Thinking in Algorithm Design and Analysis, in: E.K. Blum and A.V. Aho (eds.), Computer Science: The Hardware, Software and Heart of It, pp. 349-384, Springer-Verlag, 2011, DOI 10.1007/978-1-4614-1168-0_15
