Research

Nonuniform Fast Spherical Fourier Transforms

One of my primary research projects is the fast Fourier transform on the unit sphere ${\mathbb{S}}^2$ in ${\mathbb{R}}^3$. This is a generalisation of the well-known fast Fourier transform (FFT) to a different geometry, in this case the sphere (see Figure 1 below). A convenient basis for functions defined on the sphere are spherical harmonics which are solutions to Laplace's equation in three dimensions. Figure 2 below shows a spherical harmonic basis function on the sphere. More precisely, any function $f$ from the Hilbert space of square integrable functions on the unit sphere admits a representation in spherical coordinates $\theta$ and $\phi$,

${\displaystyle f\left(\theta ,\phi \right)=\sum _{l=0}^{\infty }\sum _{m=-l}^l{a}_l^m{Y}_l^m\left(\theta ,\phi \right)}$.

${\displaystyle f\left(\theta ,\phi \right)=\sum _{l=0}^L\sum _{m=-l}^l{a}_l^m{Y}_l^m\left(\theta ,\phi \right)}$.

(1)

${\displaystyle a_l^m=\sum _{m=1}^{\infty }\sum _{m=-l}^l{w}_{m}f\left({\theta }_m,{\phi }_m\right)Y_l^m\left({\theta }_m,{\phi }_m\right)}$.

(2)

In most cases, the number of points $M$ is of the same order of magnitude as the number of Fourier coefficients ${\left(L+1\right)}^2$ (we assume this from here on). The rationale is that the degrees of freedom for both transformations must be comparable if they are inverses of each other. Straightforward algorithms to compute the transformations have a typical arithmetical operation count proportional to $L^4$. This is way to slow for large-scale computations. The ultimate goal (which has been reached by some algorithms) is a cost proportional to $L^{2}logL$ matching the cost of a usual two-dimensional fast Fourier transform of same degree. In recent years, different approaches to these fast algorithms have been proposed. My research here is to develop new fast and stable algorithms, techniques and a good implementation for the transforms. This is also a numerical challenge as the functions involved can cause severe numerical instabilities if the wrong path is taken. Besides these implementation issues, my work also includes bringing these algorithms to the applications.

Figure1: Unit sphere $S^2$	Figure 2: Spherical Harmonic on $S^2$	Figure 3: Voronoi partition of a point set on $S^2$

Aufgrund technischer Probleme stehen zur Zeit nicht alle Seiten des Institutes zur Verfügung !