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. The ra...

Full description

Main Authors: Tolimieri, Richard, An, Myoung (Author), Lu, Chao (Author)
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: New York, NY Springer US 1993, 1993
Series:Signal Processing and Digital Filtering
Subjects:
Online Access:
Collection: Springer Book Archives -2004 - Collection details see MPG.ReNa
Table of Contents:
  • 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