Author	Tolimieri, Richard. author
Title	Mathematics of Multidimensional Fourier Transform Algorithms [electronic resource] / by Richard Tolimieri, Myoung An, Chao Lu
Imprint	New York, NY : Springer US, 1993
Connect to	http://dx.doi.org/10.1007/978-1-4684-0205-6
Descript	XIV, 233 p. online resource

The Fourier transform of large multidimensional data sets is an essenยญ tial computation in many scientific and engineering fields, including seismology, X-ray crystallography, radar, sonar and medical imaging. Such fields require multidimensional arrays for complete and faithful modelling. Classically, a set of data is processed one dimension at a time, permitting control over the size of the computation and calling on well-established I-dimensional programs. The rapidly increasing availability of powerful computing chips, vector processors, multinode boards and parallel machines has provided new tools for carrying out multidimensional computations. Multidimensional processing offers a wider range of possible implementations as compared to I-dimensional the greater flexibility of movement in the data inยญ processing, due to dexing set. This increased freedom, along with the massive size data sets typically found in multidimensional applications, places intensive demands on the communication aspects of the computation. The writยญ ing of code that takes into account all the algorithmic possibilities and matches these possibilities to the communication capabilities of the tarยญ get architecture is an extremely time-consuming task. A major goal of this text is to provide a sufficiently abstra

1 Tensor Product -- 1.1 Introduction -- 1.2 Tensor Product -- 1.3 Stride Permutations -- 1.4 Algebra of Stride Permutations -- 1.5 Tensor Product Factorization -- 1.6 Fast Fourier Transform Algorithms I -- 1.7 General 1-Dimensional FFT -- Problems -- 2 Multidimensional Tensor Product and FFT -- 2.1 Introduction -- 2.2 Multidimensional Fourier Transform -- 2.3 2-Dimensional Operations -- 2.4 2-Dimensional Cooley-Tukey FFT -- Problems -- 3 Finite Abelian Groups -- 3.1 Introduction -- 3.2 Character Group -- 3.3 Duality -- 3.4 Chinese Remainder Theorem -- 3.5 Vector Space L(A) -- Problems -- 4 Fourier Transform of Finite Abelian Groups -- 4.1 Introduction -- 4.2 Fourier Transform of A -- 4.3 Induced Fourier Transform -- 4.4 Periodic and Decimated Data -- 4.5 Periodization and Decimation -- 5 CooleyโTukey and GoodโThomas -- 5.1 Introduction -- 5.2 Good-Thomas FFT -- 5.3 Abstract Cooley-Tukey FFT -- 6 Lines -- 6.1 Introduction -- 6.2 Examples -- 6.3 Prime Case -- 6.4 Prime Power Case -- 6.5 Square Case -- 6.6 Rectangular Case -- Problems -- 7 Duality of Lines and Planes -- 7.1 Automorphism Group -- 7.2 Dual of Lines -- 7.3 Planes and Duality -- Problems -- 8 Reduced Transform Algorithms -- 8.1 Introduction -- 8.2 General Structure -- 8.3 Periodizations -- 8.4 Examples -- 8.5 RTA Permutations -- Bibliograpgy -- Problems -- 9 Field Algorithm -- 9.1 Introduction -- 9.2 Rader Field Algorithm -- 9.3 Finite Fields -- 9.4 Fourier Transform of Finite Fields -- 9.5 Factorization of Core Matrices -- 9.6 Auslander-Feig-Winograd DFT -- Bibliograpgy -- Problems -- 10 Implementation on RISC Architectures -- 10.1 Introduction -- 10.2 Algorithm Design for RISC Architectures -- 10.3 Implementation on the IBM RS/6000 -- 10.4 Implementation on the Intel i860 -- 11 Implementation on Parallel Architectures -- 11.1 Introduction -- 11.2 Parallel Implementation of FFT -- 11.3 Parallel Implementation of the RTA -- 11.4 New Strategy for the Parallel Implementation of FFT -- 11.5 Hybrid Algorithm -- 11.6 A Program Example on iPSC/860

1. Engineering
2. Algorithms
3. Electrical engineering
4. Engineering
5. Communications Engineering
6. Networks
7. Algorithm Analysis and Problem Complexity