Richard Tolimieri

Fourier transforms of large multidimensional data sets arise in many fields --ranging from seismology to medical imaging. The rapidly increasing power of computer chips, the increased availability of vector and array processors, and the increasing size of the data sets to be analyzed make it both possible and necessary to analyze the data more than one dimension at a time. The increased freedom provided by multidimensional processing, however, also places intesive demands on the communication aspects of the computation, making it difficult to write code that takes all the algorithmic possiblities into account and matches these to the target architecture. This book develops algorithms for multi-dimensional Fourier transforms that yield highly efficient code on a variety of vector and parallel computers. By emphasizing the unified basis for the many approaches to one-dimensional and multidimensional Fourier transforms, this book not only clarifies the fundamental similarities, but also shows how to exploit the differences in optimizing implementations. This book will be of interest not only to applied mathematicians and computer scientists, but also to seismologists, high-energy physicists, crystallographers, and electrical engineers working on signal and image processing. Topics covered include: tensor products and the fast Fourier transform; finite Abelian groups and their Fourier transforms; Cooley- Tukey and Good-Thomas algorithms; lines and planes; reduced transform algorithms; field algorithms; implementation on Risc and parallel

The aim of this work is to present several topics in time-frequency analysis as subjects in abelian group theory. The algebraic point of view pre­ dominates as questions of convergence are not considered. Our approach emphasizes the unifying role played by group structures on the development of theory and algorithms. This book consists of two main parts. The first treats Weyl-Heisenberg representations over finite abelian groups and the second deals with mul­ tirate filter structures over free abelian groups of finite rank. In both, the methods are dimensionless and coordinate-free and apply to one and multidimensional problems. The selection of topics is not motivated by mathematical necessity but rather by simplicity. We could have developed Weyl-Heisenberg theory over free abelian groups of finite rank or more generally developed both topics over locally compact abelian groups. However, except for having to dis­ cuss conditions for convergence, Haar measures, and other standard topics from analysis the underlying structures would essentially be the same. A re­ cent collection of papers [17] provides an excellent review of time-frequency analysis over locally compact abelian groups. A further reason for limiting the scope of generality is that our results can be immediately applied to the design of algorithms and codes for time­ frequency processing.

This book is based on several courses taught during the years 1985-1989 at the City College of the City University of New York and at Fudan Univer­ sity, Shanghai, China, in the summer of 1986. It was originally our intention to present to a mixed audience of electrical engineers, mathematicians and computer scientists at the graduate level a collection of algorithms that would serve to represent the vast array of algorithms designed over the last twenty years for computing the finite Fourier transform (FFT) and finite convolution. However, it was soon apparent that the scope of the course had to be greatly expanded. For researchers interested in the design of new algorithms, a deeper understanding of the basic mathematical concepts underlying algorithm design was essential. At the same time, a large gap remained between the statement of an algorithm and the implementation of the algorithm. The main goal of this text is to describe tools that can serve both of these needs. In fact, it is our belief that certain mathematical ideas provide a natural language and culture for understanding, unifying and implementing a wide range of digital signal processing (DSP) algo­ rithms. This belief is reinforced by the complex and time-consuming effort required to write code for recently available parallel and vector machines. A significant part of this text is devoted to establishing rules and procedures that reduce and at times automate this task.

The Applied and Numerical Harmonic Analysis (ANHA) book series aims to provide the engineering, mathematical, and scienti?c communities with signi?cant devel- ments in harmonic analysis, ranging from abstract harmonic analysis to basic app- cations. The title of the series re?ects the importance of applications and numerical implementation, but richness and relevance of applications and implementation - pend fundamentally on the structure and depth of theoretical underpinnings. Thus, from our point of view, the interleaving of theory and applications and their creative symbiotic evolution is axiomatic. Harmonic analysis is a wellspring of ideas and applicability that has ?ourished, developed, and deepened over time within many disciplines and by means of creative cross-fertilization with diverse areas. The intricate and fundamental relationship - tween harmonic analysis and ?elds such as signal processing, partial differential equations (PDEs), and image processing is re?ected in our state-of-the-art ANHA series. Our vision of modern harmonic analysis includes mathematical areas such as wavelet theory, Banach algebras, classical Fourier analysis, time-frequency analysis, and fractal geometry, as well as the diverse topics that impinge on them.

The aim of this work is to present several topics in time-frequency analysis as subjects in abelian group theory. The algebraic point of view pre­ dominates as questions of convergence are not considered. Our approach emphasizes the unifying role played by group structures on the development of theory and algorithms. This book consists of two main parts. The first treats Weyl-Heisenberg representations over finite abelian groups and the second deals with mul­ tirate filter structures over free abelian groups of finite rank. In both, the methods are dimensionless and coordinate-free and apply to one and multidimensional problems. The selection of topics is not motivated by mathematical necessity but rather by simplicity. We could have developed Weyl-Heisenberg theory over free abelian groups of finite rank or more generally developed both topics over locally compact abelian groups. However, except for having to dis­ cuss conditions for convergence, Haar measures, and other standard topics from analysis the underlying structures would essentially be the same. A re­ cent collection of papers [17] provides an excellent review of time-frequency analysis over locally compact abelian groups. A further reason for limiting the scope of generality is that our results can be immediately applied to the design of algorithms and codes for time­ frequency processing.

This book is based on several courses taught during the years 1985-1989 at the City College of the City University of New York and at Fudan Univer­ sity, Shanghai, China, in the summer of 1986. It was originally our intention to present to a mixed audience of electrical engineers, mathematicians and computer scientists at the graduate level a collection of algorithms that would serve to represent the vast array of algorithms designed over the last twenty years for computing the finite Fourier transform (FFT) and finite convolution. However, it was soon apparent that the scope of the course had to be greatly expanded. For researchers interested in the design of new algorithms, a deeper understanding of the basic mathematical concepts underlying algorithm design was essential. At the same time, a large gap remained between the statement of an algorithm and the implementation of the algorithm. The main goal of this text is to describe tools that can serve both of these needs. In fact, it is our belief that certain mathematical ideas provide a natural language and culture for understanding, unifying and implementing a wide range of digital signal processing (DSP) algo­ rithms. This belief is reinforced by the complex and time-consuming effort required to write code for recently available parallel and vector machines. A significant part of this text is devoted to establishing rules and procedures that reduce and at times automate this task.

Fourier transforms of large multidimensional data sets arise in many fields --ranging from seismology to medical imaging. The rapidly increasing power of computer chips, the increased availability of vector and array processors, and the increasing size of the data sets to be analyzed make it both possible and necessary to analyze the data more than one dimension at a time. The increased freedom provided by multidimensional processing, however, also places intesive demands on the communication aspects of the computation, making it difficult to write code that takes all the algorithmic possiblities into account and matches these to the target architecture. This book develops algorithms for multi-dimensional Fourier transforms that yield highly efficient code on a variety of vector and parallel computers. By emphasizing the unified basis for the many approaches to one-dimensional and multidimensional Fourier transforms, this book not only clarifies the fundamental similarities, but also shows how to exploit the differences in optimizing implementations. This book will be of interest not only to applied mathematicians and computer scientists, but also to seismologists, high-energy physicists, crystallographers, and electrical engineers working on signal and image processing. Topics covered include: tensor products and the fast Fourier transform; finite Abelian groups and their Fourier transforms; Cooley- Tukey and Good-Thomas algorithms; lines and planes; reduced transform algorithms; field algorithms; implementation on Risc and parallel