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.
@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},
volume = {48},
year = {2014},
pages = {1029-1060},
doi = {10.1051/m2an/2014009},
mrnumber = {3264345},
language = {en},
url = {http://dml.mathdoc.fr/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, Tome 48 (2014) pp. 1029-1060. doi : 10.1051/m2an/2014009. http://gdmltest.u-ga.fr/item/M2AN_2014__48_4_1029_0/
[1] , and , Multilevel adaptive particle methods for convection-diffusion equations. SIAM Multiscale Model. Simul. 4 (2005) 328-357. | MR 2164720 | Zbl 1088.76055
[2] and , A lagrangian particle-wavelet method. SIAM Multiscale Model. Simul. 5 (2006) 980-995. | MR 2272307 | Zbl 1122.65085
[3] , and , A portable opencl implementation of generic particle-mesh and mesh-particle interpolation in 2d and 3d. Parallel Comput. 39 (2013) 94-111.
[4] , Numerical study of slightly viscous flow. J. Fluid Mech. 57 (1973) 785-796. | MR 395483
[5] , and , 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] , and , The remapped particle-mesh semi-lagrangian advection scheme. Q. J. Meteorol. Soc. 133 (2007) 251-260.
[7] and , Vortex methods. Cambridge University Press (2000). | MR 1755095 | Zbl 0953.76001
[8] and , Particle methods revisited: a class of high order finite-difference methods. C.R. Math. 343 (2006) 51-56. | MR 2241959 | Zbl 1096.65084
[9] , and , 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] and , Simulation Using Particles. Inst. Phys. Publ. (1988).
[11] , , , , and , PyCUDA and PyOpenCL: A Scripting-Based Approach to GPU Run-Time Code Generation. Parallel Comput. 38 (2012) 157-174.
[12] , Inviscid axisymmetrization of an elliptical vortex. J. Comput. Phys. 138 (1997) 821-857. | MR 1607496 | Zbl 0902.76080
[13] and , 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] , and , Méthodologie et environnement de développement orientés objets: de l'analyse mathématique à la programmation. MATAPLI 70 (2003) 79-92.
[15] , 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] . Computing three-dimensional incompressible flows with vortex elements. Annu. Rev. Fluid Mech. 17 (1985) 523-559. | Zbl 0596.76026
[17] , High-resolution conservative algorithms for advection in incompressible flow. SIAM J. Numer. Anal. 33 (1996) 627-665. | MR 1388492 | Zbl 0852.76057
[18] and , Accurate, non-oscillatory, remeshing schemes for particle methods. J. Comput. Phys. 231 (2012) 152-172. | MR 2846992 | Zbl pre06044227
[19] , Extrapolating B splines for interpolation. J. Comput. Phys. 60 (1985) 253-262. | MR 805872 | Zbl 0588.41005
[20] , An introduction to sph. Comput. Phys. Commun. 48 (1988) 89-96. | Zbl 0673.76089
[21] , The OpenCL Specification. Khronos OpenCL Working Group (2011).
[22] , and , Blending finite-difference and vortex methods for incompressible flow computations. SIAM J. Sci. Comput. 22 (2000) 1655-1674. | MR 1813291 | Zbl 0993.76057
[23] and , 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] , , and , GPU accelerated simulations of bluff body flows using vortex methods. J. Comput. Phys. 229 (2010) 3316-3333. | MR 2601102 | Zbl pre05693261
[25] , and , 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] and , Vortex methods for incompressible flow simulations on the GPU. Visual Comput. 24 (2008) 699-708.
[27] and , Optimizing matrix transpose in cuda. NVIDIA CUDA SDK Application Note (2009).
[28] , , , , and , 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] , 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] , , and , Towards accelerating smoothed particle hydrodynamics simulations for free-surface flows on multi-gpu clusters. J. Parallel Distrib. Comput. 73 (2012) 1483-1493.
[31] and , GPU-accelerated numerical simulations of the knudsen gas on time- dependent domains. Comput. Phys. Commun. 184 (2013) 532-536. | MR 3007037 | Zbl pre06381377
[32] , , and , Petascale turbulence simulation using a highly parallel fast multipole method. Comput. Phys. Commun. 184 (2013) 445-455. | MR 3007029
[33] , and , Fast tridiagonal solvers on the GPU. SIGPLAN Not. 45 (2010) 127-136.