Fast simulation of large-scale growth models
I'll describe a new algorithm to compute the final state of certain growth
models without computing all intermediate states. The technique, which
applies to both internal DLA and rotor-router aggregation, is based on a
"least action principle" characterizing the odometer function of the
growth process. The algorithm takes as input an approximation of the
odometer, and outputs the exact odometer.
Choosing the initial approximation to optimize the running time is an art
form.
For a picture of a very large rotor-router aggregate (10^10 particles)
computed by our algorithm, see
http://rotor-router.mpi-inf.mpg.de/10Bio/
Joint work with Tobias Friedrich.