Speed comparison

For a two-dimensional dataset with dimensions, $N_x \times N_y$, the cost of a 1-D FFT in helical coordinates is proportional to

$$N_x N_y \log \left( N_x N_y \right).$$ (20)

For the same dataset, the cost of a 2-D FFT is

$$\begin{eqnarray} N_y \left( N_x \log N_x \right) + N_x \left( N_y \log N_y \righ... ...\right) \nonumber \ & = & N_x N_y \; \log \left( N_x N_y \right).\end{eqnarray}$$ (21)

Therefore, the cost of a 1-D helical FFT of a 2-D dataset is exactly the same as the cost of an 2-D FFT of the same dataset. The link between the two leads to no computational advantages in the number of operations.

However, other differences may lead to computational savings. For example, a 2-D FFT with a power-of-two algorithm requires both N_x and N_y to be powers of two. However, the 1-D helical FFT requires just N_x N_y to be a power of two, and so less zero-padding may be required.

The corollary, that a large 1-D FFT can be computed (with small inaccuracies) using a 2-D FFT algorithm, also leads to potential computational savings. Two-dimensional FFT's are easier to code to run both in parallel and out-of-core than 1-D FFT's, leading to significantly faster code and a lower memory requirement without the additional complexity of Singleton's algorithm Press et al. (1992).