next up previous contents
Next: Contents Contents

NFFT 3.0 - Tutorial

Jens Keiner^[*]

Stefan Kunis^[*]

Daniel Potts^[*]

---

---

Footnotes

... Keiner ^[*]

keiner@math.uni-luebeck.de,University of Lübeck, Institute of Mathematics, 23560 Lübeck

... Kunis ^[*]

kunis@mathematik.tu-chemnitz.de, Chemnitz University of Technology, Department of Mathematics, 09107 Chemnitz, Germany

... Potts ^[*]

potts@mathematik.tu-chemnitz.de, Chemnitz University of Technology, Department of Mathematics, 09107 Chemnitz, Germany

---

• Contents
• Introduction
• Notation, the NDFT, and the NFFT
  • NDFT - nonequispaced discrete Fourier transform
    • Equispaced nodes
  • NFFT - nonequispaced fast Fourier transform
    • The ansatz
    • The window function
    • The first approximation - cut-off in frequency domain
    • The second approximation - cut-off in time/spatial domain
    • The case $ d>1$
    • The algorithm
  • Available window functions and evaluation techniques
    • Fully precomputed window function
    • Tensor product based precomputation
    • Linear interpolation from a lookup table
    • Fast Gaussian gridding
    • No precomputation of the window function
  • Further NFFT approaches
  
  
• Generalisations and inversion
  • NNFFT - nonequispaced in time and frequency fast Fourier transform
  • NFCT/NFST - nonequispaced fast (co)sine transform
  • NSFFT - nonequispaced sparse fast Fourier transform
  • FPT - fast polynomial transform
  • NFSFT - nonequispaced fast spherical Fourier transform
    • Spherical coordinates
    • Legendre polynomials and associated Legendre functions
    • Spherical harmonics
  • Solver - inverse transforms
    • Least squares
    • Interpolation
  
  
• Library
  • Installation
  • Procedure for computing an NFFT
    • Initialisation
    • Setting nodes
    • Precompute $ \tilde \psi$
    • Doing the transform
    • Finalisation
    • Data structure and functions
  • Generalisations and nomenclature
    • NFSFT
  • Inversion and solver module
  
  
• Examples
  • Computing your first transform
  • Computation time vs. problem size
  • Accuracy vs. window function and cut-off parameter $ m$
  • Computing an inverse transform
  
  
• Applications
  • Summation of smooth and singular kernels
  • Fast Gauss transform
  • Summation of zonal functions on the sphere
  • Iterative reconstruction in magnetic resonance imaging
  • Computation of the polar FFT
  • Radon transform, computer tomography, and ridgelet transform
  
  
• Bibliography
• About this document ...

---

Jens Keiner 2006年11月20日