Computational Frameworks for the Fast Fourier Transform (Frontiers in Applied Mathematics)

✍ Scribed by Charles Van Loan

• Year: 1987
• Tongue: English
• Leaves: 291
• Category: Library

✦ Synopsis

The most comprehensive treatment of FFTs to date. Van Loan captures the interplay between mathematics and the design of effective numerical algorithms--a critical connection as more advanced machines become available. A stylized Matlab notation, which is familiar to those engaged in high-performance computing, is used. The Fast Fourier Transform (FFT) family of algorithms has revolutionized many areas of scientific computation. The FFT is one of the most widely used algorithms in science and engineering, with applications in almost every discipline. This volume is essential for professionals interested in linear algebra as well as those working with numerical methods. The FFT is also a great vehicle for teaching key aspects of scientific computing.

✦ Table of Contents

Cover
......Page 1
Kronecker Product Properties......Page 2
Front Matter......Page 3
Frontiers in Applied Mathematics
......Page 4
Title......Page 7
Table of Contents......Page 11
Preface......Page 13
Preliminary Remarks......Page 15
1. The Radix-2 Frameworks......Page 19
1.1 Matrix Notation and Algorithms
......Page 20
1.2 The FFT Idea......Page 29
1.3 The Cooley-Tukey Radix-2 Factorization
......Page 35
1.4 Weight and Butterfly Computations......Page 40
1.5 Bit Reversal and Transposition......Page 54
1.6 The Cooley-Tukey Framework......Page 62
1.7 The Stockham Autosort Frameworks......Page 67
1.8 The Pease Framework......Page 78
1.9 Decimation in Frequency and Inverse FFTs......Page 82
2.1 General Radix Ideas......Page 94
2.2 Index Reversal and Transposition......Page 102
2.3 Mixed-Radix Factorizations......Page 113
2.4 Radix-4 and Radix-8 Frameworks......Page 119
2.5 The Split-Radix Framework......Page 129
3. High-Performance Frameworks......Page 139
3.1 The Multiple DFT Problem......Page 140
3.2 Matrix Transposition......Page 143
3.3 The Large Single-Vector FFT Problem......Page 157
3.4 The Multidimensional FFT Problem......Page 166
3.5 Distributed-Memory FFTs......Page 174
3.6 Shared-Memory FFTs......Page 194
4.1 Prime Factor Frameworks......Page 206
4.2 Convolution......Page 223
4.3 FFTs of Real Data......Page 233
4.4 Fast Trigonometric Transforms......Page 247
4.5 Fast Poisson Solvers......Page 265
Bibliography
......Page 277
Index......Page 287