Fig. 8. Theoretical shear (solid line) and bulk (dashed line) reduced viscosities as a function of reduced density compared with the results of hexagonal lattice gas simulation with rest particles and all possible collisions (d'Humiéres and Lallemand 1987). functional forms for various fluid dynamical laws. The question of quantitative accuracy of various known constants is harder to answer, and we will take it up in detail later. The next broad class of flows studied are flows past objects. Here, we look for distinctive qualitative behavior characteristic of a fluid or gas obeying Navier-Stokes dynamics. The geometries studied, through a wide range of Reynolds numbers, were flows past flat plates placed normal to the flow, flows past plates inclined at various angles to the flow, and flows past cylinders, 60-degree wedges, and typical airfoils. The expected scenario changes as a function of increasing Reynolds number: recirculating flow behind obstacles should develop into vortices, growing couples of vortices should eventually break off to form von Karman streets with periodic oscillation of the von Karman tails; finally, and as the Reynolds number increases, the periodic oscillations should become aperiodic, and the complex phenomena characteristic of turbulent flow should appear. The lattice gas exhibits all these phenomena with no non-Navier-Stokes anomalies in the range of lattice-gas parameters that characterize near incompressibility. The next topic is quantitative self-consistency. We used the Boltzmann transport approximation for the discrete model to calculate viscosities for the simple hexagonal automaton as well as models with additional scattering rules and rest particles. We then checked these analytic predictions against the viscosities deduced from two kinds of 200 simulations. We ran plane-parallel Poiseuille flow in a channel, saw that it developed the expected parabolic velocity profile (Fig. 7) and then deduced the viscosity characteristic of this type of flow. We also ran an initially flat velocity distribution and deduced a viscosity from the observed velocity decay. These two simulations agree with each other to within a few percent and agree with the analytic predictions from the Boltzmann transport calculation to within 10 percent. Viscosity was also measured by observing the decay of sound waves of various frequencies (Fig. 8). The level of agreement between simulation and the computed Boltzmann viscosity is generic: we see a systematic error of approximately 10 percent. Monte Carlo calculations of viscosities computed from microscopic correlation functions improve agreement with simulations to at least 3 percent and indicate that the Boltzmann description is not as accurate an analytic tool for the automaton as are microscopic correlation techniques. One would call this type of viscosity disagreement a Boltzmann-induced error. Other consistency checks between the automaton simulation and analytic predictions display the same level of agreement. Detailed quantitative comparisons between conventional discretizations of the Navier-Stokes equations and lattice-gas simulations have yet to be done for several reasons. The simple lattice-gas automaton has a Fermi-Dirac distribution rather than the standard Maxwell-Boltzmann distribution. This difference alone causes deviations of O(v2) in the macrovelocity from standard results. For the same reason and unlike standard numerical spectral codes for fluid dynamics, the simple lattice-gas automaton has a velocity-dependent equation of state. A meaningful comparison between the two approaches requires adjusting the usual spectral codes to compute with a velocitydependent equation of state. This rather considerable task has yet to be done. So far our simulations can be compared only to traditional two-dimensional computer simulations and analytic results derived from simple equations of state. Some simple quantities such as the speed of sound and velocity profiles have been measured in the automaton model. The speed of sound agrees with predicted values and functional forms for channel velocity profiles and D'Arcy's law agree with calculations by standard methods. The automaton reaches local equilibrium in a few time steps and reaches global equilibrium at the maximum information-transmission speed, namely, at the speed of sound. Simulations with the two-dimensional lattice-gas model hang together rather well as a simulator of Navier-Stokes dynamics. The method is accurate enough to test theoretical turbulent mechanisms at high Reynolds number and as a simulation tool for complex geometries, provided that velocity-dependent effects due to the Fermi nature of the automaton are correctly included. Automaton models can be designed to fit specific phenomena, and work along these lines is in progress. Three-dimensional hydrodynamics is being simulated, both on serial and parallel machines, and early results show that we can easily simulate flows with Reynolds numbers of a few thousand. How accurately this model reproduces known instabilities and flows remains to be seen, but there is every reason to believe agreement will be good since the ingredients to evolve to Navier-Stokes dynamics are all present. We end Part II of this article with a graphical display of two- and three-dimensional simulations in "Calculations Using Lattice-Gas Techniques." My Los Alamos collaborators and I have accompanied this display with a summary of the known advantages and present limitations of lattice gas methods. (Part III begins on page 211.) ver the last few years the tantalizing prospect of being able to perform hydrodynamic calculations orders-of-magnitude faster than present methods allow has prompted considerable interest in lattice gas techniques. A few dozen published papers have presented both advantages and disadvantages, and several groups have studied the possibilities of building computers specially designed for lattice gas calculations. Yet the hydrodynamics community remains generally skeptical toward this new approach. The question is often asked, "What calculations can be done with lattice gas techniques?" Enthusiasts respond that in principle the techniques are applicable to any calculation, adding cautiously that increased accuracy requires increased computational effort. Indeed, by adding more particle directions, more particles per site, more particle speeds, and more variety in the interparticle scattering rules, lattice gas methods can be tailored to achieve better and better accuracy. So the real problem is one of tradeoff: How much accuracy is gained by making lattice gas methods more complex, and what is the computational price of those complications? That problem has not yet been well studied. This paper and most of the research to date focus on the simplest lattice gas models in the hope that knowledge of them will give some insight into the essential issues. We begin by examining a few of the features of the simple models. We then display results of some calculations. Finally, we conclude with a discussion of limitations of the simple models. Features of Simple Lattice Gas Methods We will discuss in some depth the memory efficiency and the parallelism of lattice gas methods, but first we will touch on their simplicity, stability, and ability to model complicated boundaries. Computer codes for lattice gas methods are enormously simpler than those for other methods. Usually the essential parts of the code are contained in only a few dozen lines of FORTRAN. And those few lines of code are much less complicated than the several hundred lines of code normally required for two- and three-dimensional hydrodynamic calcula tions. There are many hydrodynamic problems that cause most standard codes (such as finite-difference codes, spectral codes, and particle-in-cell codes) to crash. That is, the code simply stops running because the algorithm becomes unstable. Stability is not a problem with the codes for lattice gas methods. In addition, such methods conserve energy and momentum exactly, with no roundoff errors. Boundary conditions are quite easy to implement for lattice gas methods, and they do not require much computer time. One simply chooses the cells to which boundary conditions apply and updates those cells in a slightly different way. One of three boundary conditions is commonly chosen: bounce-back, in which the directions of the reflected particles are simply reversed; specular, in which mirror-like reflection is simulated; or diffusive, in which the directions of the reflected particles are chosen randomly. We consider next the memory efficiency of the lattice gas method. When the two-dimensional hydrodynamic lattice gas algorithm is programmed on a computer with a word length of, say, 64 bits (such as the Cray X-MP), two impressive efficiencies occur. The first arises because every single bit of memory is used equally effectively. Coined "bit democracy" by von Neumann, such efficient use of memory should be contrasted with that attainable in standard calculations, where each number requires a whole 64-bit word. The lattice gas is "bit democratic" because all that one needs to know is whether or not a particle with a given velocity direction exists in a given cell. Since the number of possible velocity directions is six and no two particles in the same cell can have the same direction, only six bits of information are needed to completely specify the state of a cell. Each of those six bits corresponds to one of the six directions and is set to 1 if the cell contains a particle with that direction and to 0 otherwise. Suppose we designate the six directions by A,B,C,D, E,F as shown on the next page. We associate each bit in the 64-bit word A with a different cell, say the first 64 cells in the first row. If the first cell contains (does not contain) a particle with direction A, we set the first bit in A to 1 (0). Similarly, we pack information about particles in the remaining 63 cells with direction A into the remaining 63 bits of A. The same scheme is used for the other five directions. Consequently, all the information for the first 64 cells in the first row is contained in the six words A, B, C, D, E, and F. Note that all bits are equally important and all are fully utilized. To appreciate the significance of such efficient use of memory, consider how many cells can be specified in the solidstate storage device presently used with the Cray X-MP/416 at Los Alamos. That device stores 512,000,000 64-bit words. Since the necessary information for 10 cells can be stored in each word, the device can store information for about 5,000,000,000 cells, which corresponds to a two-dimensional lattice with 100,000 cells along one axis and 50,000 cells along the other. That number of cells is a few orders of magnitude greater than the number normally treated when other methods are used. (Although such high resolution may appear to be a significant advantage of the lattice gas method, some averaging over cells is required to obtain smooth results for physical quantities such as velocity and density.) The second efficiency is related to the fact that lattice gas operations are bit oriented rather than floating-point-number oriented and therefore execute more naturally on a computer. Most computers can carry out logic operations bit by bit. For example, the result of the logic operation AND on the 64-bit words A and B is a new 64-bit word in which the ith bit has a value of 1 only if the ith bits of both A and B have values of 1. Hence in one clock cycle a logic operation can be performed on information for 64 cells. Since a Cray X-MP/416 includes eight logical function units, information for 8 times 64, or 512, cells can be processed during each clock cycle, which lasts about 10 nanoseconds. Thus information for 51,200,000,000 cells can be processed each second. The two-dimensional lattice gas models used so far require from about thirty to one hundred logic operations to implement the scattering rules and about another dozen to move the particles to the next cells. So the number of cells that can be updated each second by logic operations is near 500,000,000. Cells can also be updated by table-lookup methods. The authors have a table-lookup code for three-dimensional hydrodynamics that processes about 30,000,000 cells per second. A final feature of the lattice gas method is that the algorithm is inherently parallel. The rules for scattering particles within a cell depend only on the combination of particle directions in that cell. The scattering can be done by table lookup, in which one creates and uses a table of scattering results—one for each possible cell configuration. Or it can be done by logic operations. Using Lattice Gas Methods In August 1985 Frisch, Hasslacher, and Pomeau demonstrated that one can approximate solutions to the Navier-Stokes equations by using lattice gas methods, but their demonstration applied only to low-velocity incompressible flows near equilibrium. No one knew whether more interesting flows could be approximated. Consequently, computer codes were written to determine the region of validity of the lattice gas method. Results of some of the first simulations done at Los Alamos and of some later simulations are shown in Figs. 1 through 6. (Most of the early calculations were done on a Celerity computer, and the displays were done on a Sun workstation.) All the results indicate qualitatively correct fluid behavior. Figure la demonstrates that a stable trailing vortex pattern develops in a twodimensional lattice gas flowing past a plate. Figure 1b shows that without a three-particle scattering rule, which removes the spurious conservation of momentum along each line of particles, no vortex develops. (Scattering rules are described in Part II of the main text.) Figure 2 shows that stable vortices develop in a lattice gas at the interface between fluids moving in opposite directions. The Kelvin-Helmholtz instability is known to initiate such vortices. The fact that lattice gas methods could simulate vortex evolution was reassuring and caused several scientists to begin to study the new method. Figure 3 shows the complicated wake that develops behind a V-shaped wedge in a uniform-velocity flow. Figure 4 shows the periodic oscillation of a low-velocity wake behind a cylin der. With a Reynolds number of 76, the flow has a stable period of oscillation that slowly grows to its asymptotic limit. Figure 5 shows a flow with a higher Reynolds number past an ellipse. The wake here becomes chaotic and quite sensitive to details of the flow. Figure 6 shows views of a threedimensional flow around a square plate, which was one of the first results from Los Alamos in three-dimensional lattice gas hydrodynamic simulations. Rivet and Frisch and other French scientists have developed a similar code that measures the kinematic shear viscosity numerically; the results compare well with theoretical predictions (see Fig. 8 in the main text). The lattice gas calculations of a group at the University of Chicago (Kadanoff, McNamara, and Zanetti) for two-dimensional flow through a channel (Fig. 7 of the main text) agree with the known parabolic velocity profile for low-velocity channel flows. The above calculations, and many others, have established some confidence that qualitative features of hydrodynamic flows are simulated by lattice-gas methods. Problems encountered in detailed comparisons with other types of calculations are discussed in the next section. Limitations of Simple As we discussed earlier, lattice gas methods can be made more accurate by making them more complicated-by, for example, adding more velocity directions and magnitudes. But the added complications degrade the efficiency. We mention in this section some of the difficulties (associated with limited range of speed, velocity dependence of the equation of state, and noisy results) encountered in the simplest lattice-gas models. The limited range of flow velocities is inherent in a model that assumes a continued on page 210 |