  The paper discusses the construction of high dimensional spatial
discretizations for arbitrary multivariate trigonometric polynomials, where the
frequency support of the trigonometric polynomial is known. We suggest a
construction based on the union of several rank-1 lattices as sampling scheme
and call such schemes multiple rank-1 lattices. This approach automatically
makes available a fast discrete Fourier transform (FFT) on the data.
  The key objective of the construction of spatial discretizations is the
unique reconstruction of the trigonometric polynomial using the sampling values
at the sampling nodes. We develop construction methods for multiple rank-1
lattices that allow for this unique reconstruction and for estimates of the
number $M$ of distinct sampling nodes within the resulting spatial
discretizations. Assuming that the multivariate trigonometric polynomial under
consideration is a linear combination of $T$ trigonometric monomials, the
oversampling factor $M/T$ is independent of the spatial dimension and, roughly
speaking, with high probability only logarithmic in $T$, which is much better
than the oversampling factor that is expected when using one single rank-1
lattice.
  The newly developed approaches for the construction of spatial
discretizations are probabilistic methods. The arithmetic complexity of these
algorithms depend only linearly on the spatial dimension and, with high
probability, only linearly on $T$ up to some logarithmic factors.
  Furthermore, we analyze the computational complexities of the resulting FFT
algorithms in detail and obtain upper bounds in $\mathcal{O}\left(M\log
M\right)$, where the constants depend only linearly on the spatial dimension.
With high probability, we construct spatial discretizations where $M/T\le C\log
T$ holds, which implies that the complexity of the corresponding FFT converts
to $\mathcal{O}\left(T\log^2 T\right)$.
