next up previous
Next: 8.3.2 The Lattice Boltzmann Up: 8.3 Lattice Gas Models Previous: 8.3 Lattice Gas Models


8.3.1 Lattice Gas Cellular Automata

The first example of cellular automata was John H. Conway's computer game ``Life'': some initial pixel patterns on a screen are set, and at each iterative step every pixel is set or erased depending on the status of the neighboring pixels [EIGEN 82].

Generally, cellular automata are one- or two-dimensional bit patterns that evolve in (discrete) time according to certain simple rules. They have come to play a role in such diverse fields as informatics [WOLFRAM 86], evolution theory, and the mathematical theory of complexity [WOLFRAM 84].

A model representing a two-dimensional flow field in terms of bit patterns was introduced by Hardy, Pomeau and de Pazzis. Their ``HPP model'' is defined as follows [HARDY 73]:

- Represent the flow region by a point lattice
- Populate each grid point $(i,j)$ with up to four ``particles'' whose velocities must point into different compass directions
- Absolute value of each velocity is always $v=1$

There are $2^{4}=16$ possible ``states'' of a grid point.
Representation: Use a 4-bit (half-byte) computer word $a_{i,j}$ to describe the ``empty'' or ``full'' status of the compass directions E,N,W,S by one bit each (see Fig. 8.3).
Figure 8.3: HPP model
\begin{figure}\includegraphics[width=210pt]{figures/f8za1.ps}\end{figure}
Alternative representation: Combine the bits referring to the same direction at several successive grid points into one computer word.
Example: In a $16 \times 16$ grid each compass direction described by a set of 32 words of 1 byte each (see Fig. 8.4).
Figure 8.4: Storage methods in the HPP model
\begin{figure}\includegraphics[width=180pt]{figures/f8za2.ps}\end{figure}


Evolution law: $t_{n}$ $\Longrightarrow$$t_{n}$ by a deterministic rule comprised of two substeps, Free flight and Scattering.
Free flight: Each particle moves on by one vertex in its direction of flight.
In the representation of Figure 8.4 each ``north'' bit in the second row (in words $n_{2}$ and $n_{3}$), if $=1$ at time $t_{n}$ would be reset to $0$; the respective bit above (in words $n_{0}$ and $n_{1}$) would be set to $1$. Similar translations take place for the ``south'' bits.
The $1$-bits in the ``east'' and ``west'' words are right- and left-shifted, respectively, by one position.

In most programming languages logical operations may be performed not only with single bits but also with byte-words or even integers made up of several bytes. In the above example the new word $n_{0}'$ could be computed as
\begin{displaymath}
n_{0}'=n_{0}\; \vee \; n_{2}
\end{displaymath} (8.81)

with $\vee$ denoting the bitwise or-operation.
Analogous commands apply to the $s\/$-words.
The $e\/$ and $w\/$-words have to be handled, in this representation, in a bit-by-bit manner. By combining the east and west bits column-wise the translation may then be formulated as for north and south.

Free flight and boundaries:
Reflection: Transform all $n$-bits in the top row into $s$-bits before the translation takes place.
Periodic boundary conditions: To describe part of a longer tube etc.

Note: Periodic boundary conditions preserve momentum and energy exactly, while in the presence of reflexion the conservation laws can hold only on the average.
Figure 8.5: Scattering law for the HPP model
\begin{figure}\includegraphics[width=240pt]{figures/f8za3.ps}\end{figure}


Scattering:
- If after the translation step a grid point is inhabited by two particles, change its state according to Fig. 8.5
- Otherwise: the state remains unaltered

Momentum and energy are conserved by this scattering rule. We may write the HPP scattering rule in a concise, computer-adapted way as follows:
\begin{displaymath}
a_{i,j}'=\{e \oplus u, \, n \oplus u, \, w \oplus u, \, s \oplus u \}
\end{displaymath} (8.82)

where $a_{i,j} \equiv \{e,n,w,s \}$ is the state of grid point $(i,j)$ before scattering (but after translation), and
\begin{displaymath}
u \equiv [(e \oplus n) \odot (w \oplus s)] \odot [e \oplus (\neg w)]
\end{displaymath} (8.83)

$\odot$, $\oplus$ and $\neg$ are the logical operators and, exclusive or, and not. ($\oplus$ differs from $\vee$ in that $1 \oplus 1 = 0$.)

Lookup table: A fast way to implement the scattering rules is the use of a table containing all possible pre- an post-scattering states of a site.

Reviews of the performance of this simple model: [FRISCH 86,WOLFRAM 86B].

Application:
- Population number at a grid point = density at that position
- Sum of velocities at $(i,j)$ = local velocity density
- Coarse-graining in space and time $\Longrightarrow$averaged dynamics obeys equations similar to the flow equations
- However: only logical operations $\Longrightarrow$calculations are much faster!

Improvement: the FHP model
Frisch, Hasslacher, and Pomeau [FRISCH 86] suggested to introduce hexagonal cells in place of the simple quadratic lattice:
- Six possible flight directions per grid point
- More scattering rules (see Figure 8.6)

Refinements: Possibility of particles at rest $\Longrightarrow$richer microdynamics.

Advantage over HPP: Rotational symmetry of the flow distribution, in spite of the discretized velocities.

FHP in 3 dimensions: To retain rotational symmetry, a four-dimensional face centered hypercubic (FCHC) lattice is set up and used in the propagation and collision steps. The results are then mapped onto three dimensions following a rule due to [D'HUMI`ERES].
Figure 8.6: Scattering rules in the FHP model
\begin{figure}\includegraphics[width=300pt]{figures/f8fhp2.ps}\end{figure}


Note: In the basic HPP and FHP models the particles lose their identity in the process of scattering (see Figs. 8.5).
To determine single particle properties, like velocity autocorrelations, ``tag'' some particles and pass the tags in the scattering step in a unique way.
Application: Long time behavior of the velocity autocorrelation function [FRENKEL 90,ERNST 91]. Using a two-dimensional FHP simulation with tagging, Frenkel et al. were able to produce proof for the expected $t^{-1}$ long time tail.
next up previous
Next: 8.3.2 The Lattice Boltzmann Up: 8.3 Lattice Gas Models Previous: 8.3 Lattice Gas Models
Franz J. Vesely Oct 2005
See also:
"Computational Physics - An Introduction," Kluwer-Plenum 2001