A FAST ALGORITHM FOR THE ENERGY SPACE BOSON BOLTZMANN COLLISION OPERATOR

Abstract. This paper introduces a fast algorithm for the energy space boson Boltzmann collision operator. Compared to the direct O(N3) calculation and the previous O(N2 logN) method [Markowich and Pareschi, 2005], the new algorithm runs in complexity O(N log2N), which is optimal up to a logarith-mic factor (N is the number of grid points in energy space). The basic idea is to partition the 3-D summation domain recursively into elementary shapes so that the summation within each shape becomes a special double convolution that can be computed efficiently by the fast Fourier transform. Numerical ex-amples are presented to illustrate the efficiency and accuracy of the proposed algorithm. 1