Convolutive decomposition and fast summation methods for discrete-velocity approximations of the Boltzmann equation
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 47 (2013) no. 5, p. 1515-1531

Discrete-velocity approximations represent a popular way for computing the Boltzmann collision operator. The direct numerical evaluation of such methods involve a prohibitive cost, typically O(N2d + 1) where d is the dimension of the velocity space. In this paper, following the ideas introduced in [C. Mouhot and L. Pareschi, C. R. Acad. Sci. Paris Sér. I Math. 339 (2004) 71-76, C. Mouhot and L. Pareschi, Math. Comput. 75 (2006) 1833-1852], we derive fast summation techniques for the evaluation of discrete-velocity schemes which permits to reduce the computational cost from O(N2d + 1) to O(N̅dNd log2N),  ≪ N, with almost no loss of accuracy.

DOI : https://doi.org/10.1051/m2an/2013078
Classification:  65T50,  68Q25,  74S25,  76P05
Keywords: Boltzmann equation, discrete-velocity approximations, discrete-velocity methods, fast summation methods, farey series, convolutive decomposition
@article{M2AN_2013__47_5_1515_0,
     author = {Mouhot, Cl\'ement and Pareschi, Lorenzo and Rey, Thomas},
     title = {Convolutive decomposition and fast summation methods for discrete-velocity approximations of the Boltzmann equation},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {5},
     year = {2013},
     pages = {1515-1531},
     doi = {10.1051/m2an/2013078},
     mrnumber = {3100773},
     language = {en},
     url = {http://www.numdam.org/item/M2AN_2013__47_5_1515_0}
}
Mouhot, Clément; Pareschi, Lorenzo; Rey, Thomas. Convolutive decomposition and fast summation methods for discrete-velocity approximations of the Boltzmann equation. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 47 (2013) no. 5, pp. 1515-1531. doi : 10.1051/m2an/2013078. http://www.numdam.org/item/M2AN_2013__47_5_1515_0/

[1] A. Bobylev and S. Rjasanow, Difference scheme for the Boltzmann equation based on the fast Fourier transform. Eur. J. Mech. B Fluids 16 (1997) 293-306. | MR 1439069 | Zbl 0881.76061

[2] A.V. Bobylev, Exact solutions of the Boltzmann equation. Dokl. Akad. Nauk SSSR 225 (1975) 1296-1299. | MR 398380 | Zbl 0361.76082

[3] A.V. Bobylev, A. Palczewski and J. Schneider, On approximation of the Boltzmann equation by discrete velocity models. C. R. Acad. Sci. Paris Sér. I Math. 320 (1995) 639-644. | MR 1322351 | Zbl 0834.76078

[4] A.V. Bobylev and S. Rjasanow, Fast deterministic method of solving the Boltzmann equation for hard spheres. Eur. J. Mech. B Fluids 18 (1999) 869-887. | MR 1728639 | Zbl 0965.76059

[5] A.V. Bobylev and S. Rjasanow, Numerical solution of the Boltzmann equation using a fully conservative difference scheme based on the fast fourier transform. Trans. Theory Statist. Phys. 29 (2000) 289-310. | MR 1770434 | Zbl 1017.82042

[6] A.V. Bobylev and M.C. Vinerean, Construction of discrete kinetic models with given invariants. J. Statist. Phys. 132 (2008) 153-170. | MR 2407374 | Zbl 1214.82087

[7] C. Buet, A discrete-velocity scheme for the Boltzmann operator of rarefied gas dynamics. Trans. Theory Statist. Phys. 25 (1996) 33-60. | MR 1380030 | Zbl 0857.76079

[8] H. Cabannes, R. Gatignol and L.-S. Luo, The Discrete Boltzmann Equation (Theory and Applications). University of California, College of engineering, Los-Angeles (2003). | MR 2012006

[9] C. Canuto, M.Y. Hussaini, A. Quarteroni and T.A. Zang, Spectral methods in fluid dynamics. Springer Series in Computational Physics. Springer-Verlag, New York (1988). | MR 917480 | Zbl 0717.76004

[10] T. Carleman, Sur la théorie de l'équation intégrodifférentielle de Boltzmann. Acta Math. 60 (1933) 91-146. | JFM 59.0404.02 | MR 1555365

[11] C. Cercignani, Theory and application of the Boltzmann equation. Elsevier, New York (1975). | MR 406273 | Zbl 0403.76065

[12] C. Cercignani, R. Illner and M. Pulvirenti, The mathematical theory of dilute gases, in vol. 106 of Appl. Math. Sci. Springer-Verlag, New York (1994). | MR 1307620 | Zbl 0813.76001

[13] J.W. Cooley and J.W. Tukey, An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19 (1965) 297-301. | MR 178586 | Zbl 0127.09002

[14] F. Coquel, F. Rogier and J. Schneider, A deterministic method for solving the homogeneous Boltzmann equation. Rech. Aérospat. 3 (1992) 1-10. | MR 1192070 | Zbl 0747.65098

[15] F. Filbet, J.W. Hu and S. Jin, A numerical scheme for the quantum Boltzmann equation efficient in the fluid regime. ESAIM: M2AN 42 (2012) 443-463. | Numdam | Zbl 1277.82046

[16] F. Filbet and C. Mouhot, Analysis of spectral methods for the homogeneous Boltzmann equation. Trans. Amer. Math. Soc. 363 (2011) 1947-1980. | MR 2746671 | Zbl 1213.82069

[17] F. Filbet, C. Mouhot and L. Pareschi, Solving the Boltzmann equation in N log2N. SIAM J. Sci. Comput. 28 (2006) 1029. | MR 2240802 | Zbl 1174.82012

[18] I. Gamba and S.H. Tharkabhushanam, Spectral-Lagrangian methods for collisional models of non-equilibrium statistical states. J. Comput. Phys. 228 (2009) 2012-2036. | MR 2500671 | Zbl 1159.82320

[19] G.H. Hardy and E.M. Wright, An introduction to the theory of numbers, sixth ed. Oxford University Press, Oxford (2008). Revised by D.R. Heath-Brown and J.H. Silverman, with a foreword by Andrew Wiles. | MR 2445243 | Zbl 1159.11001

[20] J. Hu and L. Ying, A fast spectral algorithm for the quantum Boltzmann collision operator, to appear in CMS. Preprint (2011). | MR 2911206 | Zbl 1260.82068

[21] I. Ibragimov and S. Rjasanow, Numerical solution of the Boltzmann equation on the uniform grid. Comput. 69 (2002) 163-186. | MR 1954793 | Zbl 1010.82036

[22] P. Kowalczyk, A. Palczewski, G. Russo and Z. Walenta, Numerical solutions of the Boltzmann equation: comparison of different algorithms. Eur. J. Mech. B Fluids 27 (2008) 62-74. | MR 2378496 | Zbl 1129.76040

[23] M. Krook and T.T. Wu, Exact solutions of the Boltzmann equation. Phys. Fluids 20 (1977) 1589. | Zbl 0369.76075

[24] P. Markowich and L. Pareschi, Fast, conservative and entropic numerical methods for the Boson Boltzmann equation. Numer. Math. 99 (2005) 509-532. | MR 2117737 | Zbl 1204.82031

[25] Y.-L. Martin, F. Rogier and J. Schneider, Une méthode déterministe pour la résolution de l'équation de Boltzmann inhomogène. C. R. Acad. Sci. Paris Sér. I Math. 314 (1992) 483-487. | MR 1154392 | Zbl 0747.65098

[26] P. Michel and J. Schneider, Approximation simultanée de réels par des nombres rationnels et noyau de collision de l'équation de Boltzmann. C. R. Acad. Sci. Sér. I Math. 330 (2000) 857-862. | MR 1769961 | Zbl 0960.65145

[27] C. Mouhot and L. Pareschi, Fast methods for the Boltzmann collision integral. C. R. Acad. Sci. Paris Sér. I Math. 339 (2004) 71-76. | MR 2075236 | Zbl 1054.76067

[28] C. Mouhot and L. Pareschi, Fast algorithms for computing the Boltzmann collision operator. Math. Comput. 75 (2006) 1833-1852. | MR 2240637 | Zbl 1105.76043

[29] A. Nogueira and B. Sevennec, Multidimensional Farey partitions. Indag. Math. (N.S.) 17 (2006) 437-456. | MR 2321111 | Zbl 1142.11006

[30] V.A. Panferov and A.G. Heintz, A new consistent discret-velocity model for the Boltzmann equation. Math. Models Methods Appl. Sci. 25 (2002) 571-593. | MR 1895119 | Zbl 0997.82036

[31] L. Pareschi and B. Perthame, A Fourier spectral method for homogeneous Boltzmann equations. In Proc. of the Second International Workshop on Nonlinear Kinetic Theories and Mathematical Aspects of Hyperbolic Systems (Sanremo, 1994), Trans. Theory Statist. Phys. 25 (1996) 369-382. | MR 1407541 | Zbl 0870.76074

[32] L. Pareschi and G. Russo, Numerical solution of the Boltzmann equation. I. Spectrally accurate approximation of the collision operator. SIAM J. Numer. Anal. 37 (2000) 1217-1245. | MR 1756425 | Zbl 1049.76055

[33] L. Pareschi and G. Russo, On the stability of spectral methods for the homogeneous Boltzmann equation. In Proc. of the Fifth International Workshop on Mathematical Aspects of Fluid and Plasma Dynamics (Maui, HI 1998). Trans. Theory Statist. Phys. 29 (2000) 431-447. | MR 1770438 | Zbl 1019.82016

[34] T. Płatkowski and R. Illner, Discrete velocity models of the Boltzmann equation: a survey on the mathematical aspects of the theory. SIAM Rev. 30 (1988) 213-255. | MR 941111 | Zbl 0668.76087

[35] T. Platkowski and W. Walús, An acceleration procedure for discrete velocity approximation of the Boltzmann collision operator. Comput. Math. Appl. 39 (2000) 151-163. | MR 1742479 | Zbl 0949.65141

[36] F. Rogier and J. Schneider, A direct method for solving the Boltzmann equation. Trans. Theory Statist. Phys. 23 (1994) 313-338. | MR 1257657 | Zbl 0811.76050

[37] D. Valougeorgis and S. Naris, Acceleration schemes of the discrete velocity method: Gaseous flows in rectangular microchannels. SIAM J. Sci. Comput. 25 (2003) 534-552. | MR 2058074 | Zbl 1163.65302

[38] C. Villani, A review of mathematical topics in collisional kinetic theory. Elsevier Science (2002). | MR 1942465 | Zbl 1170.82369