 |
Perkolation
Perkolation gehörte mit zu den ersten Anwendung von Computersimulationen
in der statistischen Physik (siehe z.B. [1]), wobei zuerst
Algorithmen zur Simulation einzelner Cluster verwendet wurden.
Das eigentlich Perkolations-Problem, d.h. die Berechnung der
Perkolationswahrscheinlichkeit P(p) wurde jedoch anfangs als
nicht mit dem Computer behandelbar
eingeschätzt. So findet man z.B. in Ref. [1] auf
S. 135/136 die folgende Bemerkung zur Perkolationswahrscheinlichkeit
P(p) eines dreidimensionalen Würfels der Kantenlänge
M:
-
``The problem is to calculate P(p) as a function of p, and
hence to determine the critical probability p0. The problem is
probabilistic in its original physical formulation; and, in principle, it should
be amenable to direct simulation without any recourse to sophisticated
Monte Carlo devices. But this line of attack runs into a prohibitive amount
of computing. The simple-minded direct simulation would use random numbers
to label each bond as either blocked with probability q or unblocked
with probability p, would then examine each dry site in turn, wet it
whenever it was connected to an already wet site by an unblocked bond,
continue the examination until no more dry sites could be made wet, and
finally count the number of wet sites. But if M is large, say
M=200, there are 8 million sites and 24 million bonds in the chunk.
This calls for enormous storage facilities in the computer, even if we
go to the trouble of representing the state of each bond (blocked or unblocked)
and each site (dry or wet) by a single binary digit and packing this
information into separate bits of the various stored words. Further, we have
to scan all 8 million sites over and over again until no more can be
made wet, and this may require one or two hundred repetitions of the scan,
Moreover, this procedure only affords a single experimental observation on the
required number P(p); so that we must repeat it several times
to ensure that sampling errors are duly accounted for. Lastly, what we have so
far described relates merely to one prescribed value of p; so that
we must repeat the work for, say, 50 different values of p in order
to get a graph of P(p) against p for 0<=p<=1.
All in all, the complete calculation would need to process about 1012
or 1013 pieces of information and would keep a modern high-speed
computer continuously busy for about 50 years [3].
Direct simulation is thus out of the question.''
Inzwischen ist auch dieses Problem gelöst und Perkolation wurde
eine Parade-Anwendung von Computern in der
statistischen Mechanik wie man z.B. an dem Buch [2]
sehen kann. Wesentlich dazu beigetragen hat nicht nur die rapide Entwicklung
der Computer, sondern auch die Entwicklung besserer Algorithmen als dem
oben geschilderten. So benötigt der Algorithmus von Hoshen & Kopelman
[3] nur einen Durchlauf und kommt nebenbei auch ohne
Speicherung des gesamten Clusters aus.
C-Programme:
-
Illustration von Perkolation in einer X11 Umgebung:
xperc.c mit zugehörigem
makefile.
Dieses Programm enthält sowohl einen (allerdings wenig effizienten)
zellulären Automaten, der Platz-Perkolation auf dem Quadratgitter
illustriert, wie auch eine Illustration des Algorithmus von
Hoshen & Kopelman [3].
-
Zu einer Implementation, die z.B. die Cluster-Verteilung s n(s)
bei Verbindungs-Perkolation auf dem Quadratgitter simuliert, geht es
hier (diese Simulation einzelner Cluster
besitzt Ähnlichkeit mit alten Monte-Carlo Methoden [1]).
Übungsaufgabe:
Schätzen Sie für Platz-Perkolation auf einen LxL
Quadratgitter die Perkolationswahrscheinlichkeit
PL(p) mit Hilfe des
Hoshen-Kopelman-Algorithmus! Was schließen Sie aus Ihrem
Ergebnis für den Wert von pc ?
Literatur:
Für eine Erklärung des Modells sei auf Ref. [2]
und dort zitierte weitere Referenzen verwiesen.
Ein Existenzbeweis für die Perkolationsschwelle
pc findet man z.B. in Ref. [4].
Zur mathematischen Literatur gehört auch das dicke Buch
[5].
Den derzeit vermutlich genauesten Wert für die Perkolationsschwelle
(pc) bei Platz-Perkolation auf dem Quadratgitter
finden Sie in Ref. [6].
-
J.M. Hammersley, D.C. Handscomb, Monte Carlo Methods,
Methuen & Co Ltd, London (1965)
-
D. Stauffer, A. Aharony,
Introduction
to Percolation Theory,
2nd edition, Taylor & Francis Ltd, London (1994)
Perkolationstheorie:
Eine Einführung,
VCH Verlagsgesellschaft mbH, Weinheim (1995).
-
J. Hoshen, R. Kopelman, Percolation and Cluster Distribution. I. Cluster
Multiple Labeling Technique and Critical Concentration Algorithm,
Phys. Rev. B14
(1976) 3438-3445
-
R. Langlands, P. Pouliot, Y. Saint-Aubin,
Conformal
Invariance in Two-Dimensional Percolation,
Bulletin of the AMS 30 (1994) 1-61
-
G. Grimmett,
Percolation,
Spinger-Verlag, Berlin (1999)
-
M.E.J. Newman, R.M. Ziff,
Efficient
Monte Carlo Algorithm and High-Precision Results for Percolation,
Phys. Rev. Lett.
85 (2000) 4104-4107
|
|
