# zbMATH — the first resource for mathematics

A new algorithm for the nonequispaced fast Fourier transform on the rotation group. (English) Zbl 1259.65224
In this interesting paper, the authors present a novel fast and numerically stable algorithm for the approximate computation of the nonequispaced discrete Fourier transform on the rotation group SO(3) which is defined by the evaluation of $f(\alpha_q,\beta_q,\gamma_q) = \sum_{\ell=0}^L \sum_{m=-\ell}^{\ell} \sum_{n=-\ell}^{\ell} {\hat f}_{\ell}^{m,n}\,D_{\ell}^{m,n}(\alpha_q,\beta_q,\gamma_q) \quad (q = 1,\ldots, Q)$ for given Fourier coefficients $${\hat f}_{\ell}^{m,n}$$ and angles $$\alpha_q$$, $$\gamma_q\in [0,2\pi)$$ and $$\beta_q\in [0,\pi]$$, where $D_{\ell}^{m,n}(\alpha_q,\beta_q,\gamma_q)= \sqrt{\frac{2\ell +1}{8\pi^2}}\, \exp(-im\alpha_q - in\gamma_q)\,d_{\ell}^{m,n}(\cos\beta_q)\,.$ Here $$d_{\ell}^{m,n}$$ denote the Wigner-$$d$$ functions of orders $$m$$ and $$n$$. The computation steps read as follows:
(i) Separate the nonequispaced discrete SO(3) Fourier transform into a 2-dimensional Fourier sum and an inner sum of Wigner-$$d$$ functions of varying orders.
(ii) Reduce the orders of the Wigner-$$d$$ functions and convert the inner sum of Wigner-$$d$$ functions of low orders into a 1-dimensional Fourier sum.
(iii) Compute a 3-dimensional nonequispaced fast Fourier transform to obtain the desired result.
The main step (ii) is realized by a divide-and-conquer algorithm for an eigenvalue problem of a symmetric semiseparable matrix. This method needs $${\mathcal O}(L^3 \log L\,\log(1/\varepsilon) + Q\,\log^3(1/\varepsilon))$$ arithmetic operations for this transform at $$Q$$ nonequispaced nodes $$(\alpha_q,\beta_q,\gamma_q)$$ and with desired accuracy $$\varepsilon$$. In numerical tests, the advantage of the main part of this new transform is shown.

##### MSC:
 65T50 Numerical methods for discrete and fast Fourier transforms 42C10 Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) 42C20 Other transformations of harmonic type 65F15 Numerical computation of eigenvalues and eigenvectors of matrices
##### Software:
FFTW; MPACK; NFFT3
Full Text: