**ABSTRACT:**

We use the recently developed fast Fourier transform at

nonequispaced knots (NFFT) in a variety of applications.

The NFFT realises the fast computation of the sums

$$

f(w_j) = \sum_{k\in [-N/2,N/2)^d\cap\mathbb Z^d} \hat f_k \; {\rm e}^{ -2 \pi \mbox{\rm \scriptsize{i}} k w_j}

\qquad (j = 0,\ldots,M-1)

$$

where $w_j \in [-1/2,1/2)^d$.

Software: http://www.tu-chemnitz.de/$\sim$potts/nfft

We discuss fast and reliable algorithm for the optimal interpolation of scattered data

on the torus ${\mathbb T}^d$ by multivariate trigonometric polynomials as well as the approximation problem.

The algorithm is based on a variant of the conjugate gradient method in

combination with the fast Fourier transforms for nonequispaced nodes.

We present a worst case analysis as well as results based on probabilistic arguments.

The main result is that under mild assumptions the total complexity for

solving the interpolation or approximation problem at $M$ arbitrary nodes is

of order ${\cal O}(N^d\log N+M)$.

Finally, we apply these methods in magnetic resonance imaging.

This talk based on joint results with S. Kunis (TU-Chemnitz), A. B\"ottcher (TU-Chemnitz) and H. Eggers

(Philips Hamburg).