Mathematics of Multidimensional Fourier Transform Algorithms

The main emphasis of this book is the development of algorithms for processing multi-dimensional digital signals, and particularly algorithms for multi-dimensional Fourier transforms, in a form that is convenient for writing highly efficient code on a variety of vector and parallel computers.

Contenu

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.4.1 Case M = p, p a prime.- 8.4.2 Case M = p2, p a prime.- 8.4.3 Chart of 2-dimensional pR x pR RTA.- 8.4.4 Case M = pq, p and q distinct primes.- 8.4.5 3-D reduced transform algorithms.- 8.5 RTA Permutations.- Bibliograpgy.- Problems.- 9 Field Algorithm.- 9.1 Introduction.- 9.2 Rader Field Algorithm.- 9.3 Finite Fields.- 9.3.1 Properties of finite fields.- 9.3.2 Examples of finite fields.- 9.4 Fourier Transform of Finite Fields.- 9.4.1 Trace map.- 9.4.2 Evaluation map.- 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.2.1 Implementation on model I RISC.- 10.2.2 Implementation on model II RISC.- 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.3.1 2-Dimensional p x p case, p prime.- 11.4 New Strategy for the Parallel Implementation of FFT.- 11.5 Hybrid Algorithm.- 11.6 A Program Example on iPSC/860.