Fast and exact reconstruction of arbitrary multivariate algebraic polynomials in Chebyshev form

We describe a fast method for the evaluation of an arbitrary high-dimensional multivariate algebraic polynomial in Chebyshev form at the nodes of an arbitrary rank-1 Chebyshev lattice. Our main focus is on conditions on rank-1 Chebyshev lattices allowing for the exact reconstruction of such polynomials from samples along such lattices. We present an algorithm for constructing suitable rank-1 Chebyshev lattices based on a component-by-component approach. Moreover, we give a method for the fast and exact reconstruction.