Fast algorithms for spherical harmonic expansions, II

We provide an efficient algorithm for calculating, at appropriately chosen points on the two-dimensional surface of the unit sphere in R3R3, the values of functions that are specified by their spherical harmonic expansions (a procedure known as the inverse spherical harmonic transform). We also provide an efficient algorithm for calculating the coefficients in the spherical harmonic expansions of functions that are specified by their values at these appropriately chosen points (a procedure known as the forward spherical harmonic transform). The algorithms are numerically stable, and, if the number of points in our standard tensor-product discretization of the surface of the sphere is proportional to l2l2, then the algorithms have costs proportional to l2ln(l)l2ln(l) at any fixed precision of computations. Several numerical examples illustrate the performance of the algorithms.