Sandpiles and Synthesizers: Listening to the Discrete Laplacian

Year: 2019 Authors: John A. Lind

Core claim

Abelian sandpile dynamics on square lattices can be encoded as MIDI and rendered as music whose structure reflects the discrete Laplacian.

Topics

algorithmic composition, abelian sandpile model, discrete Laplacian, MIDI synthesis, graph dynamics

Domains

graph theory, combinatorics, discrete dynamical systems, numerical analysis, finite element method, music composition, electronic music, sonification

Methods

firing scripts, MIDI encoding, square lattice simulation, parameterized synthesis, algorithmic composition

Media

synthesizer, MIDI data, square grid, online recordings, computer-generated audio

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2019 Conference Proceedings

Sandpiles and Synthesizers: Listening to the Discrete Laplacian

John A. Lind

Mathematics and Statistics Dept., California State University, Chico, U.S.A.; jlind@csuchico.edu

Abstract

There are many visual representations of the dynamical system determined by the action of the discrete Laplace operator of a graph. In this paper, I present an auditory representation which translates information about the evolving system into pitch, volume, and timbre data of notes played on a synthesizer. I have implemented the method on square lattices and recordings of the resulting pieces of music are available online.

Introduction

Algorithmic composition uses deterministic processes to generate music [5,7]. I present here a new algorithmic composition method based on the abelian sandpile model, a discrete dynamical system with interesting combinatorial properties [2]. Inspired by the graphical representations developed by Cameron Fish and David Perkinson [9, 10], I encoded the abelian sandpile model into MIDI data, which then played synthesizers to create pieces of music. Recordings of the music are available online at:

jlind.yourweb.csuchico.edu/sandpile_music/

A discrete version of the Laplace operator regulates the evolution of the abelian sandpile model in the same way that the differential Laplace operator regulates diffusive processes, such as the flow of heat in thermodynamics. In fact, the discrete Laplacian can be used to numerically approximate the continuous version [3]; this is a cornerstone of the finite element method in the numerical analysis of PDEs [6]. Although its role in the mathematics of this paper is not essential, the discrete Laplacian is a central figure in the broader context.

The paper consists of two parts. In the first, I give a streamlined account of the abelian sandpile model, following the book of Corry and Perkinson [2]. In the second, I describe a method of music composition based on the mathematics of the first part. The examples are based on the evolution of the abelian sandpile model on a square grid of moderate size (e.g. $41\times 41$ nodes). In composing the music, some properties are determined by the mathematics, and some are chosen independently according to aesthetic criteria.

The Abelian Sandpile Model and the Discrete Laplace Operator

The abelian sandpile model is a combinatorial dynamical system that models flow of a quantity over a discretized network [4]. The network is represented by a set $V$ of vertices, a set $E$ of edges, and an additional vertex $s$ called the sink. In other words, $(V\cup \{s\},E)$ is a graph, which is required to be finite and contain, for each vertex $v$, a path through edges from $v$ to the sink. Note that loops from a vertex back to itself are allowed, as well as multiple edges between the same pair of vertices. Write $E_{v,w}$ for the set of edges between a pair of vertices $v$ and $w$, and define the degree of a vertex $v$ by $\mathrm{deg}(v)={\sum }_w|E_{v,w}|$. Since the graph is not directed, the ordering of subscripts does not matter: $E_{v,w}=E_{w,v}$.

A configuration $c$ of the system consists of the assignment to every non-sink vertex $v$ of an integer $c_v$, which we think of as determining a pile of $c_v$ grains of sand on $v$. The set of possible configurations is denoted by $\mathbf{Z}V$. As the notation suggests, a configuration may be encoded into an element $c={\sum }_v{c}_{v}v$ of

Lind

the free abelian group on the set $V$. Of course, only configurations with non-negative values are physically meaningful; we write $c\ge 0$ and call the configuration a sandpile when this is the case. At each moment in time, a vertex can “fire” by sending one grain of sand to each of its neighbors. Any sand sent to the sink vertex $s$ is immediately discarded. In the following example, the vertex $v_1$ fires, then the vertex $v_2$:

The effect of firing a vertex $v$ defines a function $f_v:\mathbf{Z}V\to \mathbf{Z}V$ whose value on $c\in \mathbf{Z}V$ is given by

so that as an element of $\mathbf{Z}V$,

The firing functions $f_{\nu }$ commute with each other $f_{\nu }\circ f_w=f_w\circ f_{\nu }$ —hence the term abelian sandpile model—so we need not keep track of the order of firings, only the vertices that have fired. In fact, since vertices can fire multiple times, the data of a sequence of firings can be encoded into a firing script $\sigma :V\to \mathbf{Z}$. The value $\sigma (\nu )$ of a firing script at a vertex $\nu$ is the number of times that $\nu$ fires over the entire process. Firing scripts are elements of the set ${\mathbf{Z}}^V$ of integer-valued functions on $V$. While the finiteness of the graph implies that the group of configurations $\mathbf{Z}V$ is isomorphic to ${\mathbf{Z}}^V$ via the assignment which takes $\nu \in \mathbf{Z}V$ to the characteristic function ${\chi }_{\nu }:V\to \mathbf{Z}$ (whose value ${\chi }_{\nu }(w)$ is 1 or 0 according to whether $\nu =w$ or not), it is important to distinguish configurations from firing scripts. This duality is a combinatorial counterpart of the relationship between the group of divisors on a Riemann surface and its field of meromorphic functions [1,2].

Before turning to the music generated by the abelian sandpile model, I summarize here its relation to the discrete Laplacian. This is not needed in order to understand the algorithm presented in the second part of the paper. The discrete Laplace operator $\Delta :{\mathbf{Z}}^V\to {\mathbf{Z}}^V$ is defined so that the net change $c-f_{\sigma }(c)\in \mathbf{Z}V$ to a configuration $c$ over the composite firing $f_{\sigma }$ determined by $\sigma$ corresponds to $\Delta \sigma \in {\mathbf{Z}}^V$ under the isomorphism $\mathbf{Z}V\cong {\mathbf{Z}}^V$ between configurations and firing scripts. More concretely, $\Delta$ is defined by:

In applications, such as to computer graphics [8], it is important to allow variations on this definition [11], and in algebraic combinatorics, the discrete Laplace operator is arguably a more fundamental object than the abelian sandpile model. In fact, the way in which the discrete Laplacian underlies the abelian sandpile model is analogous to the way in which the differential Laplace operator $\Delta ={\sum }_i\partial /\partial x_i^2$ describes continuous diffusive processes in terms of solutions of the differential equation $d\sigma /dt=-\Delta \sigma$. The analogy stems from the fact that both the discrete and the differential Laplace operator measure how much the value of a function $\sigma$ at a point deviates from its average on a neighborhood of that point. In the discrete case, locality is described by adjacent vertices in the graph, whereas classically the Laplacian compares the value of $\sigma$ at a point and on infinitesimal spheres centered at the point.

454

Sandpiles and Synthesizers: Listening to the Discrete Laplacian

Making Music out of Sandpiles

I now discuss the particular methods that I used to generate music from the mathematical structure of the abelian sandpile model. A sequence ${\sigma }_1,{\sigma }_2,\dots$ of firing scripts determines a discrete dynamical system

that evolves according to the initial configuration $c$. The configurations are now required to be sandpiles: $c\ge 0$. In order to preserve this property throughout different states of the system, a vertex $v$ may only fire if $c_v\ge \mathrm{deg}(v)$. This guarantees that there are a non-negative number of grains of sand left after sending one out along each edge emanating from $v$. At each moment in time $t=0,1,2,\dots$, every vertex will fire that is permitted to do so. Thus the sequence of firing scripts is defined by:

where $c(t)=(f_{{\sigma }_t}\circ \cdots \circ f_{{\sigma }_1})(c)$ is the configuration of the system at time $t$. Note that a vertex might be inactive at one moment of time, then receive enough sand to fire later on. Each firing of a vertex plays a single note. The pitch, volume, and timbre of the note are determined by the geometric location of the vertex within the graph. My examples are all built on a square grid, but the possibilities are vast.

Consider an $N\times N$ unit square grid whose lower-left corner is located at the origin in the cartesian plane. The vertices and edges of the grid form the graph on which the sandpiles evolve. For simplicity, assume that $N=2k+1$ is odd, so that the center of the grid is the point $(k,k)$. Connect each vertex along the outer rows and columns by an edge to the sink vertex $s$, so that sand “falls off” the grid when it reaches the periphery—this condition ensures that the process terminates in a finite amount of time, and thus that a finite piece of music is created. Next, I chose a scale, meaning a finite increasing sequence of integers n_1 < n_2 < \cdots < n_\ell whose values $n_i$ correspond to some subset of notes from a range of octaves of the twelve-tone equal temperament chromatic scale. Of course, other tuning systems or sets of frequencies could be used here, depending on the abilities of the synthesizer. I used the scale indicated in Figure 3, whose notes follow the chords $\text{E}={\text{maj}}^7$, ${\text{Gsus}}^7$, ${\text{Dm}}^7$.

Figure 1: Schematic for determining the note that each vertex plays

Figure 2: Example of an initial sandpile

Figure 3: Example of a scale n_1 < n_2 < \cdots < n_{\ell-1} < n_\ell

Lind

In order to determine which note of the scale a given vertex should play when it fires, I subdivided the grid into a sequence of annuli of increasing radius, creating a bullseye pattern as in Figure 1. The bands of the diagram correspond to the notes of the scale in decreasing order, so that the highest notes are in the center. The length $\ell$ of the scale determines the width $k\sqrt{2}/\ell$ of each band. To create variation in volume and tone, the notes played by a given band become quieter as the corresponding points approach the outer rim of the band, and different synthesizer voices are used for different bands. The most aesthetically pleasing results, to my ear, arise when the initial sandpile has mild asymmetry. For example, with $N=41$ and center vertex (20, 20), the starting configuration defined in Figure 2 creates a pleasant, cascading rhythmic pattern. The starting notes are struck quickly and repetitively, while the low notes at the outer rim of the bullseye only appear late in the sequence, and enter with a bemused snort of impatience. The tension between the deterministic aspects of the process and the arbitrary choices of the composer (the grid, the scale, and the initial sandpile $c$) are reflected in the music’s nature: it is both regular and random, with melodic lines that sound inevitable but are occasionally startling.

Starting the process with a large pile of sand at a single node in the center of the grid creates a longer, but less complex piece of music. The repeated figures evolve, but more simply and more slowly. Another variation is to increase the decay length of the notes generated by the synthesizer, so that each note takes longer to subside. The result is an atmospheric and muddy piece of music. The feeling of evolving, quasiperiodic flow is still present, but echoed and smeared out over time as the notes pile up on each other. Alternatively, if the decay parameter of the notes is controlled by the distance of the activated node from some fixed node within the grid, which need not be the center, the asymmetry of the play of firings across the grid creates waves into and out of echo. Contemporary synthesis technology offers a staggering variety of controllable parameters, so the methods discussed here are only a start to the exploration of the sonic potential of abelian sandpile music.

References

[1] M. Baker and S. Norine. “Riemann-Roch and Abel-Jacobi Theory on a Finite Graph.” Advances in Mathematics 215 (2007), 766–788.

[2] S. Corry and D. Perkinson. Divisors and Sandpiles. American Mathematical Society, 2018.

[3] K. Crane and M. Wardetzky. A Glimpse into Discrete Differential Geometry. Notices of the American Mathematical Society 64 (2017), no. 10, 1153–1159.

[4] D. Dhar. “Self-organized Critical State of Sandpile Automaton Models.” Physical Review Letters 64 (1990), no. 14, 1613–1616.

[5] K. Essl. “Algorithmic Composition.” Cambridge Companion to Electronic Music. ed. Collins and d’Escrivan, Cambridge University Press, 2007, pp. 107–125.

[6] R. J. Leveque. “Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-state and Time-dependent Problems.” Society for Industrial and Applied Mathematics, 2007.

[7] G. Nierhaus. “Algorithmic Composition: Paradigms of Automated Music Generation.” Springer-Verlag, 2009.

[8] M. Reuter, S. Biasotti, D. Giorgi, G. Patane, M. Spagnuolo. “Discrete Laplace-Beltrami Operators for Shape Analysis and Segmentation.” Computers & Graphics 33 (3), 381–390.

[9] C. Fish. “A GPU Approach to the Abelian Sandpile Model.” Reed College B.A. Thesis, 2017.

[10] C. Fish and D. Perkinson. Web GL sandpile simulation, people.reed.edu/~davidp/.

[11] M. Wardetzky, S. Mathur, F. Kälberer, and E. Grinspun. “Discrete Laplace operators: No free lunch.” Eurographics Symposium on Geometry Processing, ed. Belyaev and Garland, 2007.

456