Abstract
The Global Random Walk algorithm (GRW) performs the simultaneous tracking on a fixed grid of large collections of particles, while the computational costs remain comparable to those of a single-trajectory simulation by the traditional Particle Tracking (PT) approach.
Unlike the sequential PT procedure, GRW simulates diffusion processes by globally distributing all the particles lying at a lattice site. The global scattering is achieved by allowing the particles to execute unbiased spatial jumps with diffusive scaling, proportional to the square root of the simulation time step. When diffusion takes place in a velocity field, the diffusion step is preceded by a drift step which moves all the particles according to the velocity field at the lattice site. If the GRW procedure is applied to a single particle, it is equivalent to a PT procedure projected on a regular lattice. Thus, GRW can be thought as a superposition of PT procedures. Moreover, it has been shown that the GRW algorithm can also be implemented as a weak Euler scheme for the Ito equation governing the continuous diffusion process, which accurately reproduces the true probability distribution. The essential difference is that while the concentration field is estimated by post-processing the trajectories simulated sequentially in the PT approach, a single GRW simulation is required for concentration estimates. In fact, the output of the GRW simulation is not an ensemble of trajectories solving the Ito equation, rather it is a solution to the associated Fokker-Planck equation. The GRW algorithm saves memory and computing time and no restrictions are imposed to the total number of particles which ensures reliable concentration estimates.
For vanishing or constant drift coefficients, GRW is also equivalent with the stable finite-difference (FD) scheme and has the same convergence order for large enough numbers of particles. However, for space-variable drift this equivalence fails and GRW suffers from overshooting errors caused by particles jumping over lattice points with different velocities. Overshooting errors can be completely removed by allowing jumps only to first-neighbor lattice sites. This can be achieved with a biased-GRW, where the drift displacement is modeled as a bias in the jump probability.
The new algorithm is no longer a weak Euler scheme for the Ito equation, instead it is equivalent to a stable FD scheme without numerical diffusion. Removing the overshooting with biased-GRW has the drawback of high computational costs, due to the fine grids required by the first-neighbor jumps constraint. Therefore, the biased algorithm is mainly useful as reference to assess the accuracy of the coarser, but faster, unbiased GRW algorithms which are more efficient in solving large scale diffusion problems. This chapter includes a presentation of the GRW algorithm, with details on its derivation, implementation, equivalence with other schemes, sensitivity to parameters, and convergence properties.
Since the GRW approach is highly recommended for large scale simulations of advection-dominated transport processes, where PT has limited accuracy and finite element/difference schemes suffer from numerical diffusion, some relevant applications to contaminant transport in groundwater are also presented for the purpose of illustration.
Authors
Keywords
Cite this chapter as:
N. Suciu, C. Vamoş, Global random walk algorithm for diffusion processes, in A. Skogseid and V. Fasano, editors, Random Walks: Principles, Processes and Applications, pp. 341-388, Nova Science Publishers, New York, 2012.
Publisher’s website: https://novapublishers.com/shop/statistical-mechanics-and-random-walks-principles-processes-and-applications/
References
see the expansion block below.
Not available yet.
About this chapter
Book
Statistical Mechanics and Random Walks: Principles, Processes and Applications
Publisher Name
Nova Science Publisher
Print ISBN
9781614709664, 9781614709879
MR
?
ZBL
?
[1] Ames, W. F., Numerical Methods for Partial Differential Equations; Academic Press: New York, 1977.
[2] Attinger, S.; Dentz, M.; Kinzelbach, H.; Kinzelbach, H. J. Fluid Mech. 1999, 386, 77-104.
[3] Colucci, P. J.; Jaberi, F. A.; Givi, P. Phys. Fluids 1998, 10, 499-515.
[4] Chorin, A. J. J. Comput. Phys. 1978, 27, 428-442.
[5] Crank, J. The Mathematics of Diffusion; Oxford Univ. Press: Oxford, 1975.
[6] Dagan, G., Flow and Transport in Porous Formations; Springer: Berlin, 1989.
[7] Delay, F. ; Dzikowski, M.; de Marsily, G. Mathematical Geology 1993, 25, 689-712.
[8] Delay, F.; Housset-Resche, H.; Porei, G.; de Marsily, G. Mathematical Geology 1996, 28, 45-71.
[9] Delay, F.; Ackerer, P.; Danquigny, C. Vadose Zone Journal 2006, 4, 360-379.
[10] Doering, C. R.; Horsthemke, W.; Riordan, J. Phys. Rev. Lett. 1994, 72, 2984-2987.
[11] Eberhard, J.; Suciu, N.; Vamos¸, C. J. Phys. A: Math. Theor. 2007, 40, 597-610, doi: 10.1088/1751-8113/40/4/002.
[12] Fannjiang, A.; Komorowski, T. Ann. Appl. Probab. 1999, 9, 591-610.
[13] Gardiner, C. W., Handbook of Stochastic Methods; Springer: New York, 1983.
[14] Godunov, S. K.; Ryabenkii, V. S., Difference Schemes: An Introduction to the Underlying Theory; North Holland: Amsterdam, 1987.
[15] Ghoniem, A. F.; Sherman, F. S. J. Comput. Phys. 1985, 61, 1-37.
[16] Horsthemke, W.; Lefever, R., Noise-Induced Transitions. Theory and applications in Physics, Chemistry and Biology; Springer: Berlin, 1984.
[17] Karapiperis, T.; Blankleider, B. Physica D 1994, 78, 30-64.
[18] Kinzelbach, W., Numerische Methoden zur Modellierung des Transports von Schadstoffen im Grundwasser; Oldenbourg Verlag: Munchen, 1992.
[19] Kloeden, P. E.; Platen, E., Numerical Solutions of Stochastic Differential Equations; Springer: Berlin, 1999.
[20] Komorowski, T.; Papanicolaou, G. Ann. Appl. Probab. 1997, 7, 229-264.
[21] Moltyaner, G. L.; Klukas, M. H.; Willis, C. A.; Killey, R. W. D. Water Resour. Res. 1993, 29, 3433-3452.
soon