Algorithms for discrete Fourier transform and convolution.
[For the first edition (1989) see Zbl 0705.65105.] This book intends to give the theoretical tools for the statement of algorithms for discrete Fourier transform and convolution as well as to serve the ideas of the implementation of the algorithms. Especially, rules and procedures are established, that are required for implementation at parallel and vector machines. The first part of the book is suitable for students of mathematics, electrical engineering and computer science at the graduate level. Moreover, the new unified approach to fast Fourier transform (FFT) algorithms based on factorizations of the Fourier matrix is also very interesting for researchers in this field. The book starts with reviewing some basic algebra. Then the tensor product (Kronecker product) of matrices is introduced and its properties are studied. For two matrices \(A=(a_{ij})_{1\leq i\leq N_1, 1\leq j\leq M_1}\in \mathbb{C}^{ N_1\times M_1}\) and \(B\in \mathbb{C}^{N_2\times M_2}\), the tensor product reads \[ A\otimes B:=(a_{ij}\cdot B)_{1\leq i\leq N_1,1\leq j\leq M_1}\in \mathbb{C}^{(N_1\cdot N_2)\times (M_1\cdot M_2)}. \] Further, so called stride, permutation matrices are discussed. The tensor product of matrices (resp. vectors) and the stride permutations are the basic tools for deriving different kinds of FFT-algorithms. In Chapters 3-5 the Cooley-Tukey-FFT algorithm [cf. \textit{J. W. Cooley} and \textit{J. W. Tukey}, Math. Comput. 19, 297-301 (1965; Zbl 0127.09002)] and many variants of FFT-algorithms and their implementations are studied. The unified approach using tensor products shows the connections and differences between that algorithms by considering the underlying factorizations of the Fourier matrix. Chapters 6 and 7 are devoted to various linear and cyclic convolution algorithms, using especially the Chinese Remainder Theorem. In the following chapters, a more extensive application of multiplicative structure of the index set leads to a further class of algorithms generalizing the Rader transform. So, in Chapter 9, the Winograd Small Fourier transform algorithm is derived. Using the duality between periodic and decimated data established by the Fourier transform, one can also compute the Fourier transform of odd prime power transform sizes efficiently. Finally, introducing the theory of multiplicative characters, corresponding Fourier transform algorithms are obtained. Throughout the book, results are illustrated by suitable examples. Each chapter ends with appropriate references and a list of problems.
- Separation of variables and the computation of Fourier transforms on finite groups. II
- Communications overlapping in fast multipole particle dynamics methods
- Error estimate for a corrected Clenshaw-Curtis quadrature rule
- Fast Fourier-Galerkin methods for first-kind logarithmic-kernel integral equations on open arcs
- A new method for evaluating the distribution of aggregate claims
- A common algebraic description for probabilistic and quantum computations
- Matrix representation of parallel algorithms of the discrete Fourier transform, the discrete ambiguity function and the discrete Cohen distribution
- Generalizing block LU factorization: a lower-upper-lower block triangular decomposition with minimal off-diagonal ranks
- scientific article; zbMATH DE number 3880785 (Why is no real title available?)
- scientific article; zbMATH DE number 3915602 (Why is no real title available?)
- scientific article; zbMATH DE number 3917667 (Why is no real title available?)
- scientific article; zbMATH DE number 44502 (Why is no real title available?)
- Discrete Fourier transform tensors and their ranks
- Separation of variables and the computation of Fourier transforms on finite groups. II
- Automatic derivation and implementation of fast convolution algorithms
- Generalization of the fast Fourier transform with a constant structure
- Indexing in the Good-Thomas fast Fourier transform algorithm
This page was built for publication: Algorithms for discrete Fourier transform and convolution.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4373898)
