Introduction to Computational Physics PDF

COMPUTATIONAL PHYSICS Morten Hjorth-Jensen

to M. Hjorth-Jensen Lecture Notes on Computational Physics

Computational Physics

1.1 Intended Audience. These set of lecture notes are designed for an upper-division undergraduate course on computational physics. 1.2 Major Sources.

COMPUTATIONAL PHYSICS Morten Hjorth-Jensen

Indeed what you will see in the various chapters of these notes represents how. I perceive computational physics should be taught. This set of lecture notes

Introduction to Computational Physics

Pdf-files of both the slides and the exercises are also provided on these two pages. Who is the Target Audience of This Lecture?

Lecture Notes FYTN03 Computational Physics

Lecture Notes FYTN03. Computational Physics. 1 Introduction. Numerical methods in physics is simple. Just take your formula and replace every-.

Computational Physics

10-Oct-2012 see in the various chapters of these notes represents how I perceive computational physics should be taught. This set of lecture notes ...

Computational Physics - Lecture Notes Fall 2015

see in the various chapters of these notes represents how I perceive computational physics should be taught. This set of lecture notes serves the scope of

LECTURE NOTES ON PHS 473: COMPUTATIONAL PHYSICS

LECTURE NOTES ON PHS 473: COMPUTATIONAL PHYSICS. BY. DR V.C. OZEBO. CONTENT Numerical solution of some differential equations of interest in Physics.

COMPUTATIONAL PHYSICS Morten Hjorth-Jensen

I perceive computational physics should be taught. This set of lecture notes serves the scope of presenting to you and train you in an algorithmic approach.

Computational Physics

All the lecture notes source codes

Introduction to Computational Physics

Lecture of Prof. H. J. Herrmann

Swiss Federal Institute of Technology ETH, Zürich, Switzerland

Script by

Dr. H. M. Singer, Lorenz Müller and Marco - Andrea Buchmann

Computational Physics, IfB, ETH Zürich

General Information

Useful Addresses and Information

The content of this class is available online on the following pages: Pdf-files of both the slides and the exercises are also provided on these two pages.

Who is the Target Audience of This Lecture?

The lecture gives an introduction to computational physics for students of the following departments: Mathematics and Computer Science (Bachelor and Master course)

Physics (major course, "Wahlfach")

Material Science (Master course)

Civil Engineering (Master course)

1 2

Some Words About Your Teacher

Prof. Hans. J. Herrmann is full professor at the Institute of Building Materials (IfB) since April 2006. His field of expertise is computational and statistical physics, in particular granular materials. His present research subjects include dense colloids, the formation of river deltas, quicksand, the failure of fibrous and polymeric composites and complex networks.

Prof. Herrmann can be reached at

hjherrmann@ethz.ch His office is located in the Institute of Building materials (IfB), HIF E12, ETH The personal web page is located at www.icp.uni-stuttgart.de/~hans and at www.comphys.ethz.ch

Some Words About the Authors

The script was started in 2007 by Dr. H.M. Singer, who wrote large parts of the chapter on random number generators, a part of the chapter on percolation, and large parts of the chapters on solving equations. In 2009/2010, Lorenz Müller and Marco - Andrea Buchmann continued the script and filled in the gaps, expanded said chapters and added chapters on Monte Carlo methods, fractal dimensions and the Ising model. If you have suggestions or corrections, please let us know: marcobuchmann@student.ethz.ch

Thank you!

Outline of This Course

This course consists of two parts:

In a first part we are going to consider stochastic processes, such as percola- tion. We shall look at random number generators, Monte Carlo methods and the

Ising model, particularly their applications.

In the second part of the class we shall look into numerical ways of solving equa- tions (e.g. ordinary differential equations). We shall get to know a variety of ways to solve these and learn about their advantages as well as their disadvantages. 3

Prerequisites for this Class

You should have a basic understanding of the UNIX operating system and be able to work with it. This means concepts such as the "shell", stream redirections and compiling programs should be familiar. You should ideally have some knowledge about a higher level programming language such as Fortran, C/C++, Java, ... . In particular you should also be able to write, compile and debug programs yourself. It is beneficial to know how to make scientific plots. There are many tools, which can help you with that. For example Matlab, Maple, Mathematica,

R, SPlus, gnuplot, etc.

Requirements in mathematics:

-You should know the basics of statistical analysis (averaging, distribu- tions, etc.). -Furthermore, some knowledge of linear algebra and analysis will be necessary.

Requirements in physics

-You should be familiar with Classical Mechanics (Newton, Lagrange) and Electrodynamics. -A basic understanding of Thermodynamics is also beneficial.

I Stochastic Processes

1 Random Numbers

9 1.1

Definition of Random Num bers

9 1.2

Congruen tialRNG (Multiplicativ e)

10 1.3

Lagge dFib onacciRNG (A dditive)

13 1.4

Ho wGo odis a RNG?

1.5 Non-Uniform Distributions

2 Percolation

22
2.1

The Sol-Gel T ransition

2 3 2.2

The P ercolationMo del

3 Fractals

3.1 Self-Similarity

3.2 Fractal Dimension: Mathematical Definition

3.3 The Box Counting Method

3 9

3.4 The Sandbox Method

3.5 The Correlation-Function Method

4 1

3.6 Correlation Length. . . . . . . . . . . . . . . . . . . . . . . . .42

3.7 Finite Size Effects

3.8 Fractal Dimension in Percolation

3.9 Examples

3.10 Cellular Automata

4 7

4 Monte Carlo Methods

51
4.1

What is "Mon teCarlo" ?

51
4.2

Applications of Mon teCar lo

5 1 4.3

Computation of In tegrals

4.4 Higher Dimensional Integrals

57
4.5

Canonical Mon teCarlo

4.6 The Ising Model

67
4.7

In terfaces

70
4.8

Sim ulationExamples

8 1 4

CONTENTS5

II Solving Systems of Equations Numerically

5 Solving Equations

5.1 One-Dimensional Case

5.2N-Dimensional Case. . . . . . . . . . . . . . . . . . . . . . . . . 87

6 Ordinary Differential Equations

89
6.1

Examples

89
6.2

Euler Metho d

89
6.3

Runge-Kutta Metho ds

7 Partial Differential Equations

104
7.1

T ypesof PDEs

104
7.2

Examples of PDEs

105

7.3 Discretization of the Derivatives

109
7.4

The P oissonEquation

110

7.5 Solving Systems of Linear Equations

112
7.6

Finite Elemen tMetho d

127
7.7

Time Dep endentPDEs

139

7.8 Discrete Fluid Solver

147

CONTENTS6

What is Computational Physics?

Computational physics is the study and implementation of numerical algorithms to solve problems in physics by means of computers. Computational physics in particular solves equations numerically. Finding a solution numerically is useful, as there are very few systems for which an analytical solution is known. Another field of computational physics is the simulation of many-body/particle systems; in this area, a virtual reality is created which is sometimes also referred to as the

3rd branch of physics (between experiments and theory).

The evaluation and visualization of large data sets, which can come from nu- merical simulations or experimental data (for example maps in geophysics) is also part of computational physics. Another area in which computers are used in physics is the control of experi- ments. However, this area is not treated in the lecture. Computational physics plays an important role in the following fields: Computational Fluid Dynamics (CFD): solve and analyze problems that involve fluid flows Classical Phase Transition: percolation, critical phenomena

Solid State Physics (Quantum Mechanics)

High Energy Physics / Particle Physics: in particular Lattice Quantum

Chromodynamics ("Lattice QCD")

Astrophysics: many-body simulations of stars, galaxies etc. Geophysics and Solid Mechanics: earthquake simulations, fracture, rupture, crack propagation etc. Agent Models (interdisciplinary): complex networks in biology, economy, social sciences and many others

CONTENTS7

Suggested Literature

Books:

H. Gould, J. Tobochnik and Wolfgang Christian: "Introduction to Computer Simulation Methods" 3rd edition (Addison Wesley, Reading MA, 2006). D. P. Landau and K. Binder: "A Guide to Monte Carlo Simulations in Statistical Physics" (Cambridge University Press, Cambridge, 2000). D. Stauffer, F. W. Hehl, V. Winkelmann and J. G. Zabolitzky: "Computer Simulation and Computer Algebra" 3rd edition (Springer, Berlin, 1993). K. Binder and D. W. Heermann: "Monte Carlo Simulation in Statistical

Physics" 4th edition (Springer, Berlin, 2002).

N. J. Giordano: "Computational Physics" (Addison Wesley, Reading MA,

1996).

J. M. Thijssen: "Computational Physics", (Cambridge University Press,

Cambridge, 1999).

Book Series:

"Monte Carlo Method in Condensed Matter Physics", ed. K. Binder (Springer

Series).

"Annual Reviews of Computational Physics", ed. D. Stauffer (World Scien- tific). "Granada Lectures in Computational Physics", ed. J. Marro (Springer Se- ries). "Computer Simulations Studies in Condensed Matter Physics", ed. D. Lan- dau (Springer Series).

Journals:

Journal of Computational Physics (Elsevier).

Computer Physics Communications (Elsevier).

International Journal of Modern Physics C (World Scientific).

Conferences:

Annual Conference on Computational Physics (CCP): In 2007, the CCP was held in Brussels (Sept. 5th-8th 2007), in 2008 it was in Brazil.

Part I

Stochastic Processes

Chapter 1 Random Numbers

Random numbers (RN) are an important tool for scientific simulations.

As w e

shall see in this class, they are used in many different applications, including the following: Simulate random events and experimental fluctuations, for example radioac- tive decay Complement the lack of detailed knowledge (e.g. traffic or stock market simulations) Consider many degrees of freedom (e.g. Brownian motion, random walks). Test the stability of a system with respect to perturbations

Random sampling

Special literature about random numbers is given at the end of this chapter. 1.1

Definition of Random Num bers

Random numbers are a sequence of numbers in random or uncorrelated order. In particular, the probability that a given number occurs next in the sequence is always the same. Physical systems can produce random events, for example in electronic circuits ("electronic flicker noise") or in systems where quantum ef- fects play an important role (such as for example radioactive decay or the photon emission from a semiconductor).

H owever,ph ysicalrand omn umbersare usually

"bad" in the sense that they are usually correlated. The algorithmic creation of random numbers is a bit problematic, since the com- puter is completely deterministic but the sequence should be non-deterministic. One therefore considers the creation of pseudo-random numbers, which are cal- culated with a deterministic algorithm, but in suc ha w aythat the n umbersare 9

CHAPTER 1. RANDOM NUMBERS10

almost homogeneously, randomly distributed. These numbers should follow a well-defined distribution and should have long periods. Furthermore, they should be calculated quickly and in a reproducible way. A very important tool in the creation of pseudo-random numbers is the modulo- operatormod(in C++%), which determines the remainder of a division of one integer number with another one. Given two numbersa(dividend) andn(divisor), we writeamodulonoramodn which stands for the remainder of division of abyn. The mathematical definition of this operator is as follows: We consider a numberq2Z, and the two integers aandnmentioned previously. We then writeaas a=nq+r(1.1) with0r The pseudo-random n umber generators (RNG) can b edivided in tot woclasses: the multiplicative and the additive generators. The multiplicative ones are simpler and faster to program and execute, but do not produce very good sequences. The additive ones are more difficult to implement and take longer to run, but produce much better random sequences. 1.2

Congruen tialRNG (Multiplicativ e)

The simplest form of a congruential RNG was proposed by Lehmer in

1948. Th e

algorithm is based on the properties of themod-operator. Let us assume that we choose two integer numberscandpand a seed valuex0withc;p;x0being positive integers. We then create the sequencefxig; i2N, iteratively by the recurrence relation x i= (cxi1)modp;(1.2) which creates random numbers in the interval[0;p1]1. In order to transform these random numbers to the interval[0;1[we simply divide byp

0zi=xip

<1(1.3)1 Throughout the manuscript we will adopt the notation that closed square brackets[]in intervals are equivalent toandand open brackets][correspond torespectively. Thus the interval[0;1]corresponds to0x1; x2Rand]0;1]means0< x1; x2R.

CHAPTER 1. RANDOM NUMBERS11

withzi2R(actuallyzi2Q). Since all integers are smaller thanpthe sequence must repeat after at least(p1) iterations. Thus, themaximal periodof this RNG is(p1). If we pick the seed valuex0= 0, the sequence sits on a fixed point 0 (therefore,x0= 0cannot be used). In 1910, R. D. Carmichael proved that the maximal period can be obtained if pis a Mersenne prime number2and if the number is at the same time the smallest integer number for which the following condition holds: c p1modp= 1:(1.4) In 1988, Park and Miller presented the following numbers, which produce a rela- tively long sequence of pseudo-random numbers, here in pseudo-C code:Figure 1.1: Sample plot of consecutive random num- bers with clearly visible hy- perplanes ("RANDU" algo- rithm withc= 65539;p= 2

31;x0= 1) [20]const int p=2147483647;

const int c=16807; int rnd=42; // seed rnd=(c*rnd)%p; print rnd;

The numberpis of course a Mersenne prime with

the maximal length of an integer (32 bit):231 1.

The distribution of pseudo-random numbers calcu-

lated with a congruential RNG can be represented in a plot of consecutive random numbers(xi;xi+1), where they will form some patterns (mostly lines) depending on the chosen parameters. It is of course also possible to do this kind of visualization for three consecutive numbers(xi;xi+1;xi+2)in 3D (see e.g. Fig. 1.1 ). There is even a theorem which quan- tifies the patterns observed. Let us call the nor- malized numbers of the pseudo-random sequence fzig=fxig=p; i2N. Let then1= (z1;:::;zn),

2= (z2;:::;zn+1),3= (z3;:::;zn+2), ... be the

points of the unitn-cube formed fromnsuccessive z i.2 AMersenne numberis defined asMn= 2n1. If this number is also prime, it is called a

Mersenne prime.

CHAPTER 1. RANDOM NUMBERS12

Theorem 1(Marsaglia, 1968).Ifa1;a2;:::;an2Z

is any choice of integers such that a

1+a2c+a3c2+:::+ancn10modp;

then all of the points1;2;:::will lie in the set of parallel hyperplanes defined by the equations a

1y1+a2y2+:::+anyn= 0;1;2;:::; yi2R;1in

There are at most

ja1j+ja2j+:::+janj of these hyperplanes, which intersect the unitn-cube and there is always a choice ofa1;:::;ansuch that all of the points fall in fewer than(n!p)1=nhyperplanes. Proof.(Abbreviated) The theorem is proved in four steps:Step 1: If a

1+a2c+a3c2+:::+ancn10modp

then one can prove that a

1zi+a2zi+1+:::+anzi+n1

is an integer for everyiand thus Step 2: The pointi= (zi;zi+1;::;zi+n1)must lie in one of the hyperplanes a

1y1+a2y2+:::+anyn= 0;1;2;:::; yi2R;1in:

Step 3: The number of hyperplanes of the above type, which intersect the unit n-cube is at most ja1j+ja2j+:::+janj; and Step 4: For every multipliercand moduluspthere is a set of integersa1;:::;an (not all zero) such that a

1+a2c+a3c2+:::+ancn10modp

and ja1j+ja2j+:::+janj (n!p)1=n: This is of course only the outline of the proof. The exact details can be read in

G. Marsaglia, Proc. Nat. Sci. U.S.A.61, 25 (1968).In a very similar way it is possible to show that for congruential RNGs the distance

between the planes must be larger than rp n (1.5)

CHAPTER 1. RANDOM NUMBERS13

1.3

Lagged Fib onacciRNG (A dditive)

A more complicated version of a RNG is the Lagged Fibonacci algorithm proposed by Tausworth in 1965. Lagged Fibonacci type generators permit extremely large periods and even allow for advantageous predictions about correlations. Lagged Fibonacci generators often use integer values, but in the following we shall focus on binary values. Consider a sequence of of binary numbersxi2 f0;1g;1ib. The nextquotesdbs_dbs9.pdfusesText_15

[PDF] Introduction to Computational Physics

Introduction to Computational Physics

Lecture of Prof. H. J. Herrmann

Script by

Computational Physics, IfB, ETH Zürich

General Information

Useful Addresses and Information

Who is the Target Audience of This Lecture?

Physics (major course, "Wahlfach")

Material Science (Master course)

Civil Engineering (Master course)

Some Words About Your Teacher

Prof. Herrmann can be reached at

Some Words About the Authors

Thank you!

Outline of This Course

This course consists of two parts:

Ising model, particularly their applications.

Prerequisites for this Class

R, SPlus, gnuplot, etc.

Requirements in mathematics:

Requirements in physics

Contents

I Stochastic Processes

1 Random Numbers

Definition of Random Num bers

Congruen tialRNG (Multiplicativ e)

Lagge dFib onacciRNG (A dditive)

Ho wGo odis a RNG?

1.5 Non-Uniform Distributions

2 Percolation

The Sol-Gel T ransition

The P ercolationMo del

3 Fractals

3.1 Self-Similarity

3.2 Fractal Dimension: Mathematical Definition

3.3 The Box Counting Method

3.4 The Sandbox Method

3.5 The Correlation-Function Method

3.6 Correlation Length. . . . . . . . . . . . . . . . . . . . . . . . .42

3.7 Finite Size Effects

3.8 Fractal Dimension in Percolation

3.9 Examples

3.10 Cellular Automata

4 Monte Carlo Methods

What is "Mon teCarlo" ?

Applications of Mon teCar lo

Computation of In tegrals

4.4 Higher Dimensional Integrals

Canonical Mon teCarlo

4.6 The Ising Model

In terfaces

Sim ulationExamples

CONTENTS5

II Solving Systems of Equations Numerically

5 Solving Equations

5.1 One-Dimensional Case

5.2N-Dimensional Case. . . . . . . . . . . . . . . . . . . . . . . . . 87

6 Ordinary Differential Equations

Examples

Euler Metho d

Runge-Kutta Metho ds

7 Partial Differential Equations

T ypesof PDEs

Examples of PDEs

7.3 Discretization of the Derivatives

The P oissonEquation

7.5 Solving Systems of Linear Equations

Finite Elemen tMetho d

Time Dep endentPDEs

7.8 Discrete Fluid Solver

CONTENTS6

What is Computational Physics?

3rd branch of physics (between experiments and theory).

Solid State Physics (Quantum Mechanics)

Chromodynamics ("Lattice QCD")

CONTENTS7

Suggested Literature

Books:

Physics" 4th edition (Springer, Berlin, 2002).