Lattice gas automata or lattice gas cellular automata (LGCA) methods are a series of cellular automata methods used to simulate fluid flows. It was the precursor to the lattice Boltzmann methods. From the LGCA, it is possible to derive the macroscopic Navier-Stokes equations. Interest in the LGCA methods levelled off in the early 1990s, as the interest in the lattice Boltzmann started to rise.

Basic principles

As a cellular automaton, these models comprise of a lattice, where the sites on the lattice can take a certain number of different states. In lattice gas, the various states are particles with certain velocities. Evolution of the simulation is done in discrete time steps. After each time step, the state at a given site can be determined by the state of the site itself and neighboring sites, before the time step.

The state at each site is purely boolean. At a given site, there either is or is not a particle that is moving up.

At each time step, two processes are carried out, propagation and collision.

In the propagation step, each particle will move to a neighboring site determined by the velocity that particle had. Barring any collisions, a particle with an upwards velocity will after the time step maintain that velocity, but be moved to the neighboring site above the original site. The so-called exclusion principle prevents two or more particles from travelling on the same link in the same direction.

In the collision step, collision rules are used to determine what happens if multiple particles reach the same site. These collision rules are required to maintain mass conservation, and conserve the total momentum; the block cellular automaton

Block cellular automaton

A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell...

 model can be used to achieve these conservation laws. Note that the exclusion principle does not prevent two particles from travelling on the same link in opposite directions, when this happens, the two particles pass each other without colliding.

Early attempts with a square lattice

In papers published in 1973 and 1976, Hardy, Pomeau and de Pazzis introduced the first Lattice Boltzmann model, which is called the HPP model after the authors. In this model, the lattice is square, and particles can move to any of the four sites whose cells share a common edge. Particles cannot move diagonally.

If two particles collide head-on, for example a particle moving to the left meets a particle moving to the right, the outcome will be two particles leaving the site at right angles to the direction they came in.

The HPP model lacked rotational invariance

Rotational invariance

In mathematics, a function defined on an inner product space is said to have rotational invariance if its value does not change when arbitrary rotations are applied to its argument...

, which made the model highly anisotropic

Anisotropy

Anisotropy is the property of being directionally dependent, as opposed to isotropy, which implies identical properties in all directions. It can be defined as a difference, when measured along different axes, in a material's physical or mechanical properties An example of anisotropy is the light...

. This means for example, that the vortices produced by the HPP model are square-shaped.

Hexagonal grids

The hexagonal grid model was first introduced in 1986, in a paper by Uriel Frisch, Brosl Hasslacher

Brosl Hasslacher

Brosl Hasslacher was a theoretical physicist.Brosl Hasslacher obtained a bachelor's in physics from Harvard University in 1962. He did his Ph.D. with D.Z. Freeman and C.N. Yang at the State University of New York at Stony Brook...

 and Yves Pomeau, and this has become known as the FHP model after its inventors. The model has six or seven velocities, depending on which variation is used. In any case, six of the velocities represent movement to each of the neighboring sites. In some models (called FHP-II and FHP-III), a seventh velocity representing particles "at rest" is introduced. The "at rest" particles do not propagate to neighboring sites, but they are capable of colliding with other particles. The FHP-III model allows all possible collisions that conserve density and momentum. Increasing the number of collisions raises the Reynolds number, so the FHP-II and FHP-III models can simulate less viscous flows than the six-speed FHP-I model.

The collision rules in the FHP model are not deterministic, some input situations produce two possible outcomes, and when this happens, one of them is picked at random. Since random number generation

Random number generation

A random number generator ) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random....

 is computationally time consuming, a pseudorandom

Pseudorandomness

A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process...

 process is usually chosen.

The hexagonal grid does not suffer as large anisotropy troubles as those that plague the HPP square grid model, a fortunate fact that is not entirely obvious, and that prompted Frisch to remark that "the symmetry gods are benevolent".

Three dimensions

For a three-dimensional grid, the only regular polytope

Polytope

In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...

 that fills the whole space is the cube

Cube

In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and...

, while the only regular polytopes with a sufficiently large symmetry group are the dodecahedron and icosahedron

Icosahedron

In geometry, an icosahedron is a regular polyhedron with 20 identical equilateral triangular faces, 30 edges and 12 vertices. It is one of the five Platonic solids....

 (without the second constraint the model will suffer the same drawbacks as the HPP model). To make a model that tackles three dimensions therefore requires an increase in the number of dimensions, such as in the 1986 model by D'Humières, Lallemand and Frisch, which employed a face-centered hypercube

Hypercube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...

 model.

Obtaining macroscopic quantities

The density at a site can be found by counting the number of particles at each site. If the particles are multiplied with the unit velocity before being summed, one can obtain the momentum

Momentum

In classical mechanics, linear momentum or translational momentum is the product of the mass and velocity of an object...

 at the site.

However, calculating density, momentum, and velocity for individual sites is subject to a large amount of noise, and in practice, one would average over a larger region to obtain more reasonable results. Ensemble averaging

Ensemble average

In statistical mechanics, the ensemble average is defined as the mean of a quantity that is a function of the micro-state of a system , according to the distribution of the system on its micro-states in this ensemble....

 is often used to reduce the statistical noise further.

Advantages and disadvantages

The main assets held by the lattice gas model are that the boolean states mean there will be exact computing without any round-off error due to floating-point precision, and that the cellular automata system makes it possible to run LGCA simulations with parallel computing

Parallel computing

Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...

.

Disadvantages of the lattice gas include the lack of Galilean invariance

Galilean invariance

Galilean invariance or Galilean relativity is a principle of relativity which states that the fundamental laws of physics are the same in all inertial frames...

, and statistical noise

Statistical noise

Statistical noise is the colloquialism for recognized amounts of unexplained variation in a sample. See errors and residuals in statistics....

. Another problem is the difficulty in expanding the model to handle three dimensional problems, requiring the use of more dimensions to maintain a sufficiently symmetric grid to tackle such issues.

External links

Master thesis (2000) – Details on programming and optimising the simulation of the FHP LGA Master thesis (2010) - Implementation of FHP model in Nvidia CUDA technology.