Interesting observation.

But it isn''t really as it seems. The Poisson equation, solved in Stam''s case using Gauss-Siedel relaxation, actually represents the interconnection of every cell at once. Once the GS relaxation converges, you''ve actually solved for an update to every cell in a single step. The result for a single step of the GS solution will not be representative of the final solution for the cell. It has to be run through convergence before any cell will be correct.

The advection part of his approach is much closer to a cellular automation approach. This is solved by what is known as a "marching" approach, which does update each cell independently in a simple loop. Each individual cell step produces its final result for the current frame without having to iterate. Over the course of several frames, the effect on every cell on every other cell will simply emerge correctly. In real life, the effect of advection on neighbor cells actually propogates away from each cell at a physical speed that is related to the speed of sound and the speed of the sound or disturbance source. If the time step is large, the real-world effect at a given cell might step further than just one neighbor cell in each direction. The simulation is stable as long as the simulation does not try to propogate the effect further in distance than the real-world wavefront would move. Stam''s version of the NSE solver guarantees that this is the case. More accurate engineering NSE solvers do not guarantee this, and have to be handled more carefully.

In pure math terms, the Poisson (diffusion) problem is of type "Elliptic" which isn''t like cellular automation. The advection problem (dispersion) is of type "hyperbolic", which is the part that''s more like cellular automation.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

quote:Original post by laeuchli
Ah well, get a new hammer, everything looks like a nail :-). Just curious, you mention different types of problems(Elliptic and hyperbolic). Any place I could learn a bit more about this?

But at least you''re analyzing the situation, trying to put things together. That''s one of the characteristics of a good developer, or scientist, or whatever!

Actually, there is a book called "Computational Fluid Dynamics: The Basics with Applications" by John D. Anderson, Jr. (ISBN0-07-001685-2) that discusses elliptic and hyperbolic (and the third type, parabolic) systems. Its a bit of an advanced book, and might be difficult to follow depending on your schooling level. But the introductory discussions, and indeed much of the introductory material in the book, is quite straightforward. Its a very well written book.

In fact, I''ll just type out part of the section that introduces elliptic equations for you here.

"Assume that the domain of the problem is defined as the rectangle abcd shown in Figure 3.13 and that [point] P is located somewhere inside this closed domain. [GSR - removed some text] Now assume that we jab point P in Figure 3.13 with a needle; i.e., we introduce a disturbance at point P. The major mathematical charactistic of elliptic equations is that this disturbance is felt everywhere throughout the domain. Furthermore, because point P influences all points in the domain, then in turn the solution at point P must be carried out simultaneously throughout the domain. This is in stark contrast to the "marching'' solutions germane to parabolic and hyperbolic equations." - from John D. Anderson, Jr. in his book.

Hyperbolic (and elliptic) problems are a bit stranger, and require pictures/diagrams to understand. Anderson''s book does have pictures.

Unfortunately, I''m not aware of any good web resources on the subject. It seems the CFD (computational fluid dynamics) books are the absolute best resources to under the nature of different types of differential equations.

So, you may have gathered, correctly, that the problem Jos Stam is solving is a mixed Hyperbolic-Elliptic problem, which requires one time-marching loop to solve the hyperbolic part and one iterative, time-stationary solution to solve the elliptic part.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

quote:Original post by uutee
Kind of wierd I think. I don''t think even advection counts as a cellular automaton. IMHO a cellular automaton is a strictly discrete rule between different states. But solving PDEs isn''t discrete, and just discretizing the area in cells doesn''t make it a cellular automaton, right?

- Mikko Kauppila

Yes! You are right! Its just that advection (when solved using explicit integration) seems somewhat like a cellular automaton simply because the state at a point is derived from simple rules based on the state at adjacent points. When you use implicit integration even the marching problem isn''t like a cellular automaton, since (like the elliptic problems) the updated states at all points are dependent.


Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.