×

Fast simulation of large-scale growth models. (English) Zbl 1258.68182

Summary: We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a “least action principle” which characterizes the odometer function of the growth process. Starting from an approximation for the odometer, we successively correct under- and overestimates and provably arrive at the correct final state. Internal diffusion-limited aggregation (IDLA) is one of the models amenable to our technique. The boundary fluctuations in IDLA were recently proved to be at most logarithmic in the size of the growth cluster, but the constant in front of the logarithm is still not known. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations, and use the results to estimate this constant.

MSC:

68W20 Randomized algorithms
68W25 Approximation algorithms
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] http://rotor-router.mpi-inf.mpg.de 2012
[2] Asselah, From logarithmic to subdiffusive polynomial fluctuations for internal DLA and related growth models (2010) · Zbl 1283.60117
[3] Asselah, Sub-logarithmic fluctuations for internal DLA (2010)
[4] Bak, Self-organized criticality: An explanation of the 1/f noise, Phys Rev Lett 59 pp 381– (1987) · doi:10.1103/PhysRevLett.59.381
[5] Barve, Simple randomized mergesort on parallel disks, Parallel Comput 23 pp 601– (1997) · Zbl 0904.68076 · doi:10.1016/S0167-8191(97)00015-X
[6] Bond, Abelian networks I. Foundations and examples (2011) · Zbl 1356.68072
[7] Bramson, Tightness of the recentered maximum of the two-dimensional discrete Gaussian free field, Commun Pure Appl Math 65 pp 1– (2012) · Zbl 1237.60041 · doi:10.1002/cpa.20390
[8] Cooper, Simulating a random walk with constant error, Combin Probab Comput 15 pp 815– (2006) · Zbl 1113.60047 · doi:10.1017/S0963548306007565
[9] Cooper, Deterministic random walks on the integers, Eur J Combin 28 pp 2072– (2007) · Zbl 1130.60011 · doi:10.1016/j.ejc.2007.04.018
[10] Cooper, Deterministic random walks on regular trees, Rand Struct Alg 37 pp 353– (2010) · Zbl 1209.05233 · doi:10.1002/rsa.20314
[11] Dhar, Theoretical studies of self-organized criticality, Physica A 369 pp 29– (2006) · doi:10.1016/j.physa.2006.04.004
[12] Dhar, Pattern formation in growing sandpiles, Europhys Lett 85 pp 48002– (2009) · Zbl 1187.82077 · doi:10.1209/0295-5075/85/48002
[13] Diaconis, A growth model, a game, an algebra, Lagrange inversion, and characteristic classes, Rend Sem Mat Univ Politec Torino 49 pp 95– (1991) · Zbl 0776.60128
[14] Doerr, Deterministic random walks on the two-dimensional grid, Combin Probab Comput 18 pp 123– (2009) · Zbl 1185.05130 · doi:10.1017/S0963548308009589
[15] B. Doerr T. Friedrich T. Sauerwald Quasirandom rumor spreading 2008 773 781 · Zbl 1192.90024
[16] B. Doerr T. Friedrich T. Sauerwald Quasirandom rumor spreading: Expanders, push vs. pull, and robustness 2009 366 377 · Zbl 1195.68021
[17] Fey, Growth rates and explosions in sandpiles, J Stat Phys 138 pp 143– (2010) · Zbl 1186.82043 · doi:10.1007/s10955-009-9899-6
[18] Friedrich, The cover time of deterministic random walks, Electron J Combin 17 pp 1– (2010) · Zbl 1201.05084
[19] T. Friedrich M. Gairing T. Sauerwald Quasirandom load balancing 2010 1620 1629 · Zbl 1255.68286
[20] Fukai, Potential kernel for two-dimensional random walk, Ann Probab 24 pp 1979– (1996) · Zbl 0879.60068 · doi:10.1214/aop/1041903213
[21] Hellekalek, Empirical evidence concerning AES, ACM Trans Model Comput Simul 13 pp 322– (2003) · doi:10.1145/945511.945515
[22] Holroyd, Rotor walks and Markov chains, Alg Probab Combin 520 pp 105– (2010) · Zbl 1217.82042 · doi:10.1090/conm/520/10256
[23] Jerison, Internal DLA and the Gaussian free field (2011, Submitted for publication)
[24] Jerison, Logarithmic fluctuations for internal DLA, J Am Math Soc 25 pp 271– (2012) · Zbl 1237.60037 · doi:10.1090/S0894-0347-2011-00716-9
[25] Kleber, Goldbug variations, Math Intelligencer 27 pp 55– (2005) · Zbl 1062.00002 · doi:10.1007/BF02984814
[26] Kozma, An asymptotic expansion for the discrete harmonic potential, Electron J Probab 9 pp 1– (2004) · Zbl 1064.60166 · doi:10.1214/EJP.v9-170
[27] Lawler, Internal diffusion limited aggregation, Ann Probab 20 pp 2117– (1992) · Zbl 0762.60096 · doi:10.1214/aop/1176989542
[28] Levine, Spherical asymptotics for the rotor-router model in \input amssym \(\mathbb{Z}^d\), Indiana Univ Math J 57 pp 431– (2008) · Zbl 1139.60347 · doi:10.1512/iumj.2008.57.3022
[29] Levine, Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile, Potential Anal 30 pp 1– (2009) · Zbl 1165.82309 · doi:10.1007/s11118-008-9104-6
[30] Levine, Scaling limits for internal aggregation models with multiple sources, J d’Anal Math 111 pp 151– (2010) · Zbl 1210.82031 · doi:10.1007/s11854-010-0015-2
[31] McCrea, Random paths in two and three dimensions, Proc Royal Soc 60 pp 281– (1940) · Zbl 0027.33903
[32] Meakin, The formation of surfaces by diffusion-limited annihilation, J Chem Phys 85 pp 2320– (1986) · doi:10.1063/1.451129
[33] Moore, Internal diffusion-limited aggregation: Parallel algorithms and complexity, J Stat Phys 99 pp 661– (2000) · Zbl 0959.82026 · doi:10.1023/A:1018627008925
[34] Propp, How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph, J Alg 27 pp 170– (1998) · Zbl 0919.68092 · doi:10.1006/jagm.1997.0917
[35] I. A. Wagner M. Lindenbaum A. M. Bruckstein Smell as a computational resource - a lesson we can learn from the ant 1996 219 230
[36] D. B. Wilson Generating random spanning trees more quickly than the cover time 1996 296 303 · Zbl 0946.60070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.