Cellular Automata/Partial Differential Equations

From Wikibooks, open books for an open world
Jump to: navigation, search

We traditionally describe phenomena in differential equations, but we would like to simulate and eventually predict their behaviour using numerical methods. This can be done using a traditional top-down approach or a less common bottom up approach.

An inverted method would be to construct from bottom up a cellular automaton, with the same properties as the observed phenomenon differential equation.

The top down approach[edit]

The transformation of a differential equation into a discrete system that can be simulated on a computer is called the top-down approach. Let us try a simple example. One dimensional diffusion equation

 \frac{\partial C}{\partial t} = \kappa \frac{\partial^2 C}{\partial x^2}

is discretized forward in time and symmetric in space

 c_x^t = c_x^{t-1} + \frac{\Delta t \kappa}{(\Delta x)^2} \left( c_{x+1}^{t-1} - 2c_{x}^{t-1} + c_{x-1}^{t-1} \right)

The produced discrete equation can be seen as a cellular automaton local transition function

 c_x^t = f \left( c_{x+1}^{t-1} c_{x}^{t-1} c_{x-1}^{t-1} \right)

The time and space discretization is the same for both systems but there is a crucial difference in the discretization of variables. On a common computer a variable is represented using 64-bit floating point numbers whereas a cellular automaton has variables of 2 to 8 bits.

As numerical approximation errors is an important problem using floating point numbers and would be unbearable using only a few bits. We see that there is no direct method to for transforming differential equations into cellular automata, a different approach must be used.

The bottom up approach[edit]

This approach begins with selecting a discrete system that inherently possesses some basic properties needed for a simplified model of the original problem. An example of such basic properties is reversibility and preservation of quantities as mass, momentum and energy. The model is than modified and trimmed till it is sufficiently close to the original problem.

The basic model is usually as simple as possible If cellular automata are used for the basic model their neighborhood


  1. Joe D. Hoffman, Numerical Methods for Engineers and Scientists