Statistical Mechanics Algorithms and Computations W Krauth.pdf

1、OXFORD MASTER SERIES IN STATISTICAL,COMPUTATIONAL,AND THEORETICAL PHYSICSOXFORD MASTER SERIES IN PHYSICSThe Oxford Master Series is designed for final year undergraduate andbeginning graduate students in physics and related disciplines.It hasbeen driven by a perceived gap in the literature today.Whi

2、le basicundergraduate physics texts often show little or no connection with thehuge explosion of research over the last two decades,more advancedand specialized texts tend to be rather daunting for students.In thisseries,all topics and their consequences are treated at a simple level,while pointers

3、to recent developments are provided at various stages.The emphasis in on clear physical principles like symmetry,quantummechanics,and electromagnetism which underlie the whole of physics.At the same time,the subjects are related to real measurements and tothe experimental techniques and devices curr

4、ently used by physicists inacademe and industry.Books in this series are written as course books,and include ample tutorial material,examples,illustrations,revisionpoints,and problem sets.They can likewise be used as preparation forstudents starting a doctorate in physics and related fields,or for r

5、ecentgraduates starting research in one of these fields in industry.CONDENSED MATTER PHYSICS1.M.T.Dove:Structure and dynamics:an atomic view of materials2.J.Singleton:Band theory and electronic properties of solids3.A.M.Fox:Optical properties of solids4.S.J.Blundell:Magnetism in condensed matter5.J.

6、F.Annett:Superconductivity,superfluids,and condensates6.R.A.L.Jones:Soft condensed matterATOMIC,OPTICAL,AND LASER PHYSICS7.C.J.Foot:Atomic physics8.G.A.Brooker:Modern classical optics9.S.M.Hooker,C.E.Webb:Laser physics15.A.M.Fox:Quantum optics:an introductionPARTICLE PHYSICS,ASTROPHYSICS,AND COSMOLO

7、GY10.D.H.Perkins:Particle astrophysics11.Ta-Pei Cheng:Relativity,gravitation and cosmologySTATISTICAL,COMPUTATIONAL,AND THEORETICALPHYSICS12.M.Maggiore:A modern introduction to quantum field theory13.W.Krauth:Statistical mechanics:algorithms and computations14.J.P.Sethna:Statistical mechanics:entrop

8、y,order parameters,andcomplexityStatistical MechanicsAlgorithms and ComputationsWerner KrauthLaboratoire de Physique Statistique,Ecole NormaleSup erieure,Paris13Great Clarendon Street,Oxford OX2 6DPOxford University Press is a department of the University of Oxford.It furthers the Universitys object

9、ive of excellence in research,scholarship,and education by publishing worldwide inOxford NewYorkAuckland CapeTown DaresSalaam HongKong KarachiKualaLumpur Madrid Melbourne MexicoCity NairobiNewDelhi Shanghai Taipei TorontoWith offices inArgentina Austria Brazil Chile CzechRepublic France GreeceGuatem

10、ala Hungary Italy Japan Poland Portugal SingaporeSouthKorea Switzerland Thailand Turkey Ukraine VietnamOxford is a registered trade mark of Oxford University Pressin the UK and in certain other countriesPublished in the United Statesby Oxford University Press Inc.,New Yorkc?Oxford University Press 2

11、006The moral rights of the author have been assertedDatabase right Oxford University Press(maker)First published 2006All rights reserved.No part of this publication may be reproduced,stored in a retrieval system,or transmitted,in any form or by any means,without the prior permission in writing of Ox

12、ford University Press,or as expressly permitted by law,or under terms agreed with the appropriatereprographics rights organization.Enquiries concerning reproductionoutside the scope of the above should be sent to the Rights Department,Oxford University Press,at the address aboveYou must not circulat

13、e this book in any other binding or coverand you must impose the same condition on any acquirerBritish Library Cataloguing in Publication DataData availableLibrary of Congress Cataloging in Publication DataData availablePrinted in Great Britainon acid-free paper byCPI Antony Rowe,Chippenham,Wilts.IS

14、BN 0198515359(Hbk)9780198515357ISBN 0198515367(Pbk)978019851536410 9 8 7 6 5 4 3 2 1F ur Silvia,Alban und FelixThis page intentionally left blank PrefaceThis book is meant for students and researchers ready to plunge intostatistical physics,or into computing,or both.It has grown out of myresearch ex

15、perience,and out of courses that I have had the good fortuneto give,over the years,to beginning graduate students at the Ecole Nor-male Sup erieure and the Universities of Paris VI and VII,and also tosummer school students in Drakensberg,South Africa,undergraduatesin Salem,Germany,theorists and expe

16、rimentalists in Lausanne,Switzer-land,young physicists in Shanghai,China,among others.Hundreds ofstudents from many different walks of life,with quite different back-grounds,listened to lectures and tried to understand,made comments,corrected me,and in short helped shape what has now been writtenup,

17、for their benefit,and for the benefit of new readers that I hope toattract to this exciting,interdisciplinary field.Many of the students satdown afterwards,by themselves or in groups,to implement short pro-grams,or to solve other problems.With programming assignments,lackof experience with computers

18、 was rarely a problem:there were alwaysmore knowledgeable students around who would help others with thefirst steps in computer programming.Mastering technical coding prob-lems should also only be a secondary problem for readers of this book:allprograms here have been stripped to the bare minimum.No

19、ne exceeda few dozen lines of code.We shall focus on the concepts of classical and quantum statisticalphysics and of computing:the meaning of sampling,random variables,ergodicity,equidistribution,pressure,temperature,quantum statisticalmechanics,the path integral,enumerations,cluster algorithms,and

20、theconnections between algorithmic complexity and analytic solutions,toname but a few.These concepts built the backbone of my courses,andnow form the tissue of the book.I hope that the simple language andthe concrete settings chosen throughout the chapters take away none ofthe beauty,and only add to

21、 the clarity,of the difficult and profoundsubject of statistical physics.I also hope that readers will feel challenged to implement many ofthe programs.Writing and debugging computer code,even for the naiveprograms,remains a difficult task,especially in the beginning,but it iscertainly a successful

22、strategy for learning,and for approaching the deepunderstanding that we must reach before we can translate the lessons ofthe past into our own research ideas.This book is accompanied by a compact disc containing more than onehundred pseudocode programs and close to 300 figures,line drawings,viiiPref

23、aceand tables contained in the book.Readers are free to use this mate-rial for lectures and presentations,but must ask for permission if theywant to include it in their own publications.For all questions,pleasecontact me at www.lps.ens.fr/?krauth.(This website will also keep alist of misprints.)Read

24、ers of the book may want to get in contact witheach other,and some may feel challenged to translate the pseudocodeprograms into one of the popular computer languages;I will be happyto assist initiatives in this direction,and to announce them on the abovewebsite.Contents1Monte Carlo methods11.1Popula

25、r games in Monaco31.1.1Direct sampling31.1.2Markov-chain sampling41.1.3Historical origins91.1.4Detailed balance151.1.5The Metropolis algorithm211.1.6A priori probabilities,triangle algorithm221.1.7Perfect sampling with Markov chains241.2Basic sampling271.2.1Real random numbers271.2.2Random integers,

26、permutations,and combinations291.2.3Finite distributions331.2.4Continuous distributions and sample transformation 351.2.5Gaussians371.2.6Random points in/on a sphere391.3Statistical data analysis441.3.1Sum of random variables,convolution441.3.2Mean value and variance481.3.3The central limit theorem5

27、21.3.4Data analysis for independent variables551.3.5Error estimates for Markov chains591.4Computing621.4.1Ergodicity621.4.2Importance sampling631.4.3Monte Carlo quality control681.4.4Stable distributions701.4.5Minimum number of samples76Exercises77References792Hard disks and spheres812.1Newtonian de

28、terministic mechanics832.1.1Pair collisions and wall collisions832.1.2Chaotic dynamics862.1.3Observables872.1.4Periodic boundary conditions902.2Boltzmanns statistical mechanics922.2.1Direct disk sampling95xContents2.2.2Partition function for hard disks972.2.3Markov-chain hard-sphere algorithm1002.2.

29、4Velocities:the Maxwell distribution1032.2.5Hydrodynamics:long-time tails1052.3Pressure and the Boltzmann distribution1082.3.1Bath-and-plate system1092.3.2Piston-and-plate system1112.3.3Ideal gas at constant pressure1132.3.4Constant-pressure simulation of hard spheres1152.4Large hard-sphere systems1

30、192.4.1Grid/cell schemes1192.4.2Liquidsolid transitions1202.5Cluster algorithms1222.5.1Avalanches and independent sets1232.5.2Hard-sphere cluster algorithm125Exercises128References1303Density matrices and path integrals1313.1Density matrices1333.1.1The quantum harmonic oscillator1333.1.2Free density

31、 matrix1353.1.3Density matrices for a box1373.1.4Density matrix in a rotating box1393.2Matrix squaring1433.2.1High-temperature limit,convolution1433.2.2Harmonic oscillator(exact solution)1453.2.3Infinitesimal matrix products1483.3The Feynman path integral1493.3.1Naive path sampling1503.3.2Direct pat

32、h sampling and the L evy construction1523.3.3Periodic boundary conditions,paths in a box1553.4Pair density matrices1593.4.1Two quantum hard spheres1603.4.2Perfect pair action1623.4.3Many-particle density matrix1673.5Geometry of paths1683.5.1Paths in Fourier space1693.5.2Path maxima,correlation funct

33、ions1743.5.3Classical random paths177Exercises182References1844Bosons1854.1Ideal bosons(energy levels)1874.1.1Single-particle density of states1874.1.2Trapped bosons(canonical ensemble)1904.1.3Trapped bosons(grand canonical ensemble)196Contentsxi4.1.4Large-N limit in the grand canonical ensemble2004

34、.1.5Differences between ensemblesfluctuations2054.1.6Homogeneous Bose gas2064.2The ideal Bose gas(density matrices)2094.2.1Bosonic density matrix2094.2.2Recursive counting of permutations2124.2.3Canonical partition function of ideal bosons2134.2.4Cycle-length distribution,condensate fraction2174.2.5

35、Direct-sampling algorithm for ideal bosons2194.2.6Homogeneous Bose gas,winding numbers2214.2.7Interacting bosons224Exercises225References2275Order and disorder in spin systems2295.1The Ising modelexact computations2315.1.1Listing spin configurations2325.1.2Thermodynamics,specific heat capacity,and m

36、ag-netization2345.1.3Listing loop configurations2365.1.4Counting(not listing)loops in two dimensions2405.1.5Density of states from thermodynamics2475.2The Ising modelMonte Carlo algorithms2495.2.1Local sampling methods2495.2.2Heat bath and perfect sampling2525.2.3Cluster algorithms2545.3Generalized

37、Ising models2595.3.1The two-dimensional spin glass2595.3.2Liquids as Ising-spin-glass models262Exercises264References2666Entropic forces2676.1Entropic continuum models and mixtures2696.1.1Random clothes-pins2696.1.2The AsakuraOosawa depletion interaction2736.1.3Binary mixtures2776.2Entropic lattice

38、model:dimers2816.2.1Basic enumeration2816.2.2Breadth-first and depth-first enumeration2846.2.3Pfaffian dimer enumerations2886.2.4Monte Carlo algorithms for the monomerdimerproblem2966.2.5Monomerdimer partition function299Exercises303References3057Dynamic Monte Carlo methods307xiiContents7.1Random se

39、quential deposition3097.1.1Faster-than-the-clock algorithms3107.2Dynamic spin algorithms3137.2.1Spin-flips and dice throws3147.2.2Accelerated algorithms for discrete systems3177.2.3Futility3197.3Disks on the unit sphere3217.3.1Simulated annealing3247.3.2Asymptotic densities and paper-cutting3277.3.3

40、Polydisperse disks and the glass transition3307.3.4Jamming and planar graphs331Exercises333References335Acknowledgements337Index339Monte Carlo methods11.1 Popular games in Monaco31.2 Basic sampling271.3 Statistical data analysis441.4 Computing62Exercises77References79Starting with this chapter,we em

41、bark on a journey into the fascinatingrealms of statistical mechanics and computationalphysics.We set out tostudy a host of classical and quantum problems,all of value as modelsand with numerous applications and generalizations.Many computa-tional methods will be visited,by choice or by necessity.No

42、t all of thesemethods are,however,properly speaking,computer algorithms.Never-theless,they often help us tackle,and understand,properties of physicalsystems.Sometimes we can even say that computational methods givenumerically exact solutions,because few questions remain unanswered.Among all the comp

43、utational techniques in this book,one stands out:the Monte Carlo method.It stems from the same roots as statisticalphysics itself,it is increasingly becoming part of the discipline it is meantto study,and it is widely applied in the natural sciences,mathematics,engineering,and even the social scienc

44、es.The Monte Carlo method isthe first essential stop on our journey.In the most general terms,the Monte Carlo method is a statisticalalmost experimentalapproach to computing integrals using random1positions,called samples,1whose distribution is carefully chosen.In thischapter,we concentrate on how t

45、o obtain these samples,how to processthem in order to approximately evaluate the integral in question,andhow to get good results with as few samples as possible.Starting withvery simple example,we shallintroduce to the basic sampling techniquesfor continuous and discrete variables,and discuss the sp

46、ecific problemsof high-dimensional integrals.We shall also discuss the basic principlesof statistical data analysis:how to extract results from well-behavedsimulations.We shall also spend much time discussing the simulationswhere something goes wrong.The Monte Carlo method is extremely general,and t

47、he basic recipesallow usin principleto solve any problem in statistical physics.Inpractice,however,much effort has to be spent in designing algorithmsspecifically geared to the problem at hand.The design principles areintroduced in the present chapter;they will come up time and again inthe real-worl

48、d settings of later parts of this book.1“Random”comes from the old French word randon(to run around);“sample”isderived from the Latin exemplum(example).Children randomly throwing pebbles into a square,as in Fig.1.1,illus-trate a very simple direct-sampling Monte Carlo algorithm that can beadapted to

49、 a wide range of problems in science and engineering,mostof them quite difficult,some of them discussed in this book.The basicprinciples of Monte Carlo computing are nowhere clearer than where itall started:on the beach,computing?.Fig.1.1 Children computing the number?on the Monte Carlo beach.1.1Pop

50、ular games in Monaco31.1Popular games in MonacoThe concept of sampling(obtaining the random positions)is truly com-plex,and we had better get a grasp of the idea in a simplified setting be-fore applying it in its full power and versatility to the complicated casesof later chapters.We must clearly di