High order semi-lagrangian particle methods for transport equations: numerical analysis and implementation issues
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 4, p. 1029-1060

This paper is devoted to the definition, analysis and implementation of semi-Lagrangian methods as they result from particle methods combined with remeshing. We give a complete consistency analysis of these methods, based on the regularity and momentum properties of the remeshing kernels, and a stability analysis of a large class of second and fourth order methods. This analysis is supplemented by numerical illustrations. We also describe a general approach to implement these methods in the context of hybrid computing and investigate their performance on GPU processors as a function of their order of accuracy.

DOI : https://doi.org/10.1051/m2an/2014009
Classification:  65M12,  65M75,  65Y05,  65Y20
Keywords: advection equations, particle methods, semi-lagrangian methods, GPU computing
@article{M2AN_2014__48_4_1029_0,
     author = {Cottet, G.-H. and Etancelin, J.-M. and Perignon, F. and Picard, C.},
     title = {High order semi-lagrangian particle methods for transport equations: numerical analysis and implementation issues},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     year = {2014},
     pages = {1029-1060},
     doi = {10.1051/m2an/2014009},
     mrnumber = {3264345},
     language = {en},
     url = {http://www.numdam.org/item/M2AN_2014__48_4_1029_0}
}
Cottet, G.-H.; Etancelin, J.-M.; Perignon, F.; Picard, C. High order semi-lagrangian particle methods for transport equations: numerical analysis and implementation issues. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 4, pp. 1029-1060. doi : 10.1051/m2an/2014009. http://www.numdam.org/item/M2AN_2014__48_4_1029_0/

[1] M. Bergdorf, G.-H. Cottet and P. Koumoutsakos, Multilevel adaptive particle methods for convection-diffusion equations. SIAM Multiscale Model. Simul. 4 (2005) 328-357. | MR 2164720 | Zbl 1088.76055

[2] M. Bergdorf and P. Koumoutsakos, A lagrangian particle-wavelet method. SIAM Multiscale Model. Simul. 5 (2006) 980-995. | MR 2272307 | Zbl 1122.65085

[3] F. Büyükkeçeci, O. Awile and I. Sbalzarini, A portable opencl implementation of generic particle-mesh and mesh-particle interpolation in 2d and 3d. Parallel Comput. 39 (2013) 94-111.

[4] A. Chorin, Numerical study of slightly viscous flow. J. Fluid Mech. 57 (1973) 785-796. | MR 395483

[5] C. Cocle, G. Winckelmans and G. Daeninck, Combining the vortex-in-cell and parallel fast multipole methods for efficient domain decomposition simulations. J. Comput. Phys. 227 (2008) 9091-9120. | MR 2463200 | Zbl pre05355893

[6] C. Cotter, J. Frank and S. Reich, The remapped particle-mesh semi-lagrangian advection scheme. Q. J. Meteorol. Soc. 133 (2007) 251-260.

[7] G.-H. Cottet and P. Koumoutsakos, Vortex methods. Cambridge University Press (2000). | MR 1755095 | Zbl 0953.76001

[8] G.-H. Cottet and L. Weynans, Particle methods revisited: a class of high order finite-difference methods. C.R. Math. 343 (2006) 51-56. | MR 2241959 | Zbl 1096.65084

[9] N. Crouseilles, T. Respaud and E. Sonnendrücker, A forward semi-lagrangian method for the numerical solution of the vlasov equation. Comput. Phys. Commun. 180 (2009) 1730-1745. | MR 2678446 | Zbl 1197.82012

[10] R. Hockney and J. Eastwood, Simulation Using Particles. Inst. Phys. Publ. (1988).

[11] A. Klöckner, N. Pinto, Y. Lee, B. Catanzaro, P. Ivanov and A. Fasih, PyCUDA and PyOpenCL: A Scripting-Based Approach to GPU Run-Time Code Generation. Parallel Comput. 38 (2012) 157-174.

[12] P. Koumoutsakos, Inviscid axisymmetrization of an elliptical vortex. J. Comput. Phys. 138 (1997) 821-857. | MR 1607496 | Zbl 0902.76080

[13] P. Koumoutsakos and A. Leonard, High resolution simulation of the flow around an impulsively started cylinder using vortex methods. J. Fluid Mech. 296 (1995) 1-38. | Zbl 0849.76061

[14] S. Labbé, J. Laminie and V. Louvet, Méthodologie et environnement de développement orientés objets: de l'analyse mathématique à la programmation. MATAPLI 70 (2003) 79-92.

[15] J.-B. Lagaert, G Balarac, and G.-H. Cottet, Hybrid spectral particle method for turbulent transport of passive scalar. J. Comput. Phys. 260 (2014) 127-142. | MR 3151833

[16] A. Leonard. Computing three-dimensional incompressible flows with vortex elements. Annu. Rev. Fluid Mech. 17 (1985) 523-559. | Zbl 0596.76026

[17] R.J. Leveque, High-resolution conservative algorithms for advection in incompressible flow. SIAM J. Numer. Anal. 33 (1996) 627-665. | MR 1388492 | Zbl 0852.76057

[18] A. Magni and G.-H. Cottet, Accurate, non-oscillatory, remeshing schemes for particle methods. J. Comput. Phys. 231 (2012) 152-172. | MR 2846992 | Zbl pre06044227

[19] J. Monaghan, Extrapolating B splines for interpolation. J. Comput. Phys. 60 (1985) 253-262. | MR 805872 | Zbl 0588.41005

[20] J. Monaghan, An introduction to sph. Comput. Phys. Commun. 48 (1988) 89-96. | Zbl 0673.76089

[21] A. Munshi, The OpenCL Specification. Khronos OpenCL Working Group (2011).

[22] M. Ould-Salihi, G.-H. Cottet and M. El Hamraoui, Blending finite-difference and vortex methods for incompressible flow computations. SIAM J. Sci. Comput. 22 (2000) 1655-1674. | MR 1813291 | Zbl 0993.76057

[23] T. Respaud and E. Sonnendruücker, Analysis of a new class of forward semi-lagrangian schemes for the 1d Vlasov-Poisson equations. Numer. Math. 118 (2011) 329-366. | MR 2800712 | Zbl 1284.65145

[24] D. Rossinelli, M. Bergdorf, G.H. Cottet and P. Koumoutsakos, GPU accelerated simulations of bluff body flows using vortex methods. J. Comput. Phys. 229 (2010) 3316-3333. | MR 2601102 | Zbl pre05693261

[25] D. Rossinelli, C. Conti and P. Koumoutsakos, Mesh-particle interpolations on graphics processing units and multicorecentral processing units. Philosophical Transactions of the Royal Society A: Mathematical, Phys. Engrg. Sci. 369 (2011) 2164-2175. | MR 2795279 | Zbl 1223.68122

[26] D. Rossinelli and P. Koumoutsakos, Vortex methods for incompressible flow simulations on the GPU. Visual Comput. 24 (2008) 699-708.

[27] G. Ruetsch and P. Micikevicius, Optimizing matrix transpose in cuda. NVIDIA CUDA SDK Application Note (2009).

[28] I. Sbalzarini, J. Walther, M. Bergdorf, S. Hieber, E. Kotsalis and P. Koumoutsakos, PPM-a highly efficient parallel particle-mesh library for the simulation of continuum systems. J. Comput. Phys. 215 (2006) 566-588. | Zbl 1173.76398

[29] I. Schoenberg, Contribution to the problem of approximation of equidistant data by analytic functions. Q. Appl. Math. 4 (1946) 45-99. | MR 15914 | Zbl 0061.28804

[30] D. Valdez-Balderas, J. Dominguez, B. Rogers and A. Crespo, Towards accelerating smoothed particle hydrodynamics simulations for free-surface flows on multi-gpu clusters. J. Parallel Distrib. Comput. 73 (2012) 1483-1493.

[31] F. De Vuyst and F. Salvarani, GPU-accelerated numerical simulations of the knudsen gas on time- dependent domains. Comput. Phys. Commun. 184 (2013) 532-536. | MR 3007037 | Zbl pre06381377

[32] R. Yokota, L. Barba, T. Narumi and K. Yasuoka, Petascale turbulence simulation using a highly parallel fast multipole method. Comput. Phys. Commun. 184 (2013) 445-455. | MR 3007029

[33] Y. Zhang, J. Cohen and J.D. Owens, Fast tridiagonal solvers on the GPU. SIGPLAN Not. 45 (2010) 127-136.