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
The full text of recent articles is available to journal subscribers only. See the article on the journal's website

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.