Cellular Automata FAQ


[Non-Java version]

Lattice Gas Automata

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand/collapse
Expand this node
What are Lattice Gas Automata?

Contributions by: Paul Larson <palarson@dal.mobil.com> Bruce Boghosian <bruceb@bu.edu>

LGA stands for "lattice gas automaton." It is a particular type of cellular automaton that is used for the simulation of viscous fluid flow.

LGA research is a highly developed subculture of general CA research. Some CA researchers are completely immersed in it, while others have barely heard of it.

Rothman and Zaleski have a nice review article: Rev. Mod. Phys. 66 1417 (1994).

The October, 1995 issue of the Journal of Statistical Physics was devoted to lattice gases. See the papers in that, and the secondary references. Also, do you know how to access the electronic archives at LANL? If so, check out comp-gas@xyz.lanl.gov, or find the comp-gas archive. You can retrieve papers from there, do searches, etc. See also: Bogosian

There will be a meeting on LGA

LGA simulation

Expand this node
Expand/collapse
Expand this node
Waves in CA?

Contributions by: Jeremy Henderson <J.R.Henderson@durham.ac.uk> http://www.dur.ac.uk/~dgl0jrh From: LUTHI Pascal <luthi@cui.unige.ch>

I've successfully implemented a cellular automata model to simulate 2-DIM wave propagation (in a high heterogeneous macroscopic medium like an urban microcell, for instance). The method is an application of the TLM (Transmission Line Matrix) method for the time domain.

What's TLM? Read the folowing paper as an introduction:

Wolfgang J. R. Hoffer, IEEE Transaction on microwave theory and techniques, Vol. MTT-33, No 10, october 1985

Dan Rothman had a paper on modeling the 2-D wave equation with CA, back about 1987 or 1988. His method was pure integer, and the application was intended to be modeling of seismicity (I think).

Rothman's paper is in Geophysics Research Letters 14(1) 17-20 1987.

see also:

Rucker.waves R. Rucker's project on modelling the wave equation.

sportwaves Waves at sporting events.

Expand this node
Expand/collapse
Expand this node
How can I simulate wind in a CA?
Contributions by: Bruce Boghosian <bruceb@conx.bu.edu> tolman@asylum.cs.utah.edu (Kenneth Tolman); Rudy Rucker <rucker@jupiter.SJSU.EDU>

For a lattice gas treatment of incompressible, convective flow in the Boussinesq approximation, see C. Burges and S. Zaleski, "Buoyant mixtures of cellular automaton gases," Complex Systems 1 (1987) 31.

Rucker: A simple way to make wind is to just have each cell copy the cell to its right with each update. This makes a wind that blows to the left. In the RC module of the CA LAB package, I ran this rule alternating with the heat equation (rug rule). I also allowed there to be some stable blocks of cells in the pattern which were *not* shifted to the left with each update - these were copied in as masks with each update. The effect was of turbulence in the wind behind the blocks, vortices, slipstreams, the whole shmear. Try it you'll like it.

Expand this node
Expand/collapse
Expand this node
What are the commonly used rules of interaction between the cells in a lattice gas?
<bruceb@conx.bu.edu> Bruce Boghosian <mikk0022@maroon.tc.umn.edu> Christoph L Mikkelson <david@alpha1.csd.uwm.edu> Dave Stack Mohamed <osman@eecs.wsu.edu>

There's a huge literature on this. Briefly, examples include two- and three-dimensional Navier-Stokes flow, magnetohydrodynamics, immiscible fluids with a surface tension interface, convection, two-phase liquid-gas flow, Burgers' equation, and reaction-diffusion equations. For a summary of recent works on the subject, see any of the reviews listed below; also there should be a very recent (or imminent) Physics Reports devoted to lattice gases by Rothman and Zaleski.

References

``Lattice Gas Methods for Partial Differential Equations,'' Proceedings of the Workshop on Large Nonlinear Systems, held in Los Alamos, New Mexico, August, 1987, Proceedings Volume IV of the Santa Fe Institute Studies in the Sciences of Complexity, Addison-Wesley (1990), Doolen, G.D., ed.

``Lattice Gas Methods for PDE's, Theory, Applications and Hardware,'' Proceedings of the NATO Advanced Research Workshop, held at Los Alamos National Laboratory, September 6-8, 1989, North-Holland (1991), Doolen, G.D., ed.

Proceedings of the Workshop on ``Discrete Kinetic Theory, Lattice Gas Dynamics and Foundations of Hydrodynamics,'' held in Torino, Italy, September 20-24, 1988, World Scientific (1989), Monaco, R., ed.

``Cellular Automata and Modeling of Complex Physical Systems,'' Proceedings of the Winter School, Les Houches, France, February 21-28, 1989, Springer (1989), Manneville, P., Boccara, N., Vichniac, G., Bidaux, R., eds.

Proceedings of the Colloquium Euromech No. 267 on ``Discrete Models of Fluid Dynamics,'' held in Figueira da Foz, Portugal, September 19-22, 1990, World Scientific (1991), Alves, A.S. ed.

Proceedings of the NATO Advanced Research Workshop on Lattice Gas Automata: Theory, Implementation and Simulation, held at l'Observatoire de la Côte d'Azur, Nice, France, June 25-28, 1991, to appear in J. Stat. Phys., Boon, J.-P., Lebowitz, J.L., eds.

One of the seminal papers is "Lattice Gas Hydrodynamics in Two and Three Dimensions" by Frisch et. al. in Complex Systems Volumne 1 (1987) 649-707.

There is an excellent 3 part review paper by Brosl Hasslacher in a special issue of Los Almos Science in 1987. The title is "discrete fluids" and the the title of part I is "background for lattice gas automata". Also see Computer in physics, Nov. 1991, page 585 for an article by B.M. Boghosian.

Expand this node
Expand/collapse
Expand this node
Viscosity in LGA?
Contributions by:

<bruceb@conx.bu.edu> (Bruce Boghosian) <S_DOLLINGE@main01.rz.uni-ulm.de> (Dollinger Juergen)

Relationship between the shear viscosity and the collision probabilities.

Stephen Wolfram, ``Cellular Automaton Fluids 1: Basic Theory'', Journal of Statistical Physics 45 Nos.~3/4 (1986) 471-526. (equation 4.6.8 )

U.~Frisch, D.~d'Humières, B.~Hasslacher, Y.~Pomeau, J.~Rivet, ``Lattice Gas Hydrodynamics in Two and Three Dimensions'', Complex Systems 1 (1987) 649-707. (equation 8.25)

From general kinetic theoretical arguments, the viscosity of a fluid goes as the product of the thermal velocity and the mean free path. Now the thermal velocity of the particles of a lattice gas automaton is fixed at one lattice spacing per time step. It follows that the viscosity goes as the mean free path. Thus, decreasing the collision probability clearly increases the mean free path, and hence the viscosity.

References: [Boo92] [ea90] [Doo91] [Mon89] [MBVB89] [Alv91]

Expand this node
Expand/collapse
Expand this node
Does the lack of symmetry in the HPP model have any obvious bad effect, other than to remove the inertial term?

Contributions by: Bruce Boghosian <bruceb@bu.edu>

I don't think it removes the inertial term. There is still a form of the inertial term with HPP, though it is not isotropic. And, yes, it does have another effect on the equation: The viscous term, like the inertial term, is present but anisotropic.

Expand this node
Expand/collapse
Expand this node
Are there unphysical conservation laws with HPP?

Contributions by: Bruce Boghosian <bruceb@bu.edu>

Yes, HPP has several unphysical conservation laws. First, if you color the sites white and black, like a checkerboard, you can convince yourself that the dynamics on the white squares are completely independent of the dynamics on the black squares. Thus, all conserved quantities (mass and momentum) are conserved *separately* on the two checkerboard sublattices. More seriously, y-momentum is conserved separately within each column, and x-momentum is conserved separately within each row (assuming periodic b.c.'s).

Expand this node
Expand/collapse
Expand this node
What are the physical manifestations of anisotropy?
Contributions by: Bruce Boghosian <bruceb@bu.edu>

Here is a physical manifestation of the problem of anisotropy: If you tried to do a Poiseuille flow simulation with HPP, you would find that the drag on the plates depended on the angle of orientation of the plates with respect to the underlying lattice. This problem would be present even at low Reynolds number. With FHP, on the other hand, the drag would be independent of this orientation.

Expand this node
Expand/collapse
Expand this node
References
Alv91
A. S. Alves. Discrete Models of Fluid Dynamics. World Scientific, 1991.

Boo92
Jean Pierre Boon. Lattice gas automata: Theory, simulation, implementation. Journal of Statistical Physics, 68(3/4), 1992.

Doo91
G. D. Doolen. Lattice Gas Methods for PDE's, Theory, Applications and Hardware. North-Holland, 1991.

ea90
G. D. Doolen et al. Lattice gas methods for partial differential equations. Addison-Wesley, New York, 1990.

MBVB89
P. Manneville, N. Boccara, G. Vichniac, and R. Bidaux. Cellular automata and the modeling of complex physical systems. Springer, Berlin, 1989.

Mon89
R. Monaco. Discrete Kinetic Theory, Lattice Gas Dynamics and Foundations of Hydrodynamics. World Scientific, 1989.

L. Wagner, "Dependence of drag on a Galilean invariance-breaking parameter in lattice-Boltzmann flow simulations," Physical Review E 49 2115 (1994)

Rothman and Zaleski have a nice review article: Rev. Mod. Phys. 66 1417 (1994).

Bruce B. paper in Phys. Rev. E 52 (1995) 510-554 (or comp-gas/9403003) for many

L. Wagner, "Dependence of drag on a Galilean invariance-breaking parameter in lattice-Boltzmann flow simulations," Physical Review E 49 2115 (1994)

d'Humieres & Lallemand, Complex Systems 1 (1987) 633-647.

1 Wolfram, S., J. Stat. Phys., 45 (1986) 471.

2 Frisch, U., Hasslacher, B., Pomeau, Y., Phys. Rev. Lett. 56 (1986).

3 Frisch, U., d'Humières, D., Hasslacher, B., Lallemand, P., Pomeau, Y., Rivet, J.-P., Complex Systems 1 (1987) 75-136.