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

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

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2014)

  • Volume: 48, Issue: 4, page 1029-1060
  • ISSN: 0764-583X

Abstract

top
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.

How to cite

top

Cottet, G.-H., et al. "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 48.4 (2014): 1029-1060. <http://eudml.org/doc/273120>.

@article{Cottet2014,
abstract = {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.},
author = {Cottet, G.-H., Etancelin, J.-M., Perignon, F., Picard, C.},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {advection equations; particle methods; semi-lagrangian methods; GPU computing; multidimensional transport equation; particle method; remeshing; convergence; stability; semi-Lagrangian methods; numerical examples; algorithm},
language = {eng},
number = {4},
pages = {1029-1060},
publisher = {EDP-Sciences},
title = {High order semi-lagrangian particle methods for transport equations: numerical analysis and implementation issues},
url = {http://eudml.org/doc/273120},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Cottet, G.-H.
AU - Etancelin, J.-M.
AU - Perignon, F.
AU - Picard, C.
TI - High order semi-lagrangian particle methods for transport equations: numerical analysis and implementation issues
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 4
SP - 1029
EP - 1060
AB - 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.
LA - eng
KW - advection equations; particle methods; semi-lagrangian methods; GPU computing; multidimensional transport equation; particle method; remeshing; convergence; stability; semi-Lagrangian methods; numerical examples; algorithm
UR - http://eudml.org/doc/273120
ER -

References

top
  1. [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. Zbl1088.76055MR2164720
  2. [2] M. Bergdorf and P. Koumoutsakos, A lagrangian particle-wavelet method. SIAM Multiscale Model. Simul.5 (2006) 980–995. Zbl1122.65085MR2272307
  3. [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. [4] A. Chorin, Numerical study of slightly viscous flow. J. Fluid Mech.57 (1973) 785–796. MR395483
  5. [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. Zbl05355893MR2463200
  6. [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. [7] G.-H. Cottet and P. Koumoutsakos, Vortex methods. Cambridge University Press (2000). Zbl0953.76001MR1755095
  8. [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. Zbl1096.65084MR2241959
  9. [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. Zbl1197.82012MR2678446
  10. [10] R. Hockney and J. Eastwood, Simulation Using Particles. Inst. Phys. Publ. (1988). Zbl0662.76002
  11. [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. [12] P. Koumoutsakos, Inviscid axisymmetrization of an elliptical vortex. J. Comput. Phys.138 (1997) 821–857. Zbl0902.76080MR1607496
  13. [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. Zbl0849.76061
  14. [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. MATAPLI70 (2003) 79–92. 
  15. [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. MR3151833
  16. [16] A. Leonard. Computing three-dimensional incompressible flows with vortex elements. Annu. Rev. Fluid Mech.17 (1985) 523–559. Zbl0596.76026
  17. [17] R.J. LeVeque, High-resolution conservative algorithms for advection in incompressible flow. SIAM J. Numer. Anal.33 (1996) 627–665. Zbl0852.76057MR1388492
  18. [18] A. Magni and G.-H. Cottet, Accurate, non-oscillatory, remeshing schemes for particle methods. J. Comput. Phys.231 (2012) 152–172. Zbl06044227MR2846992
  19. [19] J. Monaghan, Extrapolating B splines for interpolation. J. Comput. Phys.60 (1985) 253–262. Zbl0588.41005MR805872
  20. [20] J. Monaghan, An introduction to sph. Comput. Phys. Commun.48 (1988) 89–96. Zbl0673.76089
  21. [21] A. Munshi, The OpenCL Specification. Khronos OpenCL Working Group (2011). 
  22. [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. Zbl0993.76057MR1813291
  23. [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. Zbl1284.65145MR2800712
  24. [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. Zbl1307.76066MR2601102
  25. [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. Zbl1223.68122MR2795279
  26. [26] D. Rossinelli and P. Koumoutsakos, Vortex methods for incompressible flow simulations on the GPU. Visual Comput.24 (2008) 699–708. 
  27. [27] G. Ruetsch and P. Micikevicius, Optimizing matrix transpose in cuda. NVIDIA CUDA SDK Application Note (2009). 
  28. [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. Zbl1173.76398
  29. [29] I. Schoenberg, Contribution to the problem of approximation of equidistant data by analytic functions. Q. Appl. Math.4 (1946) 45–99. Zbl0061.28804MR15914
  30. [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. [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. Zbl1302.76157MR3007037
  32. [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. MR3007029
  33. [33] Y. Zhang, J. Cohen and J.D. Owens, Fast tridiagonal solvers on the GPU. SIGPLAN Not.45 (2010) 127–136. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.