opensource.google.com

Menu

Life's a Beach: Google Summer of Code and the Abelian Sandpile Model

Thursday, February 4, 2010

The Abelian Sandpile Model (ASM) is a mathematical model of a pile of sand developed by physicists around 1990 to exemplify self-organized criticality, a phenomenon conjecturally ubiquitous in nature. Roughly, self-organized criticality describes a system that naturally evolves into a barely-stable non-equilibrium condition, where the instability is characterized by scale invariance. The Gutenberg-Richter law in geophysics and Zipf's law in linguistics are often cited as real-world examples. More recently, the ASM has been shown to have connections to algebraic geometry, combinatorics, and number theory.

The ASM starts with a graph having a finite number of vertices and edges. One is allowed to place grains of sand on each vertex. If there is enough sand on a vertex, the vertex is allowed to "fire", sending a grain of sand along each out-going edge to its neighboring vertices. These vertices, in turn, may then have enough sand to fire, etc., creating an avalanche. One often designates a "sink" vertex that only absorbs sand. In this case, if each vertex has a edge-path to the sink, any configuration of sand put on the graph will, after a sequence of firings, eventually stabilize. This stable state is independent of the order of the firings.

For his Google Summer of Code™ project, working in consultation with experts in the field, Bryan Head created a state-of-the art Java program to visualize and analyze the ASM. His program includes: a flexible graph editing environment for the creation of sandpiles on arbitrary weighted digraphs; multiple visualization modes in two- and three-dimensions using OpenGL; and an interface to the free open-source mathematical software, Sage, in particular with David Perkinson's Sage Sandpiles software.

This codebase has attracted significant interest from the sandpiles community. Bryan's visualizations are helping researchers develop better mathematical models.



If you are interested in sandpiles, you can download Bryan's program or learn more about ASM.

.