zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Computational frameworks for the fast Fourier transform. (English) Zbl 0757.65154
Frontiers in Applied Mathematics. 10. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. xiii, 273 p. (1992).

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.

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.

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.

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).

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.

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.


MSC:
65T50Discrete and fast Fourier transforms (numerical methods)
65-02Research monographs (numerical analysis)
65F30Other matrix algorithms
42A38Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type
65F50Sparse matrices (numerical linear algebra)
Software:
Matlab