NEW ALGORITHMS FOR THE MULTI-DIMENSIONAL DFT.

Title: NEW ALGORITHMS FOR THE MULTI-DIMENSIONAL DFT.
Identifier: AAI8319809
identifier: 8319809
Creator: VULIS, MICHAEL.
Contributor: L. Auslander
Date: 1983
Language: English
Publisher: City University of New York.
Subject: Mathematics
Abstract: In this work we present a new algorithm for the Discrete Fourier Transform on a multi-dimensional data array with p('s) points along each axis, where p is a prime number and s is a positive integer (DFT(p('s):n)). This algorithm is closely connected with algorithms due to S. Winograd for the one-dimensional DFT(p('s):1), described in "Arithmetical Complexity of Computations", CBMS-BSF Regional Conference Series in Applied Math., 1980, and the algorithms due to L. Auslander, E. Feig and S. Winograd for evaluation of DFT(p:n), see "New Algorithms for the Multi-dimensional Discrete Fourier Transform", IBM Research Report. The new algorithm is a generalization of the two mentioned above. While not being minimal, the described algorithm is always close to being minimal and, in fact, becomes minimal for many special cases. This work also contains a block-scheme of the algorithm and detailed example (DFT(9:2)). Some suggestions for computer implementations are also provided.
Type: dissertation
Source: PQT Legacy CUNY.xlsx
degree: Ph.D.
Program: Mathematics