Fast convolution on the sphere

We propose fast, exact and efficient algorithms for the convolution of two arbitrary functions on the sphere which speed up computations by a factor O (N) compared to present methods where N is the number of pixels. No simplifying assumptions are made other than band limitation. This reduces typical computation times for convolving the full sky with the asymmetric beam pattern of a megapixel cosmic microwave background (CMB) mission from months to minutes. Our methods enable realistic simulation and careful analysis of data from such missions, taking into account the effects of asymmetric ``point spread functions'' and far side lobes of the physical beam. While motivated by CMB studies, our methods are general and hence applicable to the convolution or filtering of any scalar field on the sphere with an arbitrary, asymmetric kernel. We show in an Appendix that the same ideas can be applied to the inverse problems of map-making and beam reconstruction by similarly accelerating the transpose convolution which is needed for the iterative solution of the normal equations.