Generalisations
Besides the nonequispaced fast Fourier transform itself, the NFFT library contains fast algorithms for several generalisations: other sampling patterns in time and frequency, other function systems, and other domains than the torus.
- NNFFT – time and frequency nonequispaced
- Fourier transform with nonequispaced data in both the time and the frequency domain.
- NFCT/NFST – nonequispaced DCT/DST
- Fast cosine and sine transforms for nonequispaced nodes.
- NSFFT – hyperbolic cross
- Nonequispaced sparse fast Fourier transform for trigonometric polynomials with frequencies on a hyperbolic cross.
- NFSFT – NFFT on the sphere
- Nonequispaced fast spherical Fourier transform, i.e., fast evaluation of spherical harmonic expansions at arbitrary points on the sphere \(\mathbb{S}^2\).
- NFSOFT – NFFT on SO(3)
- Nonequispaced fast Fourier transform on the rotation group \(SO(3)\).
- FPT – polynomials
- Fast polynomial transform for systems of algebraic polynomials satisfying a three-term recurrence relation.