go-v.orgdoi

Efficient Synthesis and Implementation of Large Discrete Fourier Transformations

S.D. Morgera · SIAM Journal on Computing · 1980

  • DOI 10.1137/0209023
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 1980

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

SIAM Journal on Computing · Society for Industrial and Applied Mathematics · article · 1980

Abstract

A systematic technique is presented for synthesizing and efficiently performing large discrete Fourier transformations (DFT’s) in the range from 60 to 5000 points. The technique is termed the mutual prime factor cyclic algorithm (MPFCA). The mutual prime factor portion of the algorithm is attributed originally to L. H. Thomas, with generalization supplied by I. J. Good; the cyclic aspect of the algorithm has recently been formalized by S. Winograd. Three methods are described for implementing the MPFCA; computational complexity (multiplications and additions) is estimated for each method and compared with the fast Fourier transform (FFT).

For special purpose hardware, the MPFCA is at least twice as efficient as the FFT. A major result of importance is the realization that the three considerably different implementation methods presented lead to rather similar multiplication complexities for large size DFT’s; furthermore, the resulting multiplication complexity is considerably higher than that achieved for small size DFT’s. It is felt that further substantial improvements for large size DFT’s built up using mutually prime factors will require more general theoretical results in addition to long, tedious hours spent with computer based formula manipulation systems.

Open the resolved locator · 10.1137/0209023

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 06:57 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0209023
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.