The crystallographic fast Fourier transform. I. p3 symmetry

An algorithm for computing the discrete Fourier transform of data with threefold symmetry axes is presented. This algorithm is straightforward and easily implemented. It reduces the computational complexity of such a Fourier transform by a factor of 3. There are no restrictive requirements imposed on the initial data. Explicit formulae and a scheme of computing the Fourier transform are given. The algorithm has been tested and benchmarked against FFT on the unit cell, revealing the expected increase in speed. This is a non-trivial example of a more general approach developed recently by the authors.