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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references