# Cellular Automata/Excitable media

## An introduction to excitable media

Excitable media are nonlinear dynamic systems known for exhibiting complex behavior that can be observed as pattern formation. They are usually defined by a reaction-diffusion differential equation.

$u_t(\mathbf{r},t) = D \nabla^2 u(\mathbf{r},t) + f(u(\mathbf{r},t))$

The diffusion part provides stability and propagation of information, the reactive part provides interesting local dynamics.

A common example of excitable media are prey-predator systems. Such systems are described by a system of differential equations, one function for each of the observed protagonists.

$u_t(\mathbf{r},t) = D_u \nabla^2 u(\mathbf{r},t) + f(u,v)$
$v_t(\mathbf{r},t) = D_v \nabla^2 v(\mathbf{r},t) + g(u,v)$

We will discuss two different approaches to modeling excitable media. Discretization of differential equations and modeling with cellular automata.

### Boundary conditions

There are different ways to define boundary conditions for the reaction-diffusion equation.

Dirichlet boundary conditions

The value of the function at the boundary is given explicitly $u(\mathbf{r_0},t)$.

Cyclic boundaries

If the initial condition $u(x,0)$ is supposed to be periodic in space, cyclic boundary conditions can be used.

Zero-flux boundary conditions

If zero-flux is expected at the boundary than the component of the functions first derivative normal to the boundary is zero $\vec{n}\cdot \nabla{u}=0$ at the boundary. This can be achieved by reflecting function values from the inside over the boundary to the outside.

## Discretization of differential equations using the explicit FTCS method

The traditional method to simulate excitable media is discretization and numerical computation of the governing PDE. First the FTCS (forward-time centered-space method) discretization method is presented. Explicit methods are the simplest and the equations are similar to a cellular automaton, but are inadequate because of stability and convergence problems.

### Single PDE

We will first observe a single PDE describing a single function.

$u_t(\mathbf{r},t) = D \nabla^2 u(\mathbf{r},t) + f(u(\mathbf{r},t))$

#### One-dimensional problem

In the one dimensional case the space vector becomes a single variable $\mathbf{r}=x$. The nabla operator becomes $\nabla^2=\frac{\partial^2}{\partial{x^2}}$.

$\frac{ \partial u(x,t) }{ \partial t } = D \frac{ \partial^2 u(x,t) }{ \partial x^2 } + f(u(x,t))$

The partial differential equation is discretized.

$\frac{ u(x,t+\Delta{t}) - u(x,t) }{ \Delta{t} } =$
$\quad D \frac{ u(x+\Delta{x},t)-2u(x,t)+u(x-\Delta{x},t) }{ \Delta{x}^2 }$
$\quad + f(u(x,t))$
Forward-time centered-space method

Each finite element at time $t+\Delta{t}$ is calculated from three neighboring elements at time $t$ (see figure at the right).

$u(x,t+\Delta{t}) = u(x,t) + \,$
$\quad + d( u(x+\Delta x,t)-2u(x,t)+u(x-\Delta x,t) )$
$\quad + \Delta{t} f(u(x,t))$

where the diffusion number is

$d = D \frac{ \Delta{t} }{ \Delta{x}^2 }$
Stability

The FTCS method is stable if

$d \leq 1/2$
Boundary conditions

For periodic boundaries present values at the left boundary $x=0$ can be used to compute the future values at the right boundary $x=L_x$ and the other way round.

$u(0,t+\Delta{t}) = u(0,t) + d( u(0+\Delta x,t)-2u(0,t)+u(L_x,t) ) + \Delta{t} f(u(0,t)) \,$
$u(L_x,t+\Delta{t}) = u(L_x,t) + d( u(0,t)-2u(L_x,t)+u(L_x-\Delta x,t) ) + \Delta{t} f(u(L_x,t)) \,$

If there is zero-flux $\nabla u(0,t)=0$ at the boundaries than values outside the boundary are reflections of values inside $u(0+\Delta x,t)=u(0-\Delta x,t)$.

$u(0,t+\Delta{t}) = u(0,t) + 2d( u(0+\Delta x,t)-u(0,t) ) + \Delta{t} f(u(0,t)) \,$
$u(L_x,t+\Delta{t}) = u(L_x,t) + 2d( u(L_x,t)+u(L_x-\Delta x,t) ) + \Delta{t} f(u(L_x,t)) \,$

#### Two-dimensional problem

In the two-dimensional case, the space vector becomes a variable pair $\mathbf{r}=[x,y]$. The nabla operator becomes $\nabla^2=\frac{\partial^2}{\partial{x^2}}+\frac{\partial^2}{\partial{y^2}}$.

$\frac{ \partial u(x,y,t) }{ \partial t } = D \left( \frac{ \partial^2 u(x,y,t) }{ \partial x^2 } + \frac{ \partial^2 u(x,y,t) }{ \partial y^2 } \right) + f(u(x,y,t))$

The partial differential equation is discretized using the forward-time centered-space method.

$\frac{ u(x,y,t+\Delta{t}) - u(x,y,t) }{ \Delta{t} } =$
$\quad = D \frac{ u(x+\Delta{x},y,t)-2u(x,y,t)+u(x-\Delta{x},y,t) }{ \Delta{x}^2 } +$
$\quad + D \frac{ u(x,y+\Delta{y},t)-2u(x,y,t)+u(x,y-\Delta{y},t) }{ \Delta{y}^2 } +$
$\quad + f(u(x,y,t))$
Forward-time centered-space method

Each finite element at time $t+\Delta{t}$ is calculated from five neighboring elements at time $t$ (see figure at the right).

$u(x,y,t+\Delta{t}) = u(x,t) + \,$
$\quad + d_x( u(x+\Delta{x},y,t)-2u(x,y,t)+u(x-\Delta{x},y,t) ) +$
$\quad + d_y( u(x,y+\Delta{y},t)-2u(x,y,t)+u(x,y-\Delta{y},t) ) +$
$\quad + \Delta{t} f(u(x,y,t))$

where the diffusion numbers are

$d_x=D\frac{\Delta{t}}{\Delta{x}^2} \quad d_y=D\frac{\Delta{t}}{\Delta{y}^2}$
Stability

The FTCS method is stable if

$d_x \leq 1/2$ and $d_y \leq 1/2$
Boundary conditions

The same ideas as in the one dimensional case can be used for two dimensions.

### System of PDE

A system of PDE describes two functions that interact with each other (prey-predator).

$u_t(\mathbf{r},t) = D_u \nabla^2 u(\mathbf{r},t) + f(u,v)$
$v_t(\mathbf{r},t) = D_v \nabla^2 v(\mathbf{r},t) + g(u,v)$

The interaction is local, which means, the dispersion part can be computed separately for each equation, and than the reaction part is added to the result.

## References

1. Joe D. Hoffman, Numerical Methods for Engineers and Scientists
2. Toffoli T., Margolus N., Cellular Automata Machines: A New Environment for Modeling, The MIT Press (1987), Cambridge, Massachusetts
3. Toffoli T., Cellular automata as an alternative to Differential equations, in Modeling Physics, Physica 10D, (1984)
4. http://www.jweimar.de/paper-abstracts.html
5. Robert Fisch, Janko Gravner, David Griffeath, Threshold-Range Scaling of Excitable Cellular Automata
6. Robert Fisch, Janko Gravner, David Griffeath, Metastability in the Greenberg-Hastings Model
7. Marcus R. Garvie Finite difference schemes for reaction-diffusion equations modeling predator-prey interactions in MATLAB