Entwicklung eines verbesserten Algorithmus zur exakten Bestimmung von Ising Spinglas Grundzuständen, Durchführung von Computerexperimenten und physikalische Interpretation der Ergebnisse
Zusammenfassung der Projektergebnisse
Ein Forschungsbereich in der theoretischen Physik widmet sich dem Studium ungeordneter Systeme. Sogenannte Spingläser, z.B. die Legierungen Kupfer- Mangan oder Gold-Eisen, sind Vertreter solcher Systeme. Ihre Physik ist noch unzureichend verstanden, aber für sie gewonnene Erkenntnisse lassen sich häufig auch auf andere ungeordnete Systeme übertragen. Ein Fokus beim Studium von Spinglasern liegt auf der Analyse der Zustände bei tiefsten Temperaturen, in denen das System in einen energieminimalen Zustand übergeht (Grundzustand). Ein wichtiges Modell für Spingläser ist das Isingmodell, in dem die magnetischen Momente (Spins) entweder „nach oben" oder „nach unten" zeigen können. Im Unterschied zu vielen Physikern, die häufig heuristische Methoden benutzen, um Grundzustände im Isingmodell zu bestimmen, ist unser Verfahren beweisbar exakt und liefert für vergleichbar große Systeme exakte Grundzustände. In dem von der Deutschen Forschungsgemeinschaft geförderten Projekt wurde das exakte Grundzustandsbestimmungsprogramm algorithmisch verbessert, so dass wir nun früher unlösbare Probleme lösen können. Die mit dem Verfahren gewonnenen Ergebnisse haben wir physikalisch interpretiert. Um das exakte Verfahren interessierten Kolleginnen und Kollegen aus der Physik zu Verfügung stellen zu können, wurde der Kölner S pinglas-Server modernisiert, erweitert und ist nun für den Nutzer bequemer zu bedienen. Man kann entweder über ein www-Interface oder mittels eines von uns entwickelten Klienten auf einfache Art und Weise gleichzeitig viele Jobs an den Server übermitteln. Die in Köln berechneten exakten Grundzustände werden per email an den Nutzer zurückgeschickt. Für Gittergraphen haben wir das algorithmische Verfahren durch Einbauen von Heuristiken für die Separierung der Kreisungleichungen verbessert. Wir haben eine Separierung von allgemeineren Schnittebenen durch Liften und Projizieren implementiert und getestet. Für einige Instanzklassen ergibt sich eine bessere Performance, wenn die auftretenden Linearen Programme zunächst approximativ und erst später exakt gelöst werden, um die Korrektheit zu wahren. Um einen approximativen LP-Löser nutzen zu können, wurde die ABACUS-Bibliothek erweitert. Für gaussverteilte zweidimensionale Instanzen liegt z.B. die durchschnittliche Laufzeit für 1202 Gitter nun bei weniger als einer halben Stunde, was unseres Wissens nach deutlich schneller ist, als mit guten heuristischen Verfahren erzielt werden kann. Für Instanzen der sogenannten eindimensionalen Isingkette haben wir einen Branch-Cut and Price Algorithmus entwickelt und implementiert, so dass wir für dieses Modell Grundzustände deutlich größerer Instanzen berechnen können als die default Branch-and-Cut Implementierung. Das Verfahren für zweidimensionale Instanzen im äußeren magnetischen Feld haben wir komplettiert, so dass wir auch für größere Instanzen in vernünftiger Zeit die Grundzustände als Funktion des äußeren Feldes bestimmen können. In der Analyse der Physik von Spingläsern zeigten wir, dass die Voraussagen der Droplet Scaling Theorie, die für zweidimensionale Spingläser ohne äußeres Feld akzeptiert ist, auch für zweidimensionale Spingläser im äußeren Magnetfeld die Physik korrekt beschreibt. Diese Fragestellung war seit einem Jahrzehnt offen. Für die eindimensionale Isingkette konnten wir zeigen, dass die zuvor von anderen Wissenschaftlern gefundene Schiefe der Energieverteilung ein Artefakt eines Mean-Field Systems ist und für kurzreichweitige Modelle verschwindet. Für dreidimensionale kurzreichweitige Systeme mit gaußverteilten Kopplungen um einen Mittelwert c haben wir den kritischen Mittelwert bestimmt, bei dem der Phasenübergang vom Ferromagneten zum Spinglas stattfindet. Weiter haben wir gezeigt, dass sich das sogenannte SRAM Modell bei Temperatur T = 0 wie ein Spinglas verhält. Im Rahmen der jetzigen Förderung von Dr. Frauke Liers im Emmy-Noether Programm der DFG wird dieses Projekt als eines der wichtigen Probleme weiter verfolgt werden.
Projektbezogene Publikationen (Auswahl)
- Modernisierter und erweiterter Server zur Bestimmung von Ising Spinglas Grundzuständen
- Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut. In: A.K. Hartmann und H. Rieger (Hrsg.) New Optimization Algorithms in Physics, Wiley (2004)
F. Liers, M. Jünger, G. Reinelt, und G. Rinaldi
- Contributions to Determining Exact Ground States of Ising Spin Glasses and to their Physics. Dissertation, Köln (2004)
F. Liers
- Determining Maximum Cuts in Graphs Coming from Theoretical Physics, (2005). Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 18.-20. Mai 2005, Köln (CTW 2005)
M. Jünger und F. Liers
- Energy Fluctuations in Spin Glasses. Phys. Rev. B, 72, 094421 (2005)
H.G. Katzgraber, M. Körner, F. Liers, M. Jünger, und A.K. Hartmann
- Overcoming System-Size Limitations in Spin Glasses. Progress of Theoretical Physics Supp., 157, 59, (2005)
H. G. Katzgraber, M. Körner, F. Liers, und A.K. Hartmann
- A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem. In: C. Demetrescu (Hrsg.), Workshop on Experimental Algorithms, Lecture Notes of Computer Science 4525, Springer Verlag, S. 379 - 392 (2007)
M. Behle, M. Jünger, und F. Liers
- Local Cuts Revisited
C. Buchheim, F. Liers, und M. Oswald
- Magnetic exponents of two-dimensional spin glasses. Physical Review Letters
F. Liers und O.G. Martin
- Zerotemperature behavior of the random-anisotropy model in the stronganisotropy limit
F. Liers, J. Lukic, E. Marinari, A. Pelisetto und E. Vicari
