|
|
 |
 |
|
|
|
|
Computing Exact Ground States of Ising
Spin Glasses
|
 |
| Begin: |
in the eighties |
 |
| End: |
open |
|
| Status: |
ongoing |
 |
|
|
|
| |
|
|
|
|
|
|
Description: |
> |
A spin-glass instance in the Ising
model is given by n spins that can either point up or
down. Spin i and j are coupled with coupling strengh Jij.
We mainly consider short-range
systems, e.g. d-dimensional systems in which spins are located on the
sites of a d-dimensional lattice with nearest neighbor interactions
being present. The Hamiltonian H is given by
H = - Σ Jij Si Sj,
where the sum runs over all coupled spins, and the couplings Jij
are appropriately chosen. A ground state is a
spin configuration that attains the global minimum of the energy
function H. In contrast to heuristic algorithms used by many
physicists, we determine exact ground states. Calculating an exact
ground state of a spin glass in the Ising model amounts to determining
a maximum cut in the associated graph of interactions. The
algorithm that has been
developed at the Institut für Informatik in Cologne in
collaboration with several other researchers is quite effective in
practice, making it is possible to gain insight into the physics of
spin glasses. Recently, we have extended the service to long-range spin glasses in the SK-model using an algorithm provided to us by our colleagues F. Rendl, G. Rinaldi, and A. Wiegele.
We make our program available to the
physics community via our server.
The command-line client option is the easiest possibility in case you want
to know ground states of many samples. Just download the perl-script.
An exact ground state of a 2- or 3-dimensional lattice or defined on a
complete graph will be returned to the reply address. In case the
program could not determine an optimum solution within the allowed cpu
time, you get a legal spin configuration together with a lower bound
for the energy. Within the allowed time limit we usually can compute
exact ground states for two-dimensional spin glasses of sizes up to
50x50 (for continuous distributions), 40x40 (for +/- 1 systems), and
6x6x6 for three-dimensional systems.
|
|
|
|
|
|
|
| People involved: |
> |
, |
|
| |
|
|
|
| Partners: |
> |
colleagues from both the spin glass and the optimization community:
(Universität Göttingen),
(ETH Zuerich),
(Universitat de Barcelona),
(Université
Paris-Sud, Orsay),
Giovanni Rinaldi (IASI-CNR, Rome)
Gerhard Reinelt (Universität Heidelberg)
(Universität des
Saarlandes),
Franz Rendl (Alpen-Adria Universität Klagenfurt)
(Universita di Roma 'La Sapienza', Italy)
Angelika Wiegele (Alpen-Adria Universität Klagenfurt)
(University of California
Santa Cruz)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Documents:
|
> |
|
|
|
|
|
|
|
|
|
|
|
