Paper Info
Title
Efficient Algorithms for Some Specific FFTs on a Massively Parallel Computer
Abstract
Even and quarter-even symmetric discrete Fourier transforms are variants of the discrete Fourier transform (DFT) in which all redundant operations induced on the DFT equations by the presence of either an even or quarter-even symmetry in the input data have been eliminated. These kinds of transforms appear frequently in image processing and in the core procedures of some direct methods for the numerical solution of the Poisson equation. Fast methods for computing even and the quarter-even DFTs when the number of data samples is a power of two, have been proposed by Swarztrauber and Briggs. Their methods are generalizable to any factorizable number of data samples. This article is a development of an idea originally proposed by Seguel et. al. to compute even and quarter-even symmetric FFTs of prime length. We review the theoretical background of this approach and adopt it to algorithms which we implement on a distributed SIMD massively parallel computer-the MasPar MP-1. We show comparisons between the extended Rader`s approach of prime length to our approach for the even and the quarter-even cases of prime length, to confirm the superiority of our methods.
Year
Venue
Field
1995
PPSC
Prime (order theory),Computer science,Massively parallel,Direct methods,Parallel computing,SIMD,Algorithm,Image processing,Fourier transform,Discrete Fourier transform,Power of two
DocType
Citations 
PageRank 
Conference
1
0.37
References 
Authors
0
2
Name
Order
Citations
PageRank
Avijit Purkayastha1132.69
Jaime Seguel23910.02