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

$\displaystyle 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

$\displaystyle \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$ .

The algorithms are implemented by Antje Vollrath in ./kernel/nfsoft. 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