Computational Physics Lab 8

Diffusion-Limited Aggregation

The goal of this lab is to study formation and properties of particle clusters produced by the diffusion-limited aggregation (DLA) model. DLA is one of the most important models of fractal growth. The model itself and its physics applications are discussed in section 7.6 of Giordano & Nakanishi and, in more detail, in a Physics Today article by Thomas Halsey.

Part 1. Simulating Random Walks on a Lattice

The properties of a random walk on a lattice (or, in general, on an arbitrary set of discrete sites) can often be summarized by the random walk transition matrix, T. The elements of this matrix, T_ij, are the probabilities to jump from the lattice site i to the site j in one step. These probabilities are normalized:

Essentially, the random walk is modeled here as a Markov chain whose states are defined as "the walker is now in site i". T is then the transition matrix of the chain. Note that not all types of random walks allow for the Markov chain interpretation. For example, self-avoiding walks can not be represented by Markov chains.

In what follows, we will consider only the random walks in which T does not depend on time (that is, the corresponding Markov chain is time-homegeneous). Moreover, we will limit ourselves to the cases in which the elements T_ijdepend only on the relative location of sites i and j in the lattice (such walks are called space-homogeneous) and in which all T_ijvalues become 0 when the distance between the sites exceeds a certain threshold r_max. The properties of such walks are fully defined by a finite set of transition probabilities p_j ≡ T_ij taken for any site i which is at least the distance r_max away from any lattice boundary.

Consider a random walk on an infinite 2-d rectangular lattice. For this walk, the transition probabilities p_j can be usefully arranged in a 2-d array P[k][m] in which k and m are the integer spatial coordinates of the lattice site j: k = 0, 1, ..., K-1, and m = 0, 1, ..., M-1. It is usually convenient to choose odd values of K and M, and to place the site i at the center of the array at [K/2][M/2] (the division here is according to the integer division rules). The values of K and M should be large enough so that all non-zero transition probabilities are included in P[k][m]. Simulation of the random walk on the lattice consists in performing a sequence of steps. In each step, the k and m values are chosen randomly according to their respective probabilities P[k][m], and the walker on the lattice is shifted by (k - K/2, m - M/2).

A C++ code which can sample the lattice sites according to an arbitrary input set of transition probabilities is provided: lab8_code.tar.gz. After downloading, this code can be compiled as follows:

tar xzvf lab8_code.tar.gz
cd Lab8_code/src
make

Take a look at the Python example in the "tests" subdirectory. Using the sampler class "SiteSampler" (C++ interface is explained in the header file), write a C++ class which simulates random walks in 2d and interface it to Python. Be careful subtracting unsigned integers while calculating k - K/2, etc. -- it is best to convert all unsigned numbers to normal integers before subtraction. Plot a few random walk trajectories. Using an ensemble of walkers, verify that your code behaves as expected by plotting the mean displacement vector (over the whole ensemble) and the mean displacement distance (average of lengths of displacement vectors) as the functions of number of steps taken. The former should remain close to 0 (with some fluctuations) while the latter should increase in proportion to the square root of the number of steps.

Part 2. Generating DLA Clusters

Write a program which simulates the growth of DLA clusters in 2 dimensions. Your program should be able to produce plots similar to Fig. 1a in the Thomas Halsey's article.

1) Define a square 2-d lattice of points represented by a 2-d array. The size of the lattice should be adjustable so that you can develop and debug your code using small grid sizes, and then perform the simulations using reasonably large grids. Set all array values to 0 initially.

2) Place the seed at the center of the lattice (set to 1 the corresponding array value).

3) Simulate random walkers on the lattice. You need to decide two things: a) where to start your walkers and b) when to abandon a walker which has traveled too far away from the cluster. I suggest the following: imagine a circle around your growing cluster. Let say, the current cluster size (the distance from the center to the most distant cluster point) is a. Set the radius of the circle to 2 (a+r_max). Generate a random point on this circle, choose the lattice site closest to this random point, and start your walker from there. Abandon the walker if it has traveled beyond the circle with the raduis 4 (a+r_max).

4) For every walker step, check if its trajectory comes near any of the sites already in the cluster. When the walker is close to the cluster (the distance to the center is a+r_max or less), you should move your walker one lattice site at a time, until the total distance of the step is covered. For every move from one site to the next, check if any of the four nearest neighbor sites already belong to the cluster. If yes then terminate the walk and mark the walker's current site as belonging to the cluster. Use a counter so that the sites in the cluster are marked by an increasing integer in the order of their addition to the cluster. Update a if the addition of the new site results in the increase of the cluster size.

5) Terminate your simulation when the cluster size grows to 1/2 of the lattice size (that is, when a becomes as large as the distance from the lattice center to the lattice boundary).

Run your code and visualize the results for the following transiton probabilities (not normalized here):

a) Symmetric random walk: P[k][m] =
((0.707, 1.0, 0.707),
     (1.0,   0.0, 1.0),
     (0.707, 1.0, 0.707))

b) Biased random walk: P[k][m] =
((0.566, 1.0, 0.707),
     (0.8,   0.0, 1.0),
     (0.566, 1.0, 0.707))

c) Random walk with different step sizes in x and y: P[k][m] =
((0.707, 0.0, 1.0, 0.0, 0.707),
     (1.0,   0.0, 0.0, 0.0, 1.0),
     (0.707, 0.0, 1.0, 0.0, 0.707))

View at least 5 clusters for each of the random walk types. Can you explain the relationship between random walk transition probabilities and cluster shapes?

Part 3. Fractal Analysis of DLA Clusters

Using your simulation developed in part 2, determine the fractal dimension of the 2-d DLA clusters. Generate an ensemble of DLA clusters (~50 or so) and build a plot similar to the plots in Fig. 7.20 of G&N (page 210). This kind of study requires a lot of CPU time, so plan your calculations carefully. Use the symmetric random walk only: the simple fractal dimension determination method described by G&N will not work for asymmetric structures produced by other types of random walk. If you like, instead of the G&N method you can implement the box counting method described in the lecture on fractals. Box counting works for all types of clusters but it will require more coding effort and a larger cluster ensemble.

Submit your lab report by email before 2 pm 03/27/2008. Include the code, the plots, and a brief discussion of results.