The Bactra Review: Occasional and eclectic book reviews by Cosma Shalizi   90

# Lattice-Gas Cellular Automata

## byDaniel H. RothmanandStéphane Zaleski

Collection Aléa Saclay, vol. 5
Cambridge University Press, 1997
Hydrodynamics is a peculiarly interesting and frustrating branch of physics, because it ought to have been wrapped up by the middle of the nineteenth century, but looks like it will continue to be intractable well into the twenty-first. That a mathematical understanding of fluid motion would be very useful technologically needs, I trust, no argument. And indeed the fundamental equation of fluid motion was discovered by Navier in 1823, and independently by Stokes a little later. The Navier-Stokes equation is an extremely well-confirmed piece of Newtonian physics, widely applicable and fairly unmysterious. Theoretical hydrodynamics ought to involve no more than solving it from various initial conditions. The problem is that, like many Newtonian differential equations, it can be extremely non-linear, and analytical solutions are available for almost no situations of interest. An immense amount of effort has, therefore, gone into two kinds of cheats: approximations and statistics. The approximations are ways of finding things which are not exact solutions of the equations, but are reasonably close, in some well-defined way. The statistical approach tries to extract information about the properties of ensembles of exact solutions, ignoring the question of which member of the ensemble happens to be realized. Both are sufficiently hard that people work on the statistics of approximations. Lattice gases, the subject of this book, are a means of approximation, with interesting statistical properties.

Generations of physics teachers have derived (or at any rate claimed to derive) the Navier-Stokes equation for their classes from little more than the conservation of mass, momentum and energy, and the requirement that these be conserved ``locally,'' that there is no teleportation. We do this, typically, by considering the travails of a little block or parcel of fluid, and then waving our hands about limits as the volume of the parcel goes to zero. (Navier actually reasoned about such fluid ``elements''; I don't know whether Stokes thought in this way.) Lattice gases, in a sense, take this procedure literally. In these intensely simplified computational models, particles with one of a fixed, small number of velocities sit on a lattice in two or three dimensions. Every time a clock ticks, they move. If two particles happen to land on the same lattice site, they hit each other, and change their velocities according to a ``collision rule.'' That, repeated ad lib., is that. The only real restriction is that collisions have to conserve particle number (no particles appear or disappear), and they must conserve momentum and energy, too.

As someone who has rehearsed the traditional derivation of Navier-Stokes before several year's worth of students, I find it intensely gratifying that such rules do lead to recognizably fluid-like consequences. Not only can we get away with cutting up the fluid into blocks, we can cut up space and time and velocity, too, and it still works. The first lattice gas models, from the end of the 1960s through the middle 1970s, however, evolved out of statistical mechanics, and not a desire to vindicate pedagogical tradition. That field has a long tradition, from 1911, of working with systems of discrete variables on lattices, and has found them very useful indeed. (For historical reasons, it calls all such things lattice gases, which is why our critters are not lattice fluids, and sometimes leads to confusion.) The problem with those first lattice gases was that they weren't much more than fluid-like. Even at very large scales, the dynamics were anisotropic --- different in different directions --- reflecting the fact that the lattice was also anisotropic.

This problem was finally solved in 1985, by Uriel Frish, Brosl Hasslacher, and Yves Pomeau, with the so-called FHP rule. This used a hexagonal lattice and one speed (and so six velocities), and the trick turned on the fact that certain symmetry tensors of hexagonal lattices are isotropic, so that at large scales the fact that the FHP gas lives on a lattice washes out. The same rule was independently discovered by Stephen Wolfram shortly afterwards, who patented not just that rule but lattice gases as a whole. (People have been curiously reluctant to pay him royalties.)

Two fields were very excited by the FHP rule: fluid dynamics and cellular automata. Fluid dynamicists were excited by the possibility of very large, fast and parallel computer simulations: each lattice point needs only a little memory (six bits for the FHP rule, versus about ten times as much for previous methods), and the lattice is updated by shifting around bits and then performing simple Boolean operations at each site. Cellular automata are mathematical objects introduced by John von Neumann in the 1950s; they are also lattice systems, in discrete time, with a finite number of states at each site, where the state at each site at the next time-step is some regular function of the current state and the state of a fixed ``neighborhood'' of other sites. (For physicists, cellular automata are fully-discretized classical field theories.) For several decades cellular automata were little more than mathematical curiosities, but they include lattice gases (in our sense) as a special case. Lattice gases were in fact almost the first known instance of cellular automata which could model interesting physical phenomena, and as such their discovery gave a tremendous boost to the field. Since the mid-1980s, however, the limitations of lattice gases have become clearer, and early hopes that they would let us crack the problem of turbulence, for example, have been dashed. (More about turbulence another time.)

Lattice gas have by no means however proven useless; in fact, they have many applications, especially to situations where we face messy boundary conditions, irregular obstacles in the way of the flow, or more than one type of fluid. This covers a lot; in particular, the petroleum industry is very interested in how to force oil out of rock. But there are many other important applications, too, having to do with pattern formation, and even to straight-forward fluid flow when the Reynolds number (a kind of ratio of inertia to viscosity) is not too large.

Rothman and Zaleski have written the first textbook on lattice gases, covering both principles and applications, with a certain understandable emphasis on applications which they themselves have worked on. (They give thanks to eight oil companies and one petroleum research foundation in their acknowledgments.) The first half of the text (roughly) is given over to building up the basic model, and the second half to elaborations and applications.

The bulk of the foundational first half is about calculating the ``hydrodynamics'' of various lattice gases, their dynamics over lengths large compared to the lattice-spacing and times long compared to the clock-tick. In real fluids, the hydrodynamics are isotropic, there are no special or preferred directions; but the lattice itself marks out special directions, so we need to find lattices where this effect gets washed out over large scales. In two dimensions, as I said, a regular hexagonal lattice will do this. There actually aren't any regular three-dimensional lattices which will do, but one can use a four-dimensional lattice, project it down to three dimensions, and get everything to work. (Two-dimensional drawings of this beast look really weird.) Having established that realistic hydrodynamics happens, the authors introduce the ``lattice Boltzmann method,'' a fuzzed-up version of straight lattice gases. We start with our favorite gas and keep the lattice, the particle types, and the collision rule the same, but instead of tracking individual particles, we work on probability distributions for particles, and ignore certain kinds of correlations between particles. (Statistical mechanics think of this, contrariwise, as taking the fully continuous Boltzmann equation and discretizing it in time and space.) This is in some sense like averaging over many different realizations of the original lattice gas, and so tends to give us smaller variance in the results, and smoother flows.

The applications chapters cover mixtures of fluids (miscible and immiscible), surface tension and other interfacial phenomena, liquid-gas mixtures, phase separation, flow through porous media, the foundations of equilibrium statistical mechanics, and the detailed derivation of the Navier-Stokes equations of hydrodynamics from lattice Boltzmann models. The chapters on immiscible mixtures and on flow through porous media are particularly good, and the latter even includes comparison with experimental data. I am less taken with the chapter on the foundations of statistical mechanics, however, not because I disagree with any of it, but it would be a miracle if this fantastically tricky topic could be dealt with adequately in sixteen pages.

This is very definitely a book aimed at physicists, and not, say, computer scientists (who are also interested in cellular automata). The most important pre-requisites, after introductory mechanics and vector calculus, are familiarity with tensor notation and manipulations (at, say, the level of Schutz), and a first course in statistical mechanics. Readers whose introductory physics courses skipped fluids (a shamefully common practice these days) may want to read the relevant chapters of the Feynman lectures, or Landau and Lifshitz. The book is well-written, with a consistently pedagogical yet friendly tone, in quite fluent English. Lattice-Gas Cellular Automata is not just the first textbook on its subject, but also a very good one, and I expect it to serve as a standard reference and introduction for years; it would even make an excellent book for a one-semester course if it came out in paperback.

Disclaimer: I asked the publisher for a review copy of this book, but didn't get one. I'd like to think this didn't bias me against it, though.
xxii + 297 pp., numerous black and white figures, select bibliography for each chapter, author index, subject index
Cellular Automata / Hydrodynamics
Currently in print as a hardback, ISBN 0-521-55201-X, US\$74.95, LoC QC157 R587
8 July 1999, revised 14 July 1999