Jump to main content
Nonequispaced fast Fourier transform
NFFT on SO(3)

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}\widehat f^{m,n}_lD^{m,n}_l(\alpha,\beta,\gamma). \] in terms of Wigner-D functions \( D^{m,n}_l\) on a set of arbitary nodes \(\left(\alpha_d,\beta_d,\gamma_d\right)\), \(d=1,\ldots,D\), \(D \in \mathbb{N}\), in Euler angles. Furthermore, the fast evaluation of sums \[ \tilde{\widehat f}^{m,n}_l:= \sum_{d=1}^{D} f\left(\alpha_d,\beta_d,\gamma_d\right) \overline{ D^{m,n}_l \left(\alpha_d,\beta_d,\gamma_d\right)} \] for given function values \(f\left(\alpha_d,\beta_d,\gamma_d\right) \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