Fast Fourier transform: algorithms and applications
type: Item
instance of: scholarly article
title: Fast Fourier transform: algorithms and applications
zbMATH Open document ID: 1203.65292
DOI: 10.1007/978-1-4020-6629-0
author: J. Martínez
published in: Signals and Communication Technology
publication date: 2010-06-25T00:00:00Z
review text: The fast Fourier transform (FFT) is an essential tool in applied mathematics and digital signal processing. Excellent descriptions of the mathematical background of FFT can be found in the books by \textit{C.F.~Van Loan} [Computational frameworks for the fast Fourier transform, Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics (1992; Zbl 0757.65154)] and by \textit{R.~Tolimieri}, \textit{M.~An} and \textit{C. Lu} [Algorithms for discrete Fourier transform and convolution, 2nd ed. New York, NY: Springer (1997; Zbl 0894.65076)]. This monograph on the FFT is mainly written for graduate students and researchers in engineering and science. It consists of 8 chapters, 8 appendices and a comprehensive bibliography. After an extremely short introduction, Chapter 2 describes the properties of the discrete Fourier transform (DFT). Chapter 3 presents different FFTs such as decimation-in-time, decimation-in-frequency, radix-2, radix-3, radix-4, split-radix, and mixed-radix algorithms. The close connection between FFT and sparse factorization of the Fourier matrix is described too. The numerical stability of FFT is not discussed. Chapter 4 is devoted to integer FFT which is an integer approximation of the DFT. The integer FFT can be implemented by using only bit shifts and additions but no multiplications. Corresponding error estimates are missing. Chapter 5 presents properties of the 2- and 3-dimensional DFT and applications to filtering. Fast algorithms for the 2-dimensional DFT are covered in Chapter 6. The nonuniform DFT which is a DFT for nonequally spaced samples or frequencies is introduced in Chapter 7. The corresponding algorithms for the nonuniform DFT are very slow. The authors do not handle efficient algorithms of nonuniform DFT [see \textit{A.~Dutt} and \textit{V.~Rokhlin}, SIAM J.~Sci.~Comput. 14, No.~6, 1368--1393 (1993; Zbl 0791.65108)]. In Chapter 8, the authors sketch numerous applications of FFT in signal and image processing. Here the read…
reviewed by: Manfred Tasche
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 94-02
Mathematics Subject Classification ID: 94A08
Mathematics Subject Classification ID: 94A12
Mathematics Subject Classification ID: 65-02
zbMATH DE Number: 5726192
zbMATH Keywords: monograph
zbMATH Keywords: discrete Fourier transform
zbMATH Keywords: DFT
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: FFT
zbMATH Keywords: sparse matrix factorization
zbMATH Keywords: decimation-in-time
zbMATH Keywords: decimation-in-frequency
zbMATH Keywords: integer FFT
zbMATH Keywords: nonuniform DFT
zbMATH Keywords: image processing
zbMATH Keywords: signal processing
zbMATH Keywords: radix-2 FFT
zbMATH Keywords: radix-3 FFT
zbMATH Keywords: radix-4 FFT
zbMATH Keywords: split-radix FFT
zbMATH Keywords: mixed-radix FFT
zbMATH Keywords: filtering
zbMATH Keywords: flow diagram
zbMATH Keywords: \texttt{MATLAB} programs
zbMATH Keywords: numerical examples
zbMATH Keywords: algorithms
zbMATH Keywords: exercises
describes a project that uses: Matlab
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-1-4020-6629-0
OpenAlex ID: W3147354744
Recommended article: Q4382286
Recommended article: Q4298259
Recommended article: Q3725511
Recommended article: Q5186696
Recommended article: Q4314094
Recommended article: Q5459965
Recommended article: The Fast Fourier Transform
Recommended article: Q4023163
Recommended article: Fast and precise Fourier transforms
Recommended article: On a fast algorithm for computing the Fourier transform
description: scientific article; zbMATH DE number 5726192