8
$\begingroup$

Is there a theory for solving PDE by using Cellular Automata ? Something which is on the line of, passing to the limit (scale) i.e., if you increase the number of grid points the solution to the cellular automata will converge to the PDE ? If so, how successful is this approach ? What are the limitations of this approach. Also, given a PDE how does one go about finding the rules for the corresponding cellular automata and vice versa ?

$\endgroup$

2 Answers 2

5
$\begingroup$

There are a number of PDEs that have been fruitfully attacked using cellular automata. First among these are various incarnations of the Navier-Stokes equations, which can be (and in geophysical or other complex flow applications, frequently are) simulated with lattice gases and lattice Boltzmann methods. Other PDEs that CAs can handle include diffusion and reaction-diffusion equations and wave equations. Another one that is more widely known is the random walk treated as a random CA, which can be used to tackle the heat equation.

Will Jagy's guess about hexagons anticipates (if we think about triangles instead) the improvement that so-called FHP models offer over HPP models; in higher dimensions the lattice issues get trickier. I have some unpublished and cryptic notes about a possible new approach in 3D using the root lattice $A_4$ and permutohedral boundary conditions.

One of the main advantages of the CA approach is the ability to work with complicated boundary shapes, though on the other hand the boundary conditions are a very delicate issue in general.

A very nice (though somewhat dated) reference for this and related problems is Chopard and Droz (a PDF of the opening parts is here) and IIRC you can find a paper by one of the authors online that covers some of the same topics with a similar approach.

$\endgroup$
2
  • $\begingroup$ Hi Steve. I am looking into using a CA based approach to solving PDEs on evolving (closed) curves. Could you recommend any specific "keywords" I should use in order to mine the literature for information on this topic? Any reviews I could approach first perhaps, in order to be led onto other sources? Thanks for your help! $\endgroup$
    – bzm3r
    May 6, 2014 at 0:43
  • 1
    $\begingroup$ @user89 - the only words I can think of that might be relevant are "Eulerian" and "Lagrangian", a la fluids. Generally the lattice Boltzmann geometries I've seen are time-invariant, though porous media are modeled and those are of course quite complex. $\endgroup$ May 6, 2014 at 3:14
3
$\begingroup$

The only one I know may not count as an automaton. For a two dimensional Dirichlet problem for the Laplacian, take a square grid. Fix the values of the function on the squares judged to be boundary squares. Fill in some values in all the middle squares. At each stage, the value at a square becomes the average of the values at the four immediately neighboring squares, up, down, left, right. This is a discrete analog of the mean value property of harmonic functions. I don't know how well this method is regarded. I also suspect one would get a better mean value property with a grid of hexagons. However, in larger dimension we are probably stuck with cubes.

$\endgroup$
4
  • $\begingroup$ Actually, what I am looking for is discrete models of a problem which converges in the limit to the continuous problem. $\endgroup$
    – Vagabond
    Feb 5, 2012 at 21:59
  • $\begingroup$ So, if the grid size goes to zero does the solution ``converges'' to the actual solution ? $\endgroup$
    – Vagabond
    Feb 5, 2012 at 22:02
  • $\begingroup$ @Vagabond, yes, I believe so. The mean value property is in many texts, and Theorem 2.1 on page 14 of Gilbarg and Trudinger, Elliptic Partial Differential Equations of Second Order. $\endgroup$
    – Will Jagy
    Feb 5, 2012 at 22:14
  • $\begingroup$ There are quite a few works in theoretical computer science (google for Belkin, Hein, von Luxburg, to begin with) that state results like: Take a manifold and some (randomly chosen) sample points on them. Define in this way a discrete(=graph) Laplacian. Then the discrete Laplacian will converge towards the Laplace-Beltrami operator on the original manifold as the sample points exhaust the manifold. $\endgroup$ May 15, 2014 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.