contents

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