David-Venegas, Ivan A.

Profile Picture

Filters

20041
Reset filters

Settings

Citations

Publication Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Publication
    A new multidimensional crystallographic fast fourier transform
    (2004) David-Venegas, Ivan A.; Seguel, Jaime; College of Engineering; Rodriguez-Martinez, Manuel; Rivera-Gallego, Wilson; Department of Electrical and Computer Engineering; Walker-Ramos, Uroyoan R.
    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 multidimmensional FFTs is presented in [3]. However, attempts to develop actual implementations from these high-level specifications have been, so far, unsucessful. The main implementation problem is the recursiveness of the divide-and-conquer methodology proposed in [3]. This work aims at solving this difficulty by rewritting the algorithm in [3] as a non recursive method, implementable in terms of O(N3log N) passes through a fixed, nonredundant 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. ii The resulting algorithm is intended for use in the Shake-and-Bake method [4], for solving Crystal Structures from X-ray difraction data.