Unformatted text preview:

Lecture 7FFT7.1 FFTThe Fast Fourier Transform is perhaps the most important subroutine in scientific computing. Ithas applications ranging from multiplying numbers and polynomials to image and signal processing,time series analysis, and the solution of linear systems and PDEs. There are tons of books on thesubject including two recent worderful ones by Charles van Loand and Briggs.The discrete Fourier transform of a vector x is y = Fnx, where Fnis the n×n matrix whose entry(Fn)jk= e−2πijk/n, j, k = 0 . . . n − 1. It is nearly always a good idea to use 0 based notation (aswith the C programming language) in the context of the discrete Fourier transform. The negativeexponent corresponds to Matlab’s definition. Indeed in matlab we obtain fn=fft(eye(n)).A good example isF4=1 1 1 11 −i −1 i1 −1 1 −11 i −1 −i.Sometimes it is convenient to denote (Fn)jk= ωjkn, where ωn= e−2π/n.The Fourier matrix has more interesting properties than any matrix deserves to have. It issymmetric (but not Hermitian). It is Vandermonde (but not ill-conditioned). It is unitary exceptfor a scale factor (1√nFnis unitary). In two ways the matrix is connected to group characters: thematrix itself is the character table of the finite cyclic group, and the eigenvectors of the matrix aredetermined from the character table of a multiplicative group.The trivial way to do the Fourier transform is to compute the matrix-vector multiply requiringn2multipilications and roughly the same number of additions. Cooley and Tukey gave the firstO(n log n) time algorithm (actually the algorithm may be found in Gauss’ work) known today asthe FFT algorithm. We shall assume that n = 2p.The Fourier matrix has the simple property that if Πnis an unshuffle operation, thenFnΠTn= Fn/2DnFn/2Fn/2−DnFn/2!, (7.1)where Dnis the diagonal matrix diag(1, ωn, . . . , ωn/2−1n).One DFT algorithm is then simply: 1) unshuffle the vector 2) recursively apply the FFT algo-rithm to the top half and the bottom half, then combine elements in the top part with correspondingelements in the bottom part (“the butterfly”) as prescribed by the matrix I DnI −Dn!.12 Math 18.337, Computer Science 6.338, SMA 5505, Spring 2004Everybody has their favorite way to visualize the FFT algorithm. For us, the right way is tothink of the data as living on a hypercube. The algorithm is then, permute the cube, perform theFFT on a pair of opposite faces, and then perform the butterfly, along edges across the dimensionconnecting the opposite faces.We now repeat the three steps of the recursive algorithm in index notation:• Step 1: id−1. . . i1i0→ i0id−1. . . i1• Step 2: i0id−1. . . i1→ i0fft(id−1. . . i1)• Step 3: →¯i0fft(id−1. . . i1)Here Step 1 is a data permutation, Step 2 refters to two FFTs, and Step 3 is the butterfly onthe high order bit.In conventional notation:yj= (Fnx)j=n−1Xk=0ωjknxkcan be cut into the even and the odd parts:yj=m−1Xk=0ω2jknx2k+ ωjn m−1Xk=0ω2jknx2k+1!;since ω2n= ωm, the two sums are just FFT(xeven) and FFT(xodd). With this remark (see Fig. 1),yj=Pm−1k=0ωjkmx2k+ ωjnPm−1k=0ωjkmx2k+1yj+m=Pm−1k=0ωjkmx2k− ωjnPm−1k=0ωjkmx2k+1.Then the algorithm keeps recurring; the entire “communication” needed for an FFT on a vector oflength 8 can be seen in Fig. 2.....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................FFT(xeven)ωjnFFT(xodd)+−yjyj+mFigure 7.1: Recursive block of the FFT.The number of operations for an FFT on a vector of length n equals to twice the number foran FFT on length n/2 plus n/2 on the top level. As the solution of this recurrence, we get thatthe total number of operations is12n log n.Now we analyze the data motion required to perform the FFT. First we assume that to eachprocessor one element of the vector x is assigned. Later we discuss the “real-life” case when thenumber of processors is less than n and hence each processor has some subset of elements. We alsodiscuss how FFT is implemented on the CM-2 and the CM-5.The FFT always goes from high order bit to low order bit, i.e., there is a fundamental asymmetrythat is not evident in the figures below. This seems to be related to the fact that one can obtaina subgroup of the cyclic group by alternating elements, but not by taking, say, the first half of theelements.Preface


View Full Document

MIT 18 337 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?