(00
4. SIMULATING GROWTH AND FORM
4.3.1 Cellular Automata as Models for Fluid Flow
INTRODUCTION. Here we introduce a very specific cellular automata (CA)
which, as will become clear later on, can be used as a model of fluid flow. This
class of CA is called the Lattice Gas Automata (LGA), and they are described
in detail in two recent books (Rothman and Zaleski 1997, Chopard and Droz
1998).
Suppose that the state of a cell is determined by b m surrounding cells.
Usually, only the nearest and next-nearest neighbors are considered. For
example, on a square lattice with only nearest-neighbor interactions b m = 4,
while if next-nearest neighbors are also included b m = 8; and on a hexagonal
lattice with nearest-neighbor interactions b.; = 6. Furthermore, suppose that
the state of the cell is a vector n =(nl>n 2 , • • • , nb) of b =b m bits. Each element
of the state vector is associated with a direction on the CAlattice. For example,
in the case of a square grid with only nearest-neighbor interactions we may
associate the first element of the state vector with the north direction, the
second with east, the third with south, and the fourth with west. With these
definitions we construct the following CA rule (called the LGA rule) , which
consists of two sequential steps:
1.
Each bit in the state vector is moved in its associated direction (thus in
the example, the bit in element 1 is moved to the neighboring cell in the
north) and placed in the state vector of the associated neighboring cell,
in the same position (so, the bit in element 1 is moved to element 1 of the
state vector in the cell in the north direction). In this step each cell is in
fact moving bits from its state vector in all directions, and at the same
time is receiving bits from all directions, which are stored into the state
vector.
2 .
Following some deterministic or stochastic procedure, the bits in the
state vector are reshuffled. For instance, the state vector (1,0,1,0) is
changed to (0,1,0,1).
As a refinement, one may also introduce b, extra bits in the state vector
which, as if they were residing on the cell itself, are not moved to another cell
in step 1 of the LGA rule. In that case the length of the state vector b = b m + b-,
These b, residing bits do however participate in the reshuffling step 2.
It is clear that the class of LGA-CA that we have just defined is very
large. We have the freedom to choose the CA lattice, the interaction list, the
number of residing bits, and the reshuffling rule. Once all this is done, we
may expect that the specific LGA-CA that we defined has a very rich dynamic
behavior, depending on the initial conditions and the size of the grid . Except
maybe for i-dimensional lattices, a detailed study of the dynamics of such
CA is probably not feasible. It was shown by Moore and Nordhal (1997) that
the problem of LGA prediction is P-complete, and thus cannot be solved
in parallel in polylogarithmic time . This implies that the only solution is
a step-by-step explicit simulation. Our new CAtherefore seems like a nice toy
that may exhibit a very complex dynamic behavior, but no more than that.
However, maybe surprisingly, ifwe associate physical quantities with our CA,
enforce physical conservation laws on the bit-reshuffling rule of step 2, and
use methods from theoretical physics to study the dynamics, we are in fact
able to analyze the CA in terms of its average behavior, i.e. the average state
vector of a cell and the average flow of bits between cells can be calculated.
4. SIMULATING GROWTH AND FORM
4.3.1 Cellular Automata as Models for Fluid Flow
INTRODUCTION. Here we introduce a very specific cellular automata (CA)
which, as will become clear later on, can be used as a model of fluid flow. This
class of CA is called the Lattice Gas Automata (LGA), and they are described
in detail in two recent books (Rothman and Zaleski 1997, Chopard and Droz
1998).
Suppose that the state of a cell is determined by b m surrounding cells.
Usually, only the nearest and next-nearest neighbors are considered. For
example, on a square lattice with only nearest-neighbor interactions b m = 4,
while if next-nearest neighbors are also included b m = 8; and on a hexagonal
lattice with nearest-neighbor interactions b.; = 6. Furthermore, suppose that
the state of the cell is a vector n =(nl>n 2 , • • • , nb) of b =b m bits. Each element
of the state vector is associated with a direction on the CAlattice. For example,
in the case of a square grid with only nearest-neighbor interactions we may
associate the first element of the state vector with the north direction, the
second with east, the third with south, and the fourth with west. With these
definitions we construct the following CA rule (called the LGA rule) , which
consists of two sequential steps:
1.
Each bit in the state vector is moved in its associated direction (thus in
the example, the bit in element 1 is moved to the neighboring cell in the
north) and placed in the state vector of the associated neighboring cell,
in the same position (so, the bit in element 1 is moved to element 1 of the
state vector in the cell in the north direction). In this step each cell is in
fact moving bits from its state vector in all directions, and at the same
time is receiving bits from all directions, which are stored into the state
vector.
2 .
Following some deterministic or stochastic procedure, the bits in the
state vector are reshuffled. For instance, the state vector (1,0,1,0) is
changed to (0,1,0,1).
As a refinement, one may also introduce b, extra bits in the state vector
which, as if they were residing on the cell itself, are not moved to another cell
in step 1 of the LGA rule. In that case the length of the state vector b = b m + b-,
These b, residing bits do however participate in the reshuffling step 2.
It is clear that the class of LGA-CA that we have just defined is very
large. We have the freedom to choose the CA lattice, the interaction list, the
number of residing bits, and the reshuffling rule. Once all this is done, we
may expect that the specific LGA-CA that we defined has a very rich dynamic
behavior, depending on the initial conditions and the size of the grid . Except
maybe for i-dimensional lattices, a detailed study of the dynamics of such
CA is probably not feasible. It was shown by Moore and Nordhal (1997) that
the problem of LGA prediction is P-complete, and thus cannot be solved
in parallel in polylogarithmic time . This implies that the only solution is
a step-by-step explicit simulation. Our new CAtherefore seems like a nice toy
that may exhibit a very complex dynamic behavior, but no more than that.
However, maybe surprisingly, ifwe associate physical quantities with our CA,
enforce physical conservation laws on the bit-reshuffling rule of step 2, and
use methods from theoretical physics to study the dynamics, we are in fact
able to analyze the CA in terms of its average behavior, i.e. the average state
vector of a cell and the average flow of bits between cells can be calculated.