  We propose fast, exact and efficient algorithms for the convolution of two
arbitrary functions on the sphere which speed up computations by a factor
\order{\sqrt{N}} compared to present methods where $N$ is the number of pixels.
No simplifying assumptions are made other than bandlimitation. 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 {\em transpose convolution} which is needed for the iterative
solution of the normal equations.
