| The Fast Fourier Transform (FFT) describes a well known set of algorithms that allows a fast evaluation of the Discrete Fourier Transform (DFT). In FFTs, the original sequence is replaced by the sum of a shorter sequence of transforms [1]. This results in an optimal reduction in the number of computations. However, some applications present repeated sequences of data inside the input dataset. These are the so-called symmetries. By eliminating these repetitions storage and Input/Output operations might be reduced significantly. Compact symmetric FFTs [2] show the potential of this approach and appears as an attractive methodology for the implementation of a highly-efficient symmetric FFT.;An extension of Compact Symmetric FFTs [2] to multidimensional FFTs is presented in [3]. However, attempts to develop actual implementations from these high-level specifications have been, so far, unsuccessful. The main implementation problem is the recursiveness of the divide-and-conquer methodology proposed in [3].;This work aims at solving this difficulty by rewriting the algorithm in [3] as a non recursive method, implementable in terms of O( N3log N) passes through a fixed, non-redundant data set. Such a variant results from a slight but nontrivial modification of the mathematical framework proposed in [3]. This variant is restricted to symmetries that are representable by unimodular matrices, a condition satisfied by crystal symmetries.;The resulting algorithm is intended for use in the Shake-and-Bake method [4], for solving Crystal Structures from X-ray diffraction data. |
