A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing (Q1338818): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q56235046, #quickstatements; #temporary_batch_1707216511891 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56235046 / rank | |||
Normal rank |
Revision as of 12:42, 6 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing |
scientific article |
Statements
A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing (English)
0 references
21 November 1994
0 references
The paper presents a unifying framework for fast Fourier transform algorithms which includes most of the known implementations and also a new version, which is especially suitable for vector and parallel processing. Advantages of the new variant are that it is in-place, it is naturally self-sorting and accesses data only with stride one. Moreover, it is efficient: the number of operations is bounded by the operation count for the traditional radix 2 algorithms. It is based on mixed-radix representation of integers and permutations of the ``digits'' in such a representation. The latter can be interpreted in terms of Kronecker products. A special section is devoted to this topic. An FFT algorithm can be described as a matrix multiplication. The algorithms presented here are also discussed in terms of factorizations of these matrices. The paper is quite self-contained with ample referencing to the literature. The algorithms are detailed up to a pseudo code level.
0 references
matrix factorization
0 references
fast Fourier transform algorithms
0 references
parallel processing
0 references
mixed-radix representation
0 references
matrix multiplication
0 references