(20) |

(21) |

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).

9/5/2000