Periodization and decimation for FFT's and crystallographic FFT's.
Item
-
Title
-
Periodization and decimation for FFT's and crystallographic FFT's.
-
Identifier
-
AAI9431347
-
identifier
-
9431347
-
Creator
-
Abdellatif, Yehya N.
-
Contributor
-
Adviser: Richard Tolimieri
-
Date
-
1994
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Engineering, Electronics and Electrical | Computer Science
-
Abstract
-
The increasing importance of large parallel computers in scientific and engineering applications requires new ideas for algorithm design and code generation. In recent years the Discrete Fourier Transform became an important tool in many applications of digital signal processing. A major reason for its importance is the existence of efficient algorithms computing the DFT. In the first part the Cooley-Tukey FFT is introduced and tensor product is used as a tool in the algorithm design. In the second part a Fourier transform on a finite abelian group is defined. This emphasizes the role of the abelian group which is used as a data indexing set of the Fourier transform computation. A generalization of the Cooley-Tukey Fourier transform algorithm will be presented that decomposes Fourier transform computations into independent smaller size computations. Periodization-Decimation algorithm with respect to group action is presented. With a periodizing subgroup that takes up the translational invariance in a crystallographic data, the result is independent blocks of equal size data each invariant under a point group. An implementation of the Periodization-Decimation algorithm using a super group with one dimensional translation and rotation symmetries used as the group generators is presented. The result is a set of 64 independent data blocks, on which computations can be executed in parallel. This super group as defined contains 80 crystallographic groups all of which can be solved by computing the proper subset of the 64 total computations. Finally specific examples and timing results are presented.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
