Show simple item record

dc.contributor.advisorSeguel, Jaime
dc.contributor.authorDavid-Venegas, Ivan A.
dc.date.accessioned2019-05-14T14:54:12Z
dc.date.available2019-05-14T14:54:12Z
dc.date.issued2004
dc.identifier.urihttps://hdl.handle.net/20.500.11801/2159
dc.description.abstractThe 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.en_US
dc.description.abstractLa 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.en_US
dc.language.isoEnglishen_US
dc.subjectFast fourier transformen_US
dc.subjectMultidimensional crystallographicen_US
dc.titleA new multidimensional crystallographic fast fourier transformen_US
dc.typeThesisen_US
dc.rights.licenseAll rights reserveden_US
dc.rights.holder(c) 2004 Ivan A. David-Venegasen_US
dc.contributor.committeeRodriguez-Martinez, Manuel
dc.contributor.committeeRivera-Gallego, Wilson
dc.contributor.representativeWalker-Ramos, Uroyoan R.
thesis.degree.levelM.S.en_US
thesis.degree.disciplineComputer Engineeringen_US
dc.contributor.collegeCollege of Engineeringen_US
dc.contributor.departmentDepartment of Electrical and Computer Engineeringen_US
dc.description.graduationYear2004en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

  • Theses & Dissertations
    Items included under this collection are theses, dissertations, and project reports submitted as a requirement for completing a degree at UPR-Mayagüez.

Show simple item record

All rights reserved
Except where otherwise noted, this item's license is described as All Rights Reserved