Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0757.65154
Van Loan, Charles F.
Computational frameworks for the fast Fourier transform. (English)
[B] Frontiers in Applied Mathematics. 10. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. xiii, 273 p. (1992). ISBN 0-89871-285-8

The fast Fourier transform (FFT) is one of the important computational developments of this century. It has revolutionized many areas of scientific computation. Today we know many books on the FFT often written by specialists in computer science, digital signal processing or electrical engineering. The new book is written by a known researcher in numerical linear algebra. The central theme of the author is the idea that different FFTs correspond to different factorizations of the Fourier matrix into a product of sparse matrices which can often be represented as Kronecker products. Couching algorithms systematically in matrix/vector notation, the FFTs can be unified and described more understandable. All algorithms are written in a stylized Matlab notation which is familiar to those engaged in high-performance computing.\par This book contains 4 chapters. The first chapter is devoted to the basic principles of {radix-2} FFTs, namely Cooley-Tukey factorization, weight and butterfly computations, bit reversal and transposition, Cooley-Tukey algorithm, Stockham autosort algorithm, decimation in time, decimation in frequency.\par Chapter 2 on mixed-radix FFTs generalizes the factorization ideas developed in Chapter 1. Especially, radix-4 and radix-8 FFTs are discussed. The split-radix FFT is handled as an interesting reduced- arithmetic rearrangement of the radix-2 FFT.\par Chapter 3 is devoted to multidimensional FFTs and related topics. Here the author also describes the blocking of large single vector FFT and parallel FFTs ( distributed-memory FFT and shared-memory FFT).\par In the final chapter some extensions ( prime factor FFT, FFTs of real data) and some essential FFT-applications ( convolutions, fast trigonometric transforms, fast Poisson solvers) are discussed.\par This comprehensive book contains may examples, problems, notes and hints to the literature. It will be very useful for students as well as researchers who are interested in the application of the FFT.
[M.Tasche (Rostock)]

MSC 2000:: *65T50 Discrete and fast Fourier transforms
65-02 Research monographs (numerical analysis)
65F30 Other matrix algorithms
42A38 Fourier type transforms, one variable
65F50 Sparse matrices

Keywords: research exposition; fast Fourier transform; scientific computations; factorizations of the Fourier matrix; sparse matrices; high-performance computing; radix-2 FFTs; Cooley-Tukey factorization; butterfly computations; bit reversal; Cooley-Tukey algorithm; Stockham autosort algorithm; decimation in time; decimation in frequency; mixed-radix FFTs; split-radix FFT; multidimensional FFTs; vector FFT; parallel FFTs; distributed-memory FFT; shared-memory FFT; prime factor FFT; convolutions; fast trigonometric transforms; fast Poisson solvers

Cited in: Zbl 1203.65292 Zbl 1143.65107 Zbl 0935.65149

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]