Abstract
The internal diffusion limited aggregation (IDLA) process places n particles on the two dimensional integer grid. The first particle is placed on the origin; every subsequent particle starts at the origin and performs an unbiased random walk until it reaches an unoccupied position.
In this work we study the computational complexity of determining the subset that is generated after n particles have been placed. We develop the first algorithm that provably outperforms the naive step-by-step simulation of all particles. Particularly, our algorithm has a running time of O(n log2 n) and a sublinear space requirement of O(n 1/2 logn), both in expectation and with high probability. In contrast to some speedups proposed for similar models in the physics community, our algorithm samples from the exact distribution.
To simulate a single particle fast we have to develop techniques for combining multiple steps of a random walk to large jumps without hitting a forbidden set of grid points. These techniques might be of independent interest for speeding up other problems based on random walks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Asselah, A., Gaudilliere, A.: From logarithmic to subdiffusive polynomial fluctuations for internal DLA and related growth models, arXiv preprint arXiv:1009.2838 (2010)
Asselah, A., Gaudilliere, A.: Lower bounds on fluctuations for internal DLA. Probability Theory and Related Fields, 1–15 (2011)
Diaconis, P., Fulton, W.: A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Politec. Torino 49(1), 95–119 (1991)
Friedrich, T., Levine, L.: Fast simulation of large-scale growth models. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol. 6845, pp. 555–566. Springer, Heidelberg (2011)
He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3(1), 21–35 (2004)
Jerison, D., Levine, L., Sheffield, S.: Logarithmic fluctuations for internal DLA. J. Amer. Math. Soc. 25(1), 271–301 (2012)
Lawler, G.F., Bramson, M., Griffeath, D.: Internal diffusion limited aggregation. The Annals of Probability, 2117–2140 (1992)
Meakin, P., Deutch, J.M.: The formation of surfaces by diffusion limited annihilation. The Journal of Chemical Physics 85, 2320 (1986)
Moore, C., Machta, J.: Internal diffusion-limited aggregation: Parallel algorithms and complexity. Journal of Statistical Physics 99, 661–690 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bringmann, K., Kuhn, F., Panagiotou, K., Peter, U., Thomas, H. (2014). Internal DLA: Efficient Simulation of a Physical Growth Model. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)