快速傅里叶变换的计算框架

Preface ix

Preliminary Remarks xi

1 The Radix-2 Frameworks

1.1 Matrix Notation and Algorithms 2

1.2 The FFT Idea 11

1.3 The Cooley-Tukey Radix-2 Factorizstion 17

1.4 Weight and Butterfly Computations 22

1.5 Bit Reversal and Transposition 36

1.6 The Cooley-Tukey Framework 44

1.7 The Stockham Autosort Frameworks 49

1.8 The Pease Framework 60

1.9 Decimation in Frequency and Inverse FFTs 64

2 General Radix Frameworks

2.1 General Radix Ideas 76

2.2 Index Reversal and Transposition 84

2.3 Mixed-Radix Factorizations 95

2.4 Radix-4 and Radix-8 Frameworks I01

2.5 The Spllt-Radix Framework III

3 High-Performance Frameworks

3.1 The Multiple OFT Problem 122

3.2 Matrix Transposition 125

3.3 The Large Single-Vector FFT Problem 139

3.4 The Multidimensional FFT Problem 148

3.5 Distributed-Memory FFTs 156

3.6 Shared-Memory FFTs 176

4 Selected Topics

4.1 Prime Factor Frameworks 188

4.2 Convolution 205

4.3 FFTs of Real Data 215

4.4 Fast Trigonometric Transforms 229

4.5 Fast Poisson Solvers 247

Bibliography 259

Index 269

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 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. he uses a stylized matlab
notation, which is familiar to those engaged in high-performance
computing.
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.