Universität zu Köln

Contributions to Determining Exact Ground-States of Ising Spin-Glasses and to their Physics

Liers, Frauke (2004) Contributions to Determining Exact Ground-States of Ising Spin-Glasses and to their Physics. PhD thesis, Universität zu Köln.

[img]
Preview
PDF
Download (1590Kb) | Preview

    Abstract

    In the last decades, much research has focused on a better understanding of so-called spin glasses (e.g., the alloys CuMn and AuFe.) Spin glasses are not yet fully understood. In order to be able to test the different theories that have been proposed for the nature of spin glasses we have to analyze numerically generated data. We consider spin glasses in the Ising model, where the spins (magnetic dipoles) have exactly two possibilities for aligning themselves. We are interested in the low-temperature states of the system, in which the spins are `frozen' and disordered. Determining a state of minimum energy, a ground state, amounts to calculating a maximum cut in a graph. The max-cut problem is a prominent NP-hard problem from combinatorial optimization. Maximum cuts can be determined exactly with a branch-and-cut algorithm. This thesis consists of two parts. In the first part we introduce the max-cut problem and a branch-and-cut algorithm for solving reasonably sized problems. We present several approaches for improving its performance for Ising spin-glass instances. In the second part of this work, we study the physics of spin glasses. We first discuss what is known in the literature. Then we present results for Bethe spin glasses. Finally we study the nature of short-range three-dimensional spin glasses. Results of the former were obtained in collaboration with M. Palassini and A.K. Hartmann, results of the latter in cooperation with M. Palassini and A. Peter Young.

    Item Type: Thesis (PhD thesis)
    Translated abstract:
    AbstractLanguage
    Seit Jahrzehnten wird intensiv daran gearbeitet, sogenannte Spingläser (z.B. die Legierungen CuMn oder AuFe) besser zu verstehen. Sie lassen sich bisher theoretisch nur unzureichend beschreiben. Man ist auf die Interpretation numerischer Ergebnisse angewiesen, um in der Literatur vorgeschlagene Theorien testen zu können. Wir betrachten Spingläser im Isingmodell, in dem die Spins (magnetische Dipole) genau zwei Einstellungsmöglichkeiten besitzen. Uns interessieren die Zustände tiefster Temperaturen, bei denen die Spins ungeordnet `einfrieren'. Das Bestimmen eines Zustandes minimaler Energie, eines Grundzustandes, läßt sich auf die Berechnung eines maximalen Schnittes in einem Graphen überführen. Das Maximum Schnitt Problem ist ein prominentes NP-schweres Problem aus der kombinatorischen Optimierung. Maximale Schnitte können mit einem Branch and Cut Algorithmus exakt bestimmt werden. Die vorliegende Arbeit besteht aus zwei Teilen. Im ersten Teil wird das Maximum Schnitt Problem und ein Branch and Cut Algorithmus zur Lösung von Instanzen vernünftiger Größe vorgestellt. Es werden verschiedene Ansätze vorgestellt, wie dieser Algorithmus für Instanzen, die von Ising Spingläern stammen, verbessert werden kann. Im zweiten Teil studieren wir die Physik von Spingläsern. Wir stellen zuerst den Stand der Forschung dar. Danach geben wir Ergebnisse für sogenannte Bethe Spingläser an. Zuletzt studieren wir die Natur von Spingläsern im kurzreichweitigen dreidimensionalen Gitter. Erstere Resultate sind in einer Kooperation mit Dr. M. Palassini und PD Dr. A.K. Hartmann entstanden, letztere in Zusammenarbeit mit Dr. M. Palassini und Prof. A. Peter Young.German
    Creators:
    CreatorsEmail
    Liers, Fraukeliers@informatik.uni-koeln.de
    URN: urn:nbn:de:hbz:38-13083
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    Maximum Schnitt Problem , SpinglasGerman
    maxcut problem , spin glassEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: 2004
    Date Type: Completion
    Date of oral exam: 06 July 2004
    Full Text Status: Public
    Date Deposited: 30 Nov 2004 11:13:59
    Referee
    NameAcademic Title
    Jünger, MichaelProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/1308

    Actions (login required)

    View Item