×

Convolution-generated motion as a link between cellular automata and continuum pattern dynamics. (English) Zbl 0938.68058

Summary: Cellular automata have been used to model the formation and dynamics of patterns in a variety of chemical, biological, and ecological systems. However, for patterns in which sharp interfaces form and propagate, automata simulations can exhibit undesirable properties, including spurious anisotropy and poor representation of interface curvature effects. These simulations are also prohibitively slow when high accuracy is required, even in two dimensions. Also, the highly discrete nature of automata models makes theoretical analysis difficult. In this paper, we present a method for generating interface motions that is similar to the threshold dynamics type cellular automata, but based on continuous convolutions rather than discrete sums. These convolution-generated motions naturally achieve the fine-grid limit of the corresponding automata, and they are also well suited to numerical and theoretical analysis. Because of this, the desired pattern dynamics can be computed accurately and efficiently using adaptive resolution and fast Fourier transform techniques, and for a large class of convolutions the limiting interface motion laws can be derived analytically. Thus convolution-generated motion provides a numerically and analytically tractable link between cellular automata models and the smooth features of pattern dynamics. This is useful both as a means of describing the continuum limits of automata and as an independent foundation for expressing models for pattern dynamics. In this latter role, it also has a number of benefits over the traditional reaction-diffusion/Ginzburg-Landau continuum PDE models of pattern formation, which yield true moving interfaces only as singular limits. We illustrate the power of this approach with convolution-generated motion models for pattern dynamics in developmental biology and excitable media. \(\copyright\) Academic Press.

MSC:

68Q80 Cellular automata (computational aspects)
Full Text: DOI

References:

[1] Barkley, D., A model for fast computer simulation of waves in excitable media, Physica D, 49, 75 (1991)
[2] Barles, G.; Georgelin, C., A simple proof of convergence for an approximation scheme for computing motions by mean curvature, SIAM J. Numer. Anal., 32, 484 (1995) · Zbl 0831.65138
[3] Beylkin, G., On the fast Fourier transform of functions with singularities, Appl. Comput. Harmonic Anal., 2, 363 (1995) · Zbl 0838.65142
[4] Bronsard, L.; Stoth, B., Volume Preserving Mean Curvature Flow as a Limit of a Nonlocal Ginzburg-Landau Equation (1994)
[5] Ermentrout, G. B.; Edelstein-Keshet, L., Cellular automata approaches to biological modeling, J. Theor. Biol., 160, 97 (1993)
[6] Evans, L. C., Convergence of an algorithm for mean curvature motion, Indiana Univ. Math. J., 42, 553 (1993) · Zbl 0802.65098
[7] Fast, V. G.; Efimov, I. G., Stability of vortex rotation in an excitable cellular medium, Physica D, 49, 75 (1991)
[8] Gerhardt, M.; Schuster, H.; Tyson, J. J., A cellular automata model of excitable media. II. Curvature, dispersion, rotating waves and meandering waves, Physica D, 46, 392 (1990) · Zbl 0800.92028
[9] Gerhardt, M.; Schuster, H.; Tyson, J. J., A cellular automata model of excitable media. III. Fitting the Belousov-Zhabotinsky reaction, Physica D, 46, 416 (1990) · Zbl 0800.92029
[10] Gerhardt, M.; Schuster, H.; Tyson, J. J., A cellular automata model of excitable media including curvature and dispersion, Science, 247, 416 (1990) · Zbl 0800.92029
[11] Gravner, J.; Griffeath, D., Threshold growth dynamics, Trans. Am. Math. Soc., 340, 837 (1993) · Zbl 0791.58053
[12] Gutowitz, H., Cellular Automata: Theory and Experiment (1991)
[13] Henze, C.; Tyson, J., Cellular automaton model of three-dimensional excitable media, J. Chem. Soc., Faraday Trans., 92, 2883 (1996)
[14] Ishii, H., A generalization of the Bence, Merriman and Osher algorithm for motion by mean curvature, Curvature Flows and Related Topics, 111-127 (1995) · Zbl 0844.35043
[15] Ishii, H.; Pires, G. E.; Souganidis, P. E., Threshold dynamics type schemes for propagating fronts, TMU Math. Preprint Ser., 4 (1996)
[16] Markus, M.; Hess, B., Isotropic cellular automaton for modeling excitable media, Nature, 347, 56 (1990)
[17] Mascarenhas, P., Diffusion Generated Motion by Mean Curvature (1992)
[18] B. Merriman, J. Bence, S. Osher, Diffusion generated motion by mean curvature, Computational Crystal Growers Workshop, J. E. Taylor, American Mathematical Society, Providence, RI, 1992, 73, 83, April 1992; B. Merriman, J. Bence, S. Osher, Diffusion generated motion by mean curvature, Computational Crystal Growers Workshop, J. E. Taylor, American Mathematical Society, Providence, RI, 1992, 73, 83, April 1992
[19] Merriman, B.; Bence, J.; Osher, S., Motion of multiple junctions: A level set approach, J. Comput. Phys., 112, 334 (1994) · Zbl 0805.65090
[20] Rubinstein, J.; Sternberg, P., Nonlocal reaction-diffusion equations and nucleation, IMA J. Appl. Math., 48, 248 (1992) · Zbl 0763.35051
[21] Ruuth, S. J., Efficient Algorithms for Diffusion-Generated Motion by Mean Curvature (1996)
[22] Ruuth, S. J., A diffusion-generated approach to multiphase motion, J. Comput. Phys., 145, 166 (1998) · Zbl 0929.76101
[23] Ruuth, S. J., Efficient algorithms for diffusion-generated motion by mean curvature, J. Comput. Phys., 144, 603 (1998) · Zbl 0946.65093
[24] Ruuth, S. J.; Merriman, B., Convolution Generated Motion and Generalized Huygens’ Principles for Interface Motion (1998) · Zbl 0958.65021
[25] Schönfisch, B., Anisotropy in cellular automata, Biosystems, 41, 29 (1997)
[26] Swindale, N. V., A model for the formation of ocular dominance stripes, Proc. R. Soc. London B, 208, 243 (1980)
[27] Toffoli, T.; Margolus, N., Cellular Automata Machines (1987) · Zbl 0655.68055
[28] Tuckwell, H., Introduction to Theoretical Neurobiology, Volume 2, Nonlinear and Stochastic Theories (1988) · Zbl 0647.92009
[29] Tyson, J. J.; Keener, J. P., Singular perturbation theory of traveling waves in excitable media, Physica D, 32, 327 (1988) · Zbl 0656.76018
[30] Weimar, J. R.; Tyson, J. J.; Watson, L. T., Diffusion and wave propagation in cellular automata models of excitable media, Physica D, 55, 309 (1992) · Zbl 0744.92002
[31] Weimar, J. R.; Tyson, J. J.; Watson, L. T., Third generation cellular automata for modeling excitable media, Physica D, 55, 328 (1992) · Zbl 0744.92003
[32] Wiener, N.; Rosenblueth, A., The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle, Arch. Inst. Cardiol. Mexico, 16, 205 (1946) · Zbl 0134.37904
[33] Winfree, A. T., When Time Breaks Down (1987)
[34] Winfree, A. T., Stable particle-like solutions to the nonlinear wave equations of three-dimensional excitable media, SIAM Rev., 32, 1 (1990) · Zbl 0711.35067
[35] Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1 (1984) · Zbl 0562.68040
[36] Wolfram, S., Cellular Automata and Complexity: Collected Papers (1994) · Zbl 0823.68003
[37] Young, D. A., A local activator-inhibitor model of vertebrate skin patterns, Math. Biosci., 72, 51 (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.