Algebraische Geometrie auf der Origin 2000

Maximilian Kreuzer
kreuzer@hep.itp.tuwien.ac.at
Institut für Theoretische Physik

Die Klassifikation reflexiver Polyeder ist ein elementares kombinatorisches Problem, dessen Anwendungen von der algebraischen Geometrie bis zur Elementarteilchenphysik reichen: In der sogenannten torischen Geometrie, einer Verallgemeinerung der projektiven Räume, werden die geometrischen Daten durch Polyeder kodiert. Hyperflächen in diesen Räumen erfüllen genau dann die Einsteingleichungen, wenn die Polyeder reflexiv sind, d.h. wenn sie genau einen inneren Gitterpunkt enthalten, der von allen  Begrenzungsflächen Abstand 1 hat. Die Kassifikation dieser Objekte ist die Grundlage für eine systematische Analyse der resultierenden vereinheitlichten String-Modelle der Naturkräfte. Die große Zahl von Lösungen erfordert allerdings den Einsatz einer Großrechenanlage.

Reflexive Polyeder

Reflexive Polyeder sind Gitterpolyeder (alle Vertizes liegen auf einem Gitter _vp_eqn_0.gif) mit genau einem inneren Punkt und der Eigenschaft, dass alle Begrenzungsflächen Abstand 1 vom Ursprung haben. Der Abstand eines Gitterpunktes von einer Hyperebene ist durch die Anzahl der dazwischenliegenden parallelen Gitterebenen definiert. Dazu äquivalent ist die Bedingung, dass das duale Polyeder

_vp_eqn_1.gif           (1)

wieder ein Gitterpolyeder ist. Bei dieser Dualität gibt es eine eindeutige Entsprechung zwischen Vertizes von _vp_eqn_2.gif und facetten (Begrenzungsflächen) von _vp_eqn_3.gif und _vp_eqn_4.gif.

Die Klassifikation im 2-dimensionalen Fall kann auf einem Blatt Papier durchgeführt werden und führt auf die 16 von Batyrev [1] angegebenen Lösungen (Abb. 1). In höheren Dimensionen wurde von Harald Skarke (Humboldt Univ., Berlin) und mir ein Algorithmus gefunden, bei dem zuerst eine endliche Zahl von maximalen Objekten konstruiert wird, die alle anderen reflexiven Polyeder als Unterpolyeder enthalten [2]. In mehrjähriger Arbeit entwickelten wir ein Programmpaket für die Analyse der mathematischen und physikalischen Eigenschaften der mit den Polyederdaten konstruierten geometrischen Räume in beliebigen Dimensionen.

Abb. 1

Abbildung 1: In 2 Dimensionen gibt es 6 duale Paare und 4 selbstduale (3. Zeile) reflexive Polyeder. alle 16 sind Unterpolyeder von 3 maximalen Objekten (1. Zeile).

Ein Projekt im Rahmen dieses Arbeitsschwerpunktes, das wegen seiner Komplexität den Einsatz einer Großrechenanlage erfordert, ist die Durchführung der Klassifikation in 4 Dimensionen, dem physikalisch interessantesten Fall. Als Aufwärmübung kann  der 3-dimensionale Fall betrachtet werden: Hier fanden wir 15 maximale Polyeder mit bis zu 39 Punkten. Diese enthalten insgesamt 4319 verschiedene reflexive Polyeder, die wir ursprünglich mit einer Rechenzeit von einigen Stunden auf einem PC erhalten konnten [3]. Die Größenordnung des Problems ist schnell ersichtlich, wenn man bemerkt, dass für den 4-dimensionalen Fall 308 maximale reflexive Polyeder mit bis zu 680 Gitterpunkten zu analysieren sind. Wie sich inzwischen herausstellte, lag unser erster "educated guess", dass damit bis zu 109 Lösungen zu erwarten sind, schon recht nahe am Ergebnis.


Implementierung in C

Das Kernstück unseres Programmpakets ist die Polyederanalyse, bei der für eine vorgegebene Menge von Gitterpunkten die Gleichungen der Begrenzungsflächen (bzw. deren Koeffizienten, die Koordinaten der Vertizes des dualen Polyeders) berechnet werden. Im reflexiven Fall werden die Inzidenzen der Seitenflächen verschiedener Dimension (Vertizes, Kanten, Flächen, ..., facetten) verwendet, um die vollständige Punkteliste des dualen Polyeders und die Betti-Zahlen der resultierenden Calabi-Yau Hyperfläche zu berechnen. Da es sich hier im Wesentlichen um kombinatorische Probleme handelt, ist unser Paket eine reine Integer Applikation. Durch eine sorgfältige Strukturierung der Rechnungen und geeignete Overflow-Abfragen war für die lineare Algebra bisher meist die Standardpräzision ausreichend; durch Präprozessorparameter kann jedoch bei Bedarf leicht auf 64 Bit umgestellt werden.

Eine sehr nützliche Eigenschaft der verwendeten Programmiersprache C sind die bitweisen Operationen: Die Inzidenzen eines Polyeders bilden eine Boolsche Algebra, sodass man die einzelnen Bits einer Integer verwenden kann, um anzugeben, welche Vertizes auf einer Seitenfläche liegen. Damit kann man mit einer einzigen Operation den Durchschnitt zweier Seitenflächen berechnen und somit die Inzidenzstruktur unter Vermeidung von aufwendiger linearer Algebra sehr effizient berechnen. Glücklicherweise traten in unseren Applikationen bisher nur Polyeder mit weniger als 64 Vertizes auf, sodass alle Inzidenzen auf jeweils einer "unsigned long long integer" (64-Bit) untergebracht werden konnten. In einer verbesserten Variante der Polyederanalyse wird bereits bei der iterativen Berechnung der Seitenflächen die Inzidenzstruktur mitverwendet: Das brachte bei den 4-dimensionalen Polyedern im Mittel eine Beschleunigung um mehr als einen Faktor 3; bei höher-dimensionalen Objekten liegt dieser Faktor um einiges höher.

Bei unserem Klassifikationsalgorithmus werden die reflexiven Polyeder als Unterpolyeder der maximalen Objekte zwar eindeutig, unter Berücksichtigung der Gitterautomorphismen aber hochgradig redundant erzeugt. Es ist daher entscheidend, äquivalente Objekte nur einmal abzuspeichern und nach Unterpolyedern zu durchsuchen. Zu diesem Zweck haben wir eine Normalform definiert, deren Berechnung der zweite zeitaufwendige Teil der Rechnung ist und etwa gleich lang dauert wie die Polyederanalyse. allerdings hat sich herausgestellt, dass es nicht sinnvoll (und aus Speicherplatzgründen auch gar nicht möglich) ist, auch nicht-reflexive Zwischenpolyeder zu speichern. Daher werden wesentlich mehr Polyederanalysen als Normalformberechnungen durchgeführt, sodass erstere der entscheidende Faktor für die Rechenzeit sind. In der aktuellen Programmversion benötigt die Klassifikation im 3-dimensionalen Fall nur noch 7 Sekunden CPU-Zeit.

Neben der Rechenzeit ist der Speicherplatzbedarf der zweite limitierende Faktor. Aus der schlichten Zahl von 5 _vp_eqn_5.gif 108 Polyedern wird klar, dass eine sehr komprimierte Kodierung der Normalformen notwendig ist. Sowohl im RAM als auch auf der Festplatte verwenden wir dazu eine aus den Koordinaten der Vertizes in der Normalform optimal gewählte Basis für die Umrechnung in ein Zahlensystem, dessen Ziffern den Koordinaten entsprechen. Diese Zahl wird dann binär abgespeichert. Durch Ausnützen der Dualität lässt sich noch ein Faktor 2 einsparen, sodass wir im Mittel etwa 12 Koordinaten pro 32-Bit Integer (3 Koordinaten pro Byte) unterbringen, und somit nur etwa 20 Byte pro dualem Paar von Polyedern benötigen.

Mit diesen Tricks konnten wir die Rechnung bis etwas unter 100 Millionen Paare vorantreiben. Weiters ergab sich unter der Annahme, dass duale Polyeder unabhängig gefunden werden, eine Prognose von etwas über 400 Millionen Polyedern für die Gesamtzahl. Damit war klar, dass die Klassifikation nicht am Speicherplatz scheitern kann. Es war aber auch klar, dass wir zu einem Datenbanksystem übergehen müssen, bei dem nur ein kleiner Teil der Polyeder im RAM gespeichert ist. Durch eine baumartige Strukturierung der Daten muss bei der Suche nach einer bestimmten Normalform durch Bisektion der Datenbank, die bis zu 1000 mal pro Sekunde notwendig sein kann, jeweils nur ein zusammenhängender Bereich von etwa 1 kB gelesen werden.


LINUX/PC gegen Origin 2000

Beim Übergang zum Datenbanksystem zeigte sich nun die Stärke der Origin 2000: Durch den großen File System Buffer ist normalerweise die gesamte Datenbank von derzeit etwa 4.5 GB im RAM, sodass beliebig viele Prozesse, die parallel die verschiedenen maximalen Polyeder abarbeiten, gleichzeitig ausreichend rasch darauf zugreifen können. Wie entscheidend dieser Umstand ist, lässt sich daraus ersehen, dass bei einer anderwärtigen Belegung des Buffers, z.B. im Zuge vom Transfer großer Datenmengen bei Backups, die CPU-Auslastung je Prozess von nahezu 100% auf etwa 20 - 30% absinkt.

Trotzdem haben auch die PCs, die wir unter LINUX am Institut für Theoretische Physik betreiben, noch nicht ausgedient. Ein Pentium III mit 600 MHz schafft im Mittel etwa 2100 Polyederanalysen und 1800 Normalformberechnungen pro Sekunde; die Vergleichszahlen auf der Origin 2000 sind 1400 Polyeder und 900 Normalformen. Da die gesamte Rechnung nach aufsteigender Punktezahl organisiert ist und es die PCs mit 1 GB RAM und maßgeschneiderter Datenbank zumindest im Endstadium der Rechnungen häufig noch auf über 90% CPU-Auslastung bringen, können Nachzügler um fast 50% schneller berechnet und das Wachstum der gesamten Datenbank damit erheblich beschleunigt werden. Im allgemeinen liegt die CPU-Auslastung der PCs aber wesentlich niedriger, sodass der Vorteil in der (Integer) Rechenleistung pro Prozessor kaum genutzt werden kann und die Organisa-tion der Rechnung und die Verwaltung der Teilergebnisse bei alleiniger Verwendung von entsprechend vielen PCs noch um ein Vielfaches mühsamer wäre.

 Der Unterschied in den Geschwindigkeitsverhältnissen zwischen Polyederanalyse (3:2) und Normalformberechnung (2:1) erklärt sich vermutlich dadurch, dass bei der Polyederanalyse für die Berechnung der Inzidenzstrukturen viele 64-Bit Operationen ausgeführt werden, während die Normalformberechnung im zeitkritischen Teil mit 32-Bit Operationen auskommt (die Origin 2000 ist eine 64-Bit Maschine). Derzeit sind etwa 130 der 308 maximalen Objekte fertig durchgerechnet und die Datenbank enthält 465.574.495 Polyeder (bei einer aktuellen Prognose von etwa 473 Millionen, die sich noch um maximal 1% erhöhen könnte, weil die dualen Paare natürlich nicht exakt gleichverteilt sind).


Naturkräfte und Geometrie

Die Bedeutung unserer Ergebnisse im Rahmen der Geometrie und im Zusammenhang mit vereinheitlichten Modellen der Naturkräfte kann hier natürlich nur skizziert werden: Calabi-Yau Mannigfaltigkeiten sind, als Analoga der K3-Fläche, eine relativ einfache Klasse von nicht-trivialen höherdimensionalen Räumen. In der Physik tauchten sie im Rahmen der String-Theorie auf, als sich herausstellte, dass sie genau durch die Bedingungen einer konsistenten Reduktion von 10 auf 4 Dimensionen charakterisiert sind. Dabei wird der Materieinhalt durch die topologie der Calabi-Yau Varietät bestimmt (zum Beispiel entspricht die halbe Euler-Charakteristik der Zahl der Generationen von Elementarteilchen).

Die Torische Geometrie liefert, als Verallgemeinerung von (gewichtet) Projektiven Räumen, eine sehr effiziente Konstuktionsmethode für komplexe Mannigfaltigkeiten   [4], deren topologie durch einfache kombinatorische Formeln aus den definierenden Polyederdaten ermittelt werden kann [5, 6]. Auch Faserungsstrukturen, die aufgrund von Dualitäten die Berechnung nichtperturbativer Quantenkorrekturen erlauben, lassen sich aus der Polyedergeometrie ablesen [7]. Fast alle bisher in der String-Theorie verwendeten Calabi-Yau Räume sind, wie sich später herausstellte, Spezialfälle dieser Konstruktion. Bisher waren allerdings nur wenige 1000 Objekte dieser Art bekannt, sodass unsere vollständige Klassifikation nicht nur das Studium generischer Eigenschaften ermöglicht, sondern auch die Zahl der zu Verfügung stehenden Beispiele um etliche Größenordnungen erhöht.

Als Kuriosität sei vermerkt, dass der Körper mit der größten Symmetrie, der sich in unserer Datenbank findet, ein 4-dimensionaler Platonischer Körper mit Symmetrieordnung 1152 ist, der durch 24 Oktaeder begrenzt wird. Es handelt sich dabei um den (in beliebigen Dimensionen!) einzigen Platonischen Körper, der (als Gitterpolyeder) selbstdual ist. In unserer Rechnung entsteht dieses Polyeder als Unterpolyeder des Hyperwürfels (Abb. 2 und 3). Der Schnitt durch den Ursprung ist wieder ein (Archimedischer) reflexiver Körper, der seinerseits (zwei inäquivalente) reflexive Polygonschnitte besitzt (Quadrat und Sechseck). Mathematisch impliziert dies, dass die zugehörige Calabi-Yau Mannigfaltigkeit eine elliptische K3-Faserung aufweist. Dies wiederum ist die Bedingung dafür, dass dieser Raum für F-Theorie Kompaktifizierungen verwendet werden kann, und impliziert eine Reihe von Dualitäten zwischen verschiedenen String-Modellen.

Abb. 2

Abbildung 2: Die 3 Schnitt-Hyperebenen des Hyperwürfels enthalten die beiden begrenzenden Oktaeder und, als Schnitt durch den Ursprung, das Kuboktaeder (einen Archimedischen Körper, der als Schnitt eines Würfels mit einem Oktaeder entsteht.

Abb. 3

Abbildung 3: In dieser Darstellung sind die Symmetrien von Oktaeder und Kuboktader als Drehsymmetrien (anstelle von Gittersymmetrien) realisiert und damit besser zu sehen.


Literatur und Links

[1] V.V. Batyrev, Boundedness of the degree of higher-dimensional toric Fano varieties, Moscow Univ. Math. Bull. 37 (1982) 28

[2] M. Kreuzer, H. Skarke, On the classification of reflexive polyhedra, Commun. Math. Phys. 185 (1997) 495; H. Skarke, Weight systems for toric Calabi-Yau varieties and reflexivity of Newton polyhedra,  Mod. Phys. Lett. A11 (1996) 1637

[3] M. Kreuzer, H. Skarke, Classification of reflexive polyhedra in three dimensions, Adv. Theor. Math. Phys. 2 (1999) 853

[4] T.Oda, Convex bodies and algebraic geometry  (Springer, Berlin Heidelberg 1988)

[5] V.V. Batyrev, Dual Polyhedra and Mirror Symmetry for Calabi-Yau Hypersurfaces in Toric Varieties,  J. Alg. Geom. 3  (1994) 493

[6] V.V.Batyrev, D.I.Dais, Strong McKay correspondence, string-theoretic Hodge numbers and mirror symmetry, topology 35 (1996) 901; V.V.Batyrev, L.A.Borisov, Mirror duality and string-theoretic Hodge numbers, Invent. Math. 126  (1996) 183

[7] M. Kreuzer, H. Skarke, Calabi-Yau 4-folds and toric fibrations, J. Geom. and Physics 26 (1998) 272

Calabi-Yau Mannigfaltigkeiten:

http://hep.itp.tuwien.ac.at/ ~kreuzer/CY.html (M. Kreuzer und H. Skarke, TU Wien)

http://www.math.okstate.edu/~katz/CY/ (S. Katz, Oklahoma State Univ.)

http://ars-www.uchicago.edu/~aklemm/ HTML/cy.htm (A. Klemm, Univ. Chicago)

http://thew02.physik.uni-bonn.de/ ~netah/cy.html (R. Schimmrigk, Univ. Bonn)

String-Theorie:

http://superstringtheory.com/index.html

http://www.physics.ucsb.edu/~jpierre/ strings/index.html

http://www.spiegel.de/spiegel/ 0,1518,32734,00.html

http://hep.itp.tuwien.ac.at/~kreuzer/ strings.html

Platonische und Archimedische Körper:

http://www.friesian.com/polyhedr.htm

http://www.treasure-troves.com/math/ Polytope.html


Zum Inhaltsverzeichnis, ZIDline 2, Dezember 1999