NFSOFT - NFFT on the rotation group

These algorithms calculate the fast Fourier synthesis and its adjoint on the rotation group $SO(3)$ for arbitrary sampling sets. They are based on the fast Fourier transform for nonequispaced nodes on the three-dimensional torus. Our algorithms evaluate the $SO(3)$ Fourier synthesis and its adjoint, respectively, of $B$-bandlimited functions at $M$ arbitrary input nodes.

This library of C functions evaluates a function $f\in {\mathrm{L}}^2(SO(3))$ with finite orthogonal expansion $$f(\alpha ,\beta ,\gamma )=\sum _{l=0}^B\sum _{m=-l}^l\sum _{n=-l}^l{\hat{f}}_l^{m,n}{D}_l^{m,n}(\alpha ,\beta ,\gamma ).$$ in terms of Wigner-D functions $D_l^{m,n}$ on a set of arbitary nodes $({\alpha }_d,{\beta }_d,{\gamma }_d)$, $d=1,\dots ,D$, $D\in \mathbb{N}$, in Euler angles. Furthermore, the fast evaluation of sums $${\tilde{\hat{f}}}_l^{m,n}:=\sum _{d=1}^{D}f({\alpha }_d,{\beta }_d,{\gamma }_d)\overline{D_l^{m,n}({\alpha }_d,{\beta }_d,{\gamma }_d)}$$ for given function values $f({\alpha }_d,{\beta }_d,{\gamma }_d)\in \mathbb{C}$ and all indices $l,m,n$ is the adjoint NFSOFT.

The algorithms are implemented by Antje Vollrath in ./kernel/nfsoft. The OpenMP parallelization and the Matlab interface in ./matlab/nfsoft are implemented by Michael Quellmalz. Related papers are

• Gräf, M., Potts, D.
  Sampling sets and quadrature formulae on the rotation group.
  Numer. Funct. Anal. Optim. 30, 665 - 688,   (full paper ps, pdf),   2009
   
• Potts, D., Prestin J., Vollrath A.
  A Fast algorithm for nonequispaced Fourier transforms on the rotation group.
  Numer. Algorithms, 52, 355 - 384,   (full paper ps, pdf),   2009
   
• Hielscher, R., Potts, D., Prestin, J., Schaeben, H., Schmalz, M.
  The Radon transform on SO(3): A Fourier slice theorem and numerical inversion.
  Inverse Problems 24, 025011,   (full paper ps, pdf),   2008