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̅ ≪ N, with almost no loss of accuracy.