TU Berlin

Fachgebiet Algorithmische AlgebraKunterbunt-Seminar

Inhalt des Dokuments

zur Navigation

Kunterbunt-Seminar

Die weit gestreuten Themen dieses Seminars reflektieren Interessen der Arbeitsgruppe. Das Seminar soll bei wenig Vorkenntnissen einen ersten Einstieg in diese Gebiete ermöglichen und die Möglichkeit bieten, die Arbeitsgruppe kennenzulernen.


Studierenden, die Interesse haben, eine Abschlussarbeit in dieser Fachgruppe zu schreiben, wird die Teilnahme am Seminar nahe gelegt.

Veranstaltungsform und Termin

Es handelt sich bei der Veranstaltung um ein Blockseminar. Der Raum MAR 4.062 befindet sich in der Marchstr. 23, der MA 313/314 direkt gegenüber von unseren Büros. Der Zeitplan für die Vorträge ist wie folgt:

Termine
Tag
Datum
Raum
Zeit
Plan
Donnerstag
6.2.2014
MAR 4.062
0800-1200
Vorträge
1200-1300
Mittagspause
1300-1700
Vorträge
Freitag
7.2.2014
MA 313/314
0800-1200
Vorträge
1200-1300
Mittagspause
1300-1700
Vorträge
Mittwoch
5.3.2014
MA 315
1400-1730
Vorträge

Es wird einen zweiten Termin geben:

Nachholtermin
Mittwoch
5.3.2014
MA 315
1400-1730
Vorträge

Anmeldung

Einige der Themen sind aus dem brandneuen Buch "Condition: The Geometry of Numerical Algorithms" von Bürgisser und Cucker, das bei Springer noch diesen Herbst erscheint. Es im folgenden kurz mit Condition bezeichnet. Teilnehmern des Seminars werden einzelne, themenbezogene Kapitel des Buches kostenfrei zur Verfügung gestellt.

Es stehen die folgenden Themen zur Auswahl (bei Bedarf können noch weitere Themen hinzu kommen). Für weitere Details siehe unten.

Themen
Thema
Vortragender
Tag
Zeit
Graph-basierte Algorithmen zur effizienten Lösung von Laplaceschen linearen Gleichungssystemen
Leili Riazy
6.2.
0800-1000
Quermasse und Steiners Formel für konvexe Körper
Sascha Hellfeuer
Abgesagt
Integration über Mannigfaltigkeiten und Coarea Formel
Darek Lesniowski
6.2.
5.3.
1000-1200
1600-1800

Poincare's Formel in der Integralgeometrie
Nick Bremer
6.2.
1300-1500
Kondition der Optimierung in der Linearen Programmierung
Julia Jonczyk
6.2.
1500-1700
Durchschnittliche Analyse der RCC Konditionszahl der Linearen Programmierung
Paul Breiding
7.2.
0800-1000
Invariantentheorie der Gruppe SL(n,C)
Fabian Adler
7.2.
1000-1200
Invarianten binärer Formen
Christoph Koseler
5.3.
1400-1600
Stabilisator der Determinante
Stella Schüler
7.2.
1500-1700

Themenbeschreibungen

Graph-basierte Algorithmen zur effizienten Lösung von Laplaceschen linearen Gleichungssystemen

Hier geht es um das effiziente Lösen dünn besetzter, linearer Gleichungssysteme.

In einer aufsehenerregenden Arbeit haben Spielman und Teng im Jahre 2003 gezeigt, dass sich symmetrische, diagonal dominante Gleichungssysteme in quasi-linearer Zeit approximativ lösen lassen. Dazu entwickelten diese Autoren eine fruchtbare Synthese von Methoden der Numerik, der Graphentheorie und der Theorie elektrischer Netzwerke (siehe Spielmans Hauptvortrag am ICM 2010). Diese ursprünglich sehr komplizierten Algorithmen sind nach und nach vereinfacht worden. Im Jahre 2013 haben Kelner et al. eine elegante und besonders einfache Variante dieser Algorithmen vorgestellt. Das Thema des Vortrags ist die Präsentation dieses Algorithmus.

Literatur:

Quermasse und Steiners Formel für konvexe Körper

Diese Formel besagt, dass das Volumen der Umgebung vom Radius $r$ eines konvexen Körpers im $\mathbb{R}^n$ eine Polynomfunktion in $r$ ist. Die Koeffizienten heissen (nach geeigneter Skalierung) die Quermasse des Körpers. Sie spielen eine wichtige Rolle in der Integralgeometrie.

Literatur:

  • Klain und Rota - Introduction to geometric probability (Kap. 9). Lezioni Lincee, 1997.
  • Schneider und Weil - Stochastic and Integral Geometry (Kap. 14). Springer, 2008.
  • Abschnitt 4.2 aus Schneider, Convex bodies: The Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications.
  • Hadwigers Klassiker "Vorlesungen Über Inhalt, Oberfläche und Isoperimetrie".

Integration über Mannigfaltigkeiten und Coarea Formel

Dieser Vortrag soll ein Schnellkurs über Untermannigfaltigkeiten des $\mathbb R^n$ und Integration über Mannigfaltigkeiten sein. Ziel ist die Erklärung der Coarea Formel, welche eine Verallgemeinerung der Transformationsformel und Fubinis Theorem darstellt. Dieser Vortrag ist die Vorbereitung auf den Vortrag über Poincare's Formel.

Literatur:

  • Abschnitte 2.1, 17.3 und Teile aus Abschnitt A.2 aus Condition.

Poincare's Formel in der Integralgeometrie

Angenommen, $M$ ist eine feste Kurve in der $2$-dimensionalen Sphäre und $N$ ein zufällig gewählter Großkreis. Was ist die erwartete Anzahl Schnittpunkte von $M$ mit $N$? Das Ergebnis ist die Länge von $M$ geteilt durch $\pi$. Dieser Satz verallgemeinert auf höhere Dimensionen und soll im Vortrag bewiesen werden. (Es werden hierzu Grundkenntnisse der Analysis auf Mannigfaltigkeiten vorausgesetzt.)

Literatur:

  • Abschnitt A.4.1 aus Condition

Für den allgemeinen Kontext siehe die Literatur bei "Quermasse und Steiners Formel"

Kondition der Optimierung in der Linearen Programmierung

Wie sensitiv hängt die Lösung eines linearen Optimierungsproblems von den Eingabedaten $d$ ab? Diese Frage lässt verschiedene Präzisierungen zu. Die Renegar-Cheung-Cucker (RCC) Konditionszahl $\kappa(d)$ ist ein quantitatives Mass für diese Abhängigkeit. Sie beschränkt auch die Komplexität, um eine Lösung zu berechnen. Im Vortrag soll diese Grösse definiert und ihre Eigenschaften besprochen werden.

Literatur:

  • Kapitel 11 von Condition.

Durchschnittliche Analyse der RCC Konditionszahl der Linearen Programmierung

Dieser Vortrag schliesst an den vorigen an. Angenommen, wir haben eine zufällige Instanz eines linearen Optimierungsproblems (formalisiert durch Gausssche Verteilungen). Wie gross ist die Wahrscheinlichkeit, dass die RCC Konditionszahl $\kappa(d)$ grösser als die Schwelle $t$ ist? Was ist der Erwartungswert von $\log\kappa(d)$? Glücklicherweise ist dieser Erwartungwert klein, was in gewissem Sinne den Erfolg gewisser Algorithmen für LP erklärt.

Literatur:

  • Kapitel 12 von Condition.

Invariantentheorie der Gruppe SL(n,C)

Die Gruppe $\operatorname{GL}(n,\mathbb C)$ operiert auf m-Tupeln $(v_1,\ldots,v_m)$ von Vektoren in $\mathbb C^n$ auf natürliche Weise. Gesucht sind polynomiale Funktionen in den Einträgen
der Vektoren $v_i$, die unter der Wirkung von $\operatorname{SL}(n,\mathbb C)$ invariant sind.
Die Determinante von $(v_{i_1},\ldots,v_{i_n})$ ist eine solche Invariante, wenn
$i_1,\ldots,i_n$ verschiedene Indizes in $\{1,2,\ldots,m\}$ bezeichnen. Der erste Fundamentalsatz der Invariantentheorie besagt, dass diese den Ring der Invarianten erzeugen.

Literatur:

  • Fulton und Harris - Representation Theory (Appendix F). Springer, 1991.
  • Sturmfels - Algorithms in Invariant Theory (Kapitel 3). Springer, 1993.

Für weiterführende Behandlungen siehe:

  • Procesi - Lie Groups: An Approach through Invariants and Representations (Kapitel 11). Springer, 2007.

Invarianten binärer Formen

Die besten Algebraiker des 19. Jahrhundert haben zu diesem Thema beigetragen. Die Gruppe $\operatorname{SL}(2,\mathbb{C})$ operiert auf dem Vektorraum der binären Formen $f$ vom Grad $d$ in den Variablen $X,Y$ durch Substitution. Eine Invariante ist eine Polynomfunktion in den Koeffizienten von $f$, die invariant unter der Aktion von $\operatorname{SL}(2,\mathbb{C})$ ist. Betrachtet man auch die Abhängigkeit von $X$ und $Y$, so wird man zum Begriff der Kovariante geführt. Man möchte die Invarianten und Kovarianten verstehen.

Literatur:

  • Sturmfels - Algorithms in Invariant Theory (Abschnitt 3.6). Springer, 1993.
  • Procesi - Lie Groups: An Approach through Invariants and Representations (Kapitel 15). Springer, 2007.

Hinweis: Dieses Thema ist weitläufig und müsste in einem Gespäch genauer eingegrenzt werden.

Stabilisator der Determinante

Die Determinante $\det(X)$ ist ein homogenenes Polynom vom Grad $n$ in den $n^2$ Einträgen der Matrix $X=(x_{ij})$. Welche invertierbaren linearen Transformationen der Variablen lassen $\det(X)$ invariant? Diese Frage wurde bereits von Frobenius 1897 beantwortet. Es soll ein moderner Beweis dieses Satzes von Frobenius präsentiert werden. Als Vorlage liegt eine Beweisskizze von Landsberg vor,
bei der allerdings einige Lücken ausgefüllt werden müssten.    

Literatur:

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe