PARALLEL ALGORITHM AND DYNAMIC EXPONENT FOR DIFFUSION-LIMITED AGGREGATION

A parallel algorithm for diffusion-limited aggregation (DLA) is descri bed and analyzed from the perspective of computational complexity. The dynamic exponent z of the algorithm is defined with respect to the pr obabilistic parallel random-access machine model of parallel computati on according to T similar to L-z, where L is the cluster size, T is th e running time, and the algorithm uses a number of processors polynomi al in L. It is argued that z=D - D-2/2, where D is the fractal dimensi on and D-2 is the second generalized dimension. Simulations of DLA are carried out to measure D-2 and to test scaling assumptions employed i n the complexity analysis of the parallel algorithm. It is plausible t hat the parallel algorithm attains the minimum possible value of the d ynamic exponent in which case z characterizes the intrinsic history de pendence of DLA.