  In this paper we present the first known deterministic algorithm for the
construction of multiple rank-1 lattices for the approximation of periodic
functions of many variables. The algorithm works by converting a potentially
large reconstructing single rank-1 lattice for some $ d $-dimensional frequency
set $ I \subset [N]^d $ into a collection of much smaller rank-1 lattices which
allow for accurate and efficient reconstruction of trigonometric polynomials
with coefficients in $ I $ (and, therefore, for the approximation of
multivariate periodic functions). The total number of sampling points in the
resulting multiple rank-1 lattices is theoretically shown to be less than $
\mathcal{O}\left( |I| \log^{ 2 }(N |I|) \right) $ with constants independent of
$d$, and by performing one-dimensional fast Fourier transforms on samples of
trigonometric polynomials with Fourier support in $ I $ at these points, we
obtain exact reconstruction of all Fourier coefficients in fewer than $
\mathcal{O}\left(d\,|I|\log^4 (N|I|)\right) $ total operations.
  Additionally, we present a second multiple rank-1 lattice construction
algorithm which constructs lattices with even fewer sampling points at the cost
of only being able to reconstruct exact trigonometric polynomials rather than
having additional theoretical approximation. Both algorithms are tested
numerically and surpass the theoretical bounds. Notably, we observe that the
oversampling factors #samples$/|I|$ appear to grow only logarithmically in $
|I| $ for the first algorithm and appear near-optimally bounded by four in the
second algorithm.
