Loading...
A new multidimensional crystallographic fast fourier transform
David-Venegas, Ivan A.
David-Venegas, Ivan A.
Citations
Altmetric:
Abstract
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.
La transformada rapida de Fourier (FFT) describe un conocido conjunto de algoritmos que permiten una rapida evaluacion de la Transformada Discreta de Fourier (DFT). En las FFTs, la secuencia original es reemplazada por la suma de transformadas mas pequeñas[1]. Este resultado es una óptima reducción en el número de computaciones. Por tanto, algunas aplicaciones presentan secuencias repetidas de datos al interior del conjunto de datos. Estas son las asi llamadas simetrias. Eliminando estas repeticiones las operaciones de almacenamiento y de Entrada/Salida podr³an ser reducidas significativamente. Las FFTs compactas simétricas [2] muestran el potencial de este enfoque y aparece como una atractiva metodolog³a para la implementación de una muy eficiente FFT simétrica. Una extensión de las FFTs Simétricas Compactas[2] a las FFTs multidimensionales es presentada en [3]. No obstante, los intentos por desarrollar una verdadera implementación desde estas especificaciones de alto nivel han sido poco exitosas. El principal problema de la implementación es la recursividad de la metodolog³a Divide y Venceras propuesto en [3]. Este trabajo se centra en solucionar esta dificultad, reescribiendo el algoritmo en [3] como un método no recursivo, implementable en términos de O(N3log N) pasadas a través de un conjunto fijo de datos no redundantes. Tal variante resulta de una pequeña modificación, no trivial, en la estructura matemática propuesta en [3]. Esta variación esta restringida a simetr³as representable por matrices unimodulares, una condición que satisfacen las simetr³as del cristal. El algoritmo final esta dirigido a ser usado como parte del método Shake-and-Bake [4], para la solución de Estructuras de Cristales a partir de los datos obtenidos usando la difracción de rayos X.
La transformada rapida de Fourier (FFT) describe un conocido conjunto de algoritmos que permiten una rapida evaluacion de la Transformada Discreta de Fourier (DFT). En las FFTs, la secuencia original es reemplazada por la suma de transformadas mas pequeñas[1]. Este resultado es una óptima reducción en el número de computaciones. Por tanto, algunas aplicaciones presentan secuencias repetidas de datos al interior del conjunto de datos. Estas son las asi llamadas simetrias. Eliminando estas repeticiones las operaciones de almacenamiento y de Entrada/Salida podr³an ser reducidas significativamente. Las FFTs compactas simétricas [2] muestran el potencial de este enfoque y aparece como una atractiva metodolog³a para la implementación de una muy eficiente FFT simétrica. Una extensión de las FFTs Simétricas Compactas[2] a las FFTs multidimensionales es presentada en [3]. No obstante, los intentos por desarrollar una verdadera implementación desde estas especificaciones de alto nivel han sido poco exitosas. El principal problema de la implementación es la recursividad de la metodolog³a Divide y Venceras propuesto en [3]. Este trabajo se centra en solucionar esta dificultad, reescribiendo el algoritmo en [3] como un método no recursivo, implementable en términos de O(N3log N) pasadas a través de un conjunto fijo de datos no redundantes. Tal variante resulta de una pequeña modificación, no trivial, en la estructura matemática propuesta en [3]. Esta variación esta restringida a simetr³as representable por matrices unimodulares, una condición que satisfacen las simetr³as del cristal. El algoritmo final esta dirigido a ser usado como parte del método Shake-and-Bake [4], para la solución de Estructuras de Cristales a partir de los datos obtenidos usando la difracción de rayos X.
Description
Date
2004
Journal Title
Journal ISSN
Volume Title
Publisher
Collections
Research Projects
Organizational Units
Journal Issue
Keywords
Fast fourier transform, Multidimensional crystallographic