The Fourier interpolation of 3D data-sets is a performance critical operation in many fields, including
certain forms of image processing and density functional theory (DFT) quantum chemistry codes based
on plane wave basis sets, to which this paper is targeted. In this paper we describe three different
algorithms for performing this operation built from standard discrete Fourier transform operations,
and derive theoretical operation counts. The algorithms compared consist of the most straightforward
implementation and two that exploit techniques such as phase-shifts and knowledge of zero padding
to reduce computational cost. Through a library implementation (tintl) we explore the performance
characteristics of these algorithms and the performance impact of different implementation choices on
actual hardware. We present comparisons within the linear-scaling DFT code ONETEP where we replace
the existing interpolation implementation with our library implementation configured to choose the most
efficient algorithm. Within the ONETEP Fourier interpolation stages, we demonstrate speed-ups of over
1.55×.