High order semi-lagrangian particle methods for transport equations: numerical analysis and implementation issues

Cottet, G.-H.; Etancelin, J.-M.; Perignon, F.; Picard, C.

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 48 (2014) no. 4, pp. 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.

[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 | Zbl

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

[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

[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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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

[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

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

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

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

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

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

[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 | Zbl

[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 | Zbl

[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

[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 | Zbl

[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

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

[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

[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

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