Fast simulation of large‐scale growth models
Copyright policy )Fast simulation of large‐scale growth models
AbstractWe 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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012
- Massachusetts Institute of Technology United States
- Max Planck Institute for Informatics Germany
- Max Planck Society Germany
FOS: Computer and information sciences, Combinatorial optimization, 82C24, 05C81, 05C85, Discrete Mathematics (cs.DM), FOS: Physical sciences, least action principle, cycle popping, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Condensed Matter - Statistical Mechanics, low discrepancy random stack, internal diffusion limited aggregation, Statistical Mechanics (cond-mat.stat-mech), Randomized algorithms, Probability (math.PR), rotor-router model, potential kernal, Approximation algorithms, Combinatorics (math.CO), Mathematics - Probability, odometer function, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Combinatorial optimization, 82C24, 05C81, 05C85, Discrete Mathematics (cs.DM), FOS: Physical sciences, least action principle, cycle popping, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Condensed Matter - Statistical Mechanics, low discrepancy random stack, internal diffusion limited aggregation, Statistical Mechanics (cond-mat.stat-mech), Randomized algorithms, Probability (math.PR), rotor-router model, potential kernal, Approximation algorithms, Combinatorics (math.CO), Mathematics - Probability, odometer function, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).12 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!