  A fast and reliable algorithm for the optimal interpolation of scattered data
on the torus by multivariate trigonometric polynomials is presented. The
algorithm is based on a variant of the conjugate gradient method in combination
with the fast Fourier transforms for nonequispaced nodes. The main result is
that under mild assumptions the total complexity for solving the interpolation
problem at M arbitrary nodes is of order O(M logM). This result is obtained by
the use of localised trigonometric kernels where the localisation is chosen in
accordance to the spatial dimension d. Numerical examples show the efficiency
of the new algorithm.
