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.

• Use a release radius,
• make large steps outside the release readius,
• use a kill radius when the particle has gone too far off,
• make large steps inside the release radius when far from cluster,

• calculate the possibility to let a particle stick for each lattice site near to the cluster,
• use pre calculated values for complex math,

Release Radius

Instead of placing the walker at any location on the grid, it is placed at a release radius R₀ 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.

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.

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 (R_k) chosen for this might be 10 times R₀. When this radius is chosen too close to R₀ we will have to kill and rereleas particles quite often. Within the region between R₀ and R_k the particle can travel quite fast to very different locations around the cluster before finally dipping into the cluster area itself.

Large steps inside release radius but far from cluster

For larger clusters even the grid within R₀ 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: l_max=15-30) for all sites within R₀ and reduce the value only for those sites which are closer to the cluster than l_max, 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.

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.

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 l_max during an initialization and just look up the values from some arrays with (relative) lattice coordinates as indices.