How can we speed up the growth of a cluster in a simulation

As the simple simulation of a DLA-growth relies on the random walk of one particle after the other this is the key to many improvements. During random walk the path a particle traveled is short compared to the number of steps done. But a particle has to walk across long paths, when a DLA-cluster becomes larger. Thus, by increasing the stepsize under certain conditions it would be possible to cross these long paths in shorter time.

The following significant tricks are mentioned in the book of Vicsek: The following ideas eventually could make some slight further improvements (partially used within my programs): So, read on for details or return to the main DLA page or even back to the start.

Release Radius

Instead of placing the walker at any location on the grid, it is placed at a release radius R0 from the seed. This radius is chosen just a bit larger than the radius of the cluster (and thus changes, when cluster grows). There is no difference for a particle reaching a point at this radius than reaching any other point outside the cluster.

Btw: some use circular release lines, other use square release lines. Obviously, the area of a circle is smaller than the one for the square, so the circular cluster envelope should leave less sites to cross over during random walk. On the other hand a release point on a square is easier to calculate.

back to toc

Large steps outside release radius

Outside the release radius we can safely increase the stepsize up to the distance (Delta R) to the release radius while calculating an arbitrary direction. Under best circumstances a particle would come into close vicintity of the cluster during one step.

back to toc

Kill radius for lost particles

When a particle walks to far abroad, it does not make sense to wait until it eventually might return. Just let it go and release a new particle. The radius (Rk) chosen for this might be 10 times R0. When this radius is chosen too close to R0 we will have to kill and rereleas particles quite often. Within the region between R0 and Rk the particle can travel quite fast to very different locations around the cluster before finally dipping into the cluster area itself.

back to toc

Large steps inside release radius but far from cluster

For larger clusters even the grid within R0 has many waste sites which will not lead to an attachment. So, calculate the (shortest) distance (delta R) to the cluster for each lattice site and adjust the step size (l') accordingly.

Practically: start with a default value (reasonable: lmax=15-30) for all sites within R0 and reduce the value only for those sites which are closer to the cluster than lmax, e.g. are at distance delta R. Respectively the stepsize is l' for sites nearby the cluster or the fix Delta R for sites with the default value. The information for the largest possible stepsize l' has to be updated after each attachment of a particle to the cluster. Thus, the range should not be too large, since the larger the range is chosen the more sites have to be updated after an attachment. Again, one could play either with circular or square regions for this.

In my program I used the color to code the distance. This gave nice pictures during growth, like cultures of yeast or bacteria in Petri plates. The cluster seemes to lie within a canyon.

back to toc

Use knowledge about environment

When a particle is close to the cluster, it has to investigate all neighbor sites, whether these already belong to the cluster and the particle should stick or wether it can walk freely. The information about the neighborhood could be assigned to each site, so that a walker has only ask the site which it is on instead of all four (or six or eight...) possible neighbors. The drawback on this is, that the information has to bea updated, after an attachment took place. But this affects only the few neighbor sites of the current site.

back to toc

Reduce time to do floating point math

Since there are many sinus/cosinus/square root operations in the improvements mentioned above, I thought it could be helpful to store the values needed to do the calculations within the radius lmax during an initialization and just look up the values from some arrays with (relative) lattice coordinates as indices.

back to toc
Realization of this page Franz-Josef Wirtz (
Copyright notice:
All material within the webspace is copyrighted to Franz-Josef Wirtz, except where declared otherwise. You are allowed to use and distribute this information as long as it's for free, since you got it for free too.

Valid HTML 3.2!