|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Loan C. — Computational Frameworks for the Fast Fourier Transform (Frontiers in Applied Mathematics) |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
Array interpretation, bit reversal 42—43
Array interpretation, Cooley — Tukey 46—48
Array interpretation, index reversal 88—90
Array interpretation, radix-p butterfly 82
Array interpretation, transposed Stockham framework 53
Array/vector duality 5—6
Barrier construct 178—179
Bit reversal of index 39
Bit reversal via even-odd sort 42
Bit reversal via perfect shuffles 41
Bit reversal, distributed-memory 162—165
Bit reversal, permutation 39
Block matrices 5
Blocking permutation 192
Bluestein chirp-z algorithm 210
Boundary conditions, Dirichlet 249—250
Boundary conditions, Dirichlet — Neumann 250—251
Boundary conditions, Neumann-Neumann 252
Boundary conditions, periodic 253
Butterfly, conjugate even 218ff
Butterfly, Cooley — Tukey, definition of 70
Butterfly, Cooley — Tukey, radix-2 setting 28—30
Butterfly, Cooley — Tukey, s-processor 160—162
Butterfly, Cooley — Tukey, two-processor 158
Butterfly, Gentleman — Sande, definition of 71
Butterfly, Gentleman — Sande, two-processor 169
Butterfly, Hartley 225
Butterfly, matrix 18
Butterfly, radix-2 18
Butterfly, radix-8 107—109
Butterfly, radix-p 79
Butterfly, split-radix 113
Butterfly, vectorization of 34
Cache, definition 127
Cache, line 128
Cache, miss 129
Chinese remainder theorem mapping 192
Circulant matrices, properties 206—207
Colon notation 4
Column partitioning 4
Communication overhead 159—160
Complex arithmetic, flops and 9
Complex arithmetic, three-multiply version 10
Computation tree, mixed-radix 82
Computation tree, radix-2 13—14
Computation tree, split-radix 114
Computation tree, symmetric FFT 244
Conjugate even, butterfly 218
Conjugate even, DFTs 222—223
Conjugate even, vectors, data structure 216ff 234
Conjugate odd vectors 234
Convolution 205ff
Convolution, FFTs and 207—208
Convolution, two-dimensional 212—214
Cooley — Tukey, combine phase 21
Cooley — Tukey, distributed-memory 165—168
Cooley — Tukey, mixed-radix 95—98
Cooley — Tukey, multiple DFTs and 123
Cooley — Tukey, permutation phase 21
Cooley — Tukey, radix-2, discussion of 44ff
Cooley — Tukey, radix-2, flop analysis 45—46
Correlation 214
Cosine matrix, definition 230
Cosine matrix, scaled 232
Cosine transform (discrete), definition 229
Cosine transform (discrete), inverse of 240
Cosine transform (discrete), matrix specification 230 231 238—239
Cosine transform-II (discrete), definition 229
Cosine transform-II (discrete), inverse of 243
Cosine transform-II (discrete), matrix specification 230 233 242—243
Data motion overheads, shared-memory 177
Data re-use, radix and 109—110
Decimation in frequency 68
Decimation in frequency for real data 223
Decimation in time (DIT) 67
Diagonal scaling 7
Dirichlet boundary conditions 249—250
Dirichlet — Neumann boundary conditions 250—251
Discrete cosine transform (DCT) 238ff
Discrete cosine transform-II (DCT-II) 242ff
Discrete Fourier Transform (DFT) of structured vectors 234
Discrete Fourier Transform (DFT), definition 2
Discrete Fourier transform (DFT), matrix 3
Discrete sine transform (DST) 236ff
Discrete sine transform-II (DST-II) 240ff
Downshift permutation 206
Dynamic scheduling 186
Edson factorization 220
Edson real-data FFT 220ff
Even-odd sort permutation 12
Exchange matrix 215
Factorizations, Bluestein chirp-z 209—210
Factorizations, Cooley — Tukey (mixed-radix) 96—98
Factorizations, Cooley — Tukey (radix-2) 17ff
Factorizations, decimation in frequency (DIF) 64—65
Factorizations, Edson 220
Factorizations, Hartley 225
Factorizations, Pease (mixed-radix) 96 99—100
Factorizations, Pease (radix-2) 62—63
Factorizations, prime factor 196
Factorizations, Rader 211
Factorizations, rotated DFT 198—201
Factorizations, split radix 116
Factorizations, Stockham (mixed-radix) 96 100—101
Factorizations, Stockham (radix-2) 55
Factorizations, transposed Stockham (mixed-radix) 96 98
Factorizations, transposed Stockham (radix-2) 50—51
Factorizations, Winograd 201—202
Fast Fourier Transform Frameworks, (DIF) Cooley — Tukey 67
Fast Fourier Transform Frameworks, (DIF) Pease 68
Fast Fourier Transform Frameworks, (DIF) Stockham 69
Fast Fourier Transform Frameworks, (DIF) transposed Stockham 69
Fast Fourier Transform Frameworks, blocked four-step 144
Fast Fourier Transform Frameworks, blocked six-step 143
Fast Fourier Transform Frameworks, Bluestein chirp-z 210
Fast Fourier Transform Frameworks, Cooley — Tukey radix-2, in-place 44
Fast Fourier Transform Frameworks, Cooley — Tukey radix-2, unit stride 45
Fast Fourier Transform Frameworks, Cooley — Tukey radix-4 104
Fast Fourier Transform Frameworks, d-dimensional 152—154
Fast Fourier Transform Frameworks, distributed-memory 167
Fast Fourier Transform Frameworks, external memory 133—134
Fast Fourier Transform Frameworks, four-step 140
Fast Fourier Transform Frameworks, general radix 81
Fast Fourier Transform Frameworks, Pease radix-2 62
Fast Fourier Transform Frameworks, prime factor 195—196
Fast Fourier Transform Frameworks, Rader 212
Fast Fourier Transform Frameworks, rotated prime-factor 201
Fast Fourier Transform Frameworks, shared memory 180—181
Fast Fourier Transform Frameworks, six-step 140
Fast Fourier Transform Frameworks, split-radix 115 118
Fast Fourier Transform Frameworks, Stockham radix-2 56—57
Fast Fourier Transform Frameworks, Stockham radix-4 106
Fast Fourier Transform Frameworks, Stockham vector radix 149
Fast Fourier Transform Frameworks, three-dimensional transform 151
Fast Fourier Transform Frameworks, transposed Stockham radix-2 52
Fast Fourier Transform Frameworks, Winograd 201—202
Fast Fourier Transform, main idea of 11ff
Fast Poisson solvers 256—257
FLOP 9
Four-step framework, blocked 144
Four-step framework, distributed memory 173
Four-step framework, read data 224
Four-step framework, shared memory 184
Fraser transpose 133—138
General radix framework, ideas behind 76ff
General radix framework, recursive specification 81
Gentleman — Sande butterfly 66
Gentleman — Sande framework 67
Gentleman — Sande idea 65—66
Givens rotations 24—25
| Hankel matrix 214
Hartley butterfly 225
Hartley factorization 225
Hartley transform 224ff
Hartley transform framework 227
History of the FFT xi—xii 16
In-place approach 44
Index-reversal, algorithm for 91
Index-reversal, array interpretation 88—90
Index-reversal, example 91
Index-reversal, permutation 87
Index-reversal, symmetry and 92
Intermediate DFTs, notion of 15
Intermediate DFTs, Stockham setting 49
Intermediate DFTs, storage schemes 95
Inverse FFT framework 64 69ff
Inverse real periodic transform, computation of 235—236
Inverse real periodic transform, definition 229
Kron1 7
Kron11 85
Kron12 86
Kron2 7
Kron3 8
Kron4 8
Kron5 8
Kron6 8
Kron7 8
Kron8 84
Kron9 84
Kronecker product definition 7
Kronecker product definition, properties 84—86
Long weight vector 34—35
Loop re-ordering 28—30 122—125
Matlab notation 9
Matrices, bit-reversal 20—21
Matrices, block 5
Matrices, butterfly 18
Matrices, complex-symmetric 3
Matrices, conjugate even butterfly 218
Matrices, cosine 230
Matrices, diagonal 7
Matrices, discrete Fourier transform 3
Matrices, even-odd sort permutation 12 39ff
Matrices, Hartley butterfly 225
Matrices, index-reversal permutation 87
Matrices, intermediate DFT 15
Matrices, mod p sort permutation 77
Matrices, orthogonal 3
Matrices, perfect shuffle 40ff
Matrices, permutation 6
Matrices, radix-p butterfly 79
Matrices, sine 230
Matrices, split radix butterfly 113
Matrices, symmetric 3
Matrices, unitary 3
Matrix, conjugate 2
Matrix, conjugate transpose 3
Matrix, transpose 2
Memory bank conflict in transposition 126
Memory bank conflict, illustration of 32
Memory references 42
Message identifier 157
Mixed-radix factorizations, Cooley — Tukey 97—98
Mixed-radix factorizations, Pease 99—100
Mixed-radix factorizations, Stockham 100—101
Mixed-radix factorizations, summary 96
Mixed-radix factorizations, transposed Stockham 98
Mixed-radix framework 82
Mixed-radix ideas 95ff
mod p, perfect shuffle 78
mod p, sort 77—78
Multidimensional, DFT 148
Multidimensional, FFT 152—154
Multiple transforms, approaches to 122ff
Multiple transforms, blocking 141
Multiple transforms, general radix setting and 81
Multiple transforms, multicolumn, definition of 122
Multiple transforms, multirow with small buffer 145
Multiple transforms, multirow, definition of 122
Multiple transforms, shared-memory 177—178
Neumann — Neumann boundary conditions 252—253
Node program 156
Notation, colon 4
Notation, submatrix designation 4
Pease FFT, mixed-radix 95—96 99—100
Pease FFT, radix-2 60ff
Perfect shuffle, definition 40—41
Perfect shuffle, mod p 78
Perfect shuffle, Stockham context 51—52
Periodic boundary conditions 253
Permutation by cycles 92—93
Permutations, bit reversal 36—39
Permutations, definition of 6
Permutations, downshift 206
Permutations, exchange 215
Permutations, index-reversal 87
Permutations, reflection matrix 215
Pipelining 32
Pointwise multiplication 7
Poisson equation on rectangle 254
Poisson equation, one-dimensional 247
Pool-of-task paradigm 184—186
Prime factor, algorithm 195—196
Prime factor, splitting 195
Primitive root 210
Quarter-wave even vectors 234
Quarter-wave odd vectors 234
Rader FFT 212
Radix, re-use of data and 109—110
Radix-2, computation tree 13—14
Radix-2, recursive specification 16
Radix-4, butterfly 102—104
Radix-4, Cooley — Tukey framework 104
Radix-4, Stockham framework 106
Radix-p 82
Radix-p splitting 78—79
Read/write overheads 177
Real arithmetic 32—33
Real data FFTs, autosort frameworks 221—222
Real data FFTs, discussion of 215ff
Real even vectors 234
Real odd vectors 234
Recursive algorithms, general radix 81
Recursive algorithms, radix-2 16
Recursive algorithms, split-radix 115
Recursive algorithms, symmetric FFT 245
recv 157
Reflection matrix 215
Relative primality 189—191
Ring 156
Rotated DFTs 197—201
Row partitioning 4
Ruritanian mapping 194—195
Scheduling dynamic 186
send 157
Shared-memory system 176
Signal flow graph 70
Sine matrix, definition 230
Sine matrix, scaled 232
Sine transform (discrete), definition 229
Sine transform (discrete), inverse of 240
Sine transform (discrete), matrix specification 230 231 236—238
Sine transform-II (discrete), definition 229
Sine transform-II (discrete), inverse of 241—242
Sine transform-II (discrete), matrix specification 230 233 240—241
Sine/cosine blocking 231
Six-point DFT 202—204
Six-step framework, blocked 143
Six-step framework, definition of 140
Six-step framework, distributed-memory 173
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå