  In his monograph Chebyshev and Fourier Spectral Methods, John Boyd claimed
that, regarding Fourier spectral methods for solving differential equations,
``[t]he virtues of the Fast Fourier Transform will continue to improve as the
relentless march to larger and larger [bandwidths] continues''. This paper
attempts to further the virtue of the Fast Fourier Transform (FFT) as not only
bandwidth is pushed to its limits, but also the dimension of the problem.
Instead of using the traditional FFT however, we make a key substitution: a
high-dimensional, sparse Fourier transform (SFT) paired with randomized rank-1
lattice methods. The resulting sparse spectral method rapidly and automatically
determines a set of Fourier basis functions whose span is guaranteed to contain
an accurate approximation of the solution of a given elliptic PDE. This much
smaller, near-optimal Fourier basis is then used to efficiently solve the given
PDE in a runtime which only depends on the PDE's data compressibility and
ellipticity properties, while breaking the curse of dimensionality and
relieving linear dependence on any multiscale structure in the original
problem. Theoretical performance of the method is established herein with
convergence analysis in the Sobolev norm for a general class of non-constant
diffusion equations, as well as pointers to technical extensions of the
convergence analysis to more general advection-diffusion-reaction equations.
Numerical experiments demonstrate good empirical performance on several
multiscale and high-dimensional example problems, further showcasing the
promise of the proposed methods in practice.
