Convolutive decomposition and fast summation methods for discrete-velocity approximations of the Boltzmann equation

Clément Mouhot, Lorenzo Pareschi, Thomas Rey
(19/01/2012 arXiv:1201:3986Math. Mod. Num. Anal. 47, 2013, 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, L.Pareschi, Math. Comp.75, 2006, we derive fast summation techniques for the evaluation of discrete-velocity schemes which permits to reduce the computational cost from O(N2d+1to O(NdlogNwith almost no loss of accuracy.