Heat Diffusion Modelling and Random Walks on Lattices and Riemannian Manifolds

Lukas Frannek

March 31, 2014
Diffusion processes are widely used in various scientific fields. Heat diffusion in particular is described by the heat equation  [1, 2]. Due to the complexity of differential equations in engineering applications, it may not be easy to find analytical solutions for the heat equation. Therefore numerical methods are mostly used, for which many deterministic schemes are available  [3, 4, 5, 6, 7, 8].

The diffusion of heat can also be imagined as the random motion of particles, agitated by heat  [9, 10], and random walks and Brownian motion are closely related to the heat equation,  [11, 12, 13, 14]. In addition, due to the fact that parabolic differential equations can be solved by using stochastic processes  [15] and together with the idea of diffusion approximation through Markov processes  [16, 17, 18] and the ideas in  [19, 20], we can modell heat diffusion as particles which are driven by a stochastic process, specifically an continuous-time infinite-state Markov chain. Each particle randomly jumps between nodes of a lattice we impose on a given object. Thinking of three dimensional objects, it is more natural to use a lattice of unequally spaced nodes on an arbitrary object, due to curvature. When simulating heat particles, we may also want to place more nodes in a specific region, which also leads to irregularity. Hence, our framework focusses on such irregular lattices.

The rate at which a heat particle jumps to neighboring nodes, the transition rate, is determined by the distances to all neighboring nodes and the distances between neighboring nodes themselves. Reference  [21] used this idea to approximate general jump-diffusion processes. These transition rates allow us to completely characterize the infinitesimal generator Q of the Markov chain. Q acts as an operator which drives the diffusion of particles.

In continuous space, where no lattice is used, path integrals describe the idea of jumping from one point to another with a specific probability, based on all possible paths between those points  [22, 23]. To find the right transition rates, such that our framework approximates the heat diffusion, we evaluate the variance and mean of the distribution of heat particles. The desired distribution in one dimension is a Gaussian distribution with variance 2 = t and mean = 0. Such a distribution satisfies the heat equation when the diffusivity constant is set to 1 2. Reference  [24] shows that for specific transition rates, our framework delivers a very good approximation of the heat diffusion on a line with unequally spaced nodes. Reference  [25] extends the framework to two-dimensional space and a certain class of triangular lattices. This framework was also extended to allow for lattice structures with less restrictions regarding the position and number of neighboring nodes. Specifically, we categorize the nodes of given lattice into smallest units and show the usage of our framework on different classes of lattices. The approximation of the diffusion of heat on lattices with even less restrictions and irregular structure, similar to those created by triangulations  [26, 27], is very desireable. In addition, the approximation of the diffusion of heat on the circle  [28] is investigated. In the case of the unit circle the desired distribution is the wrapped Gaussian distribution  [29, 30] with the mean resultant R = e22-, see  [31, 32, 33, 34], as the requirement for the distribution of particles on a circle. The mean resultant is the addition of all particle positions on the unit circle, where each particle position is repsresented as a vector from the center of the unit circle to the corresponding position on the circumference of the unit circle. We can obtain the wrapped Gaussian distribution by wrapping the Gaussian distribution on the infinite line around the unit circle. The resulant R can be therefore determined by using the variance 2 of the Gaussian distribtion on the infinite line. It turns out that we can nd transition rates as a function of the geodesic distances between nodes along the circle such that the mean resultant is guaranteed to be e2t. Since we use the Laplace-Beltrami operator  [35] in the heat equation on the circle  [36], the previously mentioned infinitesimal generator Q fulfils the same role as the Laplace-Beltrami operator. Note that with appropiate scaling, we can approximate the diusion of heat on any closed line, not only the unit cirlce. We use the rst moment of the random variable on the closed line instead of the mean resultant.

The next step is the approximation of the heat distribution on a sphere S2in R3  [37]. On the sphere there is no notion of wrapped Gaussian distributions  [32]. Instead we treat the sphere locally as a plane  [38]. By using the transition rates in  [25] we can conduct simulations on the plane and recover distributions of particles on the sphere. We can compare the recovered distribution with the Brownian distribution on the sphere  [39, 40], by numerically calculating the mean and the variance for times t. Alternatively the von Mises-fisher distribution can be used for comparison, since the von Mises-fisher distribution very closely approximates the Brownian distribution  [40, 41]. The mean and variance of the recovered distributions and the mean and variance of the Brownian distribution are very close as the number of nodes on the sphere increase. In the case of an icosahedron with only 12 nodes, the approximation is less accurate, suggesting a different projection of a point on the sphere onto the tangent plane of that node  [42].

A given grid can also be viewed as an undirected graph. The matrix representation of that graph is called graph Laplacian. The infinitesimal generator of the Markov chain has the same form as the graph Laplacian which is also called discrete Laplace-Beltrami operator  [43, 44, 45, 46, 47]. In our framework we model the infinitesimal generator in such a way that the mean and variance of the simulated distribution is very close to the mean and variance of the Gaussian distribution on a given manifold. This can be interpreted as choosing the weights of the graph Laplacian, i.e. discrete Laplace-Beltrami operator  [48], or infinitesimal generator of the Markov chain, as a function of the metric dened on an manifold such that the continuous Laplace-Beltrami operator is approximated  [49].

References

[1]   W. Stoecker, Design of Thermal Systems. McGraw-Hill, NY, 1989.

[2]   J. H. Lienhard, A Heat Transfer Textbook. Phlogiston Press, 2008.

[3]   E. Oran and J. Boris, Numerical Simulation of Reactive Flow. Elsevier, Amsterdam, 1987.

[4]   S. Chapra and R. Canale, Numerical Methods for Engineers. McGraw-Hill, NY, 1998.

[5]   V. Horak and P. Gruber, "Parallel numerical solution of 2-D heat equation," Parallel Numerics, pp. 47-56, 2005.

[6]   J. Reddy and D. Gartling, The Finite Element Method in Heat Transfer and Fluid Dynamics. CRC Press, Boca Raton, 2010.

[7]   D. Wolf-Gladrow, "A lattice Boltzman equation for diffusion," Journal of Statistical Physics, vol. 79, pp. 1023-1032, 1995.

[8]   H. Huang, X. Lu, and M. Sukop, "Numerical study of lattice boltzmann methods for a convection-diffusion equation coupled with Navier-Stokes equations," Journal of Physics A: Mathematical and Theoretical, vol. 44, no. 5, p. 055001, 2011.

[9]   J. Crank, The Mathematics of Di

[10]   C. P. Brangwynne, G. H. Koenderink, F. MacKintosh, and D. Weitz, "Intracellular transport by active di class="cmti-10">Trends Cell Biol, vol. 19, pp. 423-427, 2009.

[11]   G. Lawler, Random Walk and the Heat Equation. American Mathematical Society, 2010.

[12]   C. W. Gardiner, Handbook of Stochastic Methods. Springer-Verlag, Berlin, 2004.

[13]   E. A. Codling, M. J. Plank, and S. Benhamou, "Random walk models in biology," J. R. Soc. Interface, vol. 5, pp. 813-834, 2008.

[14]   P. Moerters and P. Yuval, Brownian Motion. Cambridge University Press, 2010.

[15]   M. Kac, "Random walk and the theory of Brownian motion," The American Mathematical Monthly, vol. 54, pp. 369-391, 1947.

[16]   N. van Kampen, "Markov processes and their diffusion approximations," in Reprinted from: Thermodynamics & kinetics of biological processes, pp. 181-195, Walter de Gruyter & Co., New York, 1982.

[17]   Z. Schuss, "Markov processes and their diffusion approximations," in Theory and Applications of Stochastic Processes, vol. 170 of Applied Mathematical Sciences, pp. 207-256, Springer New York, 2010.

[18]   H. Koeppl, D. Densmore, G. Setti, and M. di Bernado, Engineering Approaches to Systems and Synthetic Biology. Springer, 2011.

[19]   W. Gong, "Are stochastic dynamics the foundation of intelligence?," in Proc. IEEE Conf. Dec. Contr. and Eur. Contr. Conf., (Orlando, FL), 2011.

[20]   M. Bossy and N. Champagnat, "Markov processes and parabolic partial differential equations," in Encyclopedia of Quantitative Finance, pp. 1142-1159, John Wiley & Sons Ltd. Chichester, UK, 2010.

[21]   M. Cerrato, C. Lo, and K. Skindilias, "Adaptive continuous time Markov chain approximation model to general jump-diffusion," in working paper, 2011.

[22]   J. Zinn-Justin, "Path integral," Scholarpedia, vol. 4, no. 2, p. 8674, 2009.

[23]   C. Yeang and M. Szummer, "Markov random walk representation with continuous distributions," in Proc. Uncertainty in Arti pp. 600-607, 2003.

[24]   L. Frannek, T. Hayakawa, and A. Cetinkaya, "One-dimensional heat di class="cmti-10">Proc. IEEE Conf. Dec. Contr., (Maui, HI), pp. 5548-5553, 2012.

[25]   L. Frannek, T. Hayakawa, and A. Cetinkaya, "Heat diffusion modelling with random walks on triangular lattices," in Proc. Amer. Contr. Conf., (Washington, D.C.), pp. 1118-1123, 2013.

[26]   M. Bern and D. Eppstein, "Mesh generation and optimal triangulation," Computing in Euclidean Geometry, vol. 1, pp. 23-90, 1992.

[27]   J. Sewchuk, "Delaunay refinement algorithms for triangular mesh generation," Computational Geometry: Theory and Applications, vol. 22, pp. 21-74, 2002.

[28]   G. S. Chirikijan, Stochastic models, Information Theory, and Lie Groups, Volume 1. Springer, 2009.

[29]   T. P. Fletcher, S. C. Joshi, C. Lu, and S. M. Pizer, "Gaussian Distributions on Lie Groups and Their Application to Statistical Shape Analysis," in IPMI, pp. 450-462, 2003.

[30]   G. Borradaile, Statistics of Earth Science Data. Springer, 2003.

[31]   P. Berens, "Circstat: A matlab toolbox for circular statistics," Journal of Statistical Software, vol. 31, no. 10, pp. 1-21, 2009.

[32]   K. V. Mardia and P. E. Jupp, Directional Statistics. John Wiley & Sons, 2000.

[33]   P. Castro-Villarreal, "Brownian motion meets riemann curvature," J. Stat. Mech. P08006, 2010.

[34]   N. I. Fisher, Statistical Analysis of Circular Data. Cambridge University Press, 1993.

[35]    E. Gine and V. Koltchinskii, "Empirical graph Laplacian approximation of Laplace-Beltrami operators: Large sample results," High Dimensional Probability. Institute of Mathematical Statistics Lecture NotesMonograph Series, vol. 51, pp. 238-259, 2006.

[36]   R. Castaneda-Priego, P. Castro-Villarreal, S. Estrada-Jimenez, and J. M. Mendez-Alcaraz, "Brownian motion of free particles on curved surfaces," eprint: arXiv/1211.5799, 2012.

[37]   J. Jost, Riemannian Geometry and Geometric Analysis. Springer-Verlag, 2002.

[38]   R. Renka, "Interpolation of data on the surface of a sphere," ACM Transactions on Mathematical Software, vol. 10, pp. 417-436, 1984.

[39]   D. Nikolayev and T. I. Savyolova, "Normal distribution on the rotation group SO(3)," Textures & Microstructures, vol. 29, pp. 201-233, 1997.

[40]   P. H. Roberts and H. D. Ursell, "Random walk on a sphere and on a Riemannian manifold," Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, vol. 252, pp. 317-356, 1960.

[41]   G. S. Watson, "Distributions on the circle and sphere," Journal of Applied Probability, vol. 19, pp. 265-280, 1982.

[42]   J. Lee, Introduction to Smooth Manifolds. New York: Springer Verlag, 2003.

[43]   K. Sinha and M. Belkin, "Towards a theoretical foundation for Laplacian-based manifold methods," J. Comput. Syst. Sci., vol. 74, pp. 1289-1308, 2008.

[44]   M. Belkin, Problems of Learning on Manifolds. PhD thesis, The University of Chicago, 2003.

[45]   D. Ting, L. Huang, and M. Jordan, "An analysis of the convergence of the graph Laplacians," Arxiv preprint math.ML/1101.5435v1, 2011.

[46]   J. W. Robbin and D. A. Salamon, Introduction to Differential Geometry, ETH. Lecture Notes, 2011.

[47]   S. Waner, Introduction to Differential Geometry & General Relativity. Department of Mathematics, Hofstra University, 2005.

[48]   A. I. Bobenko and B. A. Springborn, "A discrete Laplace-Beltrami operator for simplicial surfaces," Discrete Comput. Geom., vol. 38, pp. 740-756, 2007.

[49]   W. Zeng, R. Guo, and X. Gu, "Discrete heat kernel determines discrete Riemannian metric," Graphical Models, vol. 74, pp. 121-129, 2012.