Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity
| dc.creator | Moore, Cristopher | |
| dc.creator | Machta, Jonathan | |
| dc.date | 1999-09-15 | |
| dc.date.accessioned | 2026-07-07T03:14:34Z | |
| dc.date.available | 2026-07-07T03:14:34Z | |
| dc.description | The computational complexity of internal diffusion-limited aggregation (DLA) is examined from both a theoretical and a practical point of view. We show that for two or more dimensions, the problem of predicting the cluster from a given set of paths is complete for the complexity class CC, the subset of P characterized by circuits composed of comparator gates. CC-completeness is believed to imply that, in the worst case, growing a cluster of size n requires polynomial time in n even on a parallel computer. A parallel relaxation algorithm is presented that uses the fact that clusters are nearly spherical to guess the cluster from a given set of paths, and then corrects defects in the guessed cluster through a non-local annihilation process. The parallel running time of the relaxation algorithm for two-dimensional internal DLA is studied by simulating it on a serial computer. The numerical results are compatible with a running time that is either polylogarithmic in n or a small power of n. Thus the computational resources needed to grow large clusters are significantly less on average than the worst-case analysis would suggest. For a parallel machine with k processors, we show that random clusters in d dimensions can be generated in O((n/k + log k) n^{2/d}) steps. This is a significant speedup over explicit sequential simulation, which takes O(n^{1+2/d}) time on average. Finally, we show that in one dimension internal DLA can be predicted in O(log n) parallel time, and so is in the complexity class NC. | |
| dc.identifier | https://arxiv.org/abs/cond-mat/9909233 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/9909233 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/29720 | |
| dc.subject | Condensed Matter | |
| dc.title | Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity | |
| dc.type | text |