# A Fast Transform for Spherical Harmonics

## Martin James Mohlenkamp

## 1997

### Abstract:

Spherical Harmonics arise on the sphere S^2 in the same way that the
(Fourier) exponential functions {exp(i k theta)}, k an integer,
arise on the circle. Spherical Harmonic series have many of the same
wonderful properties as Fourier series, but have lacked one important thing:
a numerically stable fast transform analogous to the Fast Fourier
Transform. Without a fast transform, evaluating (or expanding in)
Spherical Harmonic series on the computer is slow --- for large
computations prohibitively slow.
This thesis provides a fast transform.

For a grid of N^2 points on the sphere, a direct calculation
has computational complexity O(N^4), but a simple
separation of variables and Fast Fourier Transform reduces it to
O(N^3) time. Here we present an algorithm with time
O(N^2log^2 N).

The problem quickly reduces to the fast application of matrices of
Associated Legendre Functions of certain orders.
The essential insight is that although these matrices are dense and
oscillatory, locally they
can be represented efficiently in trigonometric functions. We
construct an adaptive partition of each matrix into rectangles such
that each rectangle is sparse in (two dimensional) local trigonometric
series. The entire matrix can be represented in O(N log N)
coefficients in this non--standard form, with constants independent of
the order parameter. It can be applied in O(N log N)
time, but the overhead cost for adaption is O(N log^2 N).
Adding this over the orders yields the overall time
O(N^2 log^2 N).