On the real complexity of a complex DFT
- Authors: Sergeev I.S.1
-
Affiliations:
- Federal State Unitary Enterprise “Kvant Scientific Research Institute,”
- Issue: Vol 53, No 3 (2017)
- Pages: 284-293
- Section: Large Systems
- URL: https://journal-vniispk.ru/0032-9460/article/view/166429
- DOI: https://doi.org/10.1134/S0032946017030103
- ID: 166429
Cite item
Abstract
We present a method to construct a theoretically fast algorithm for computing the discrete Fourier transform (DFT) of order N = 2n. We show that the DFT of a complex vector of length N is performed with complexity of 3.76875N log2N real operations of addition, subtraction, and scalar multiplication.
About the authors
I. S. Sergeev
Federal State Unitary Enterprise “Kvant Scientific Research Institute,”
Author for correspondence.
Email: isserg@gmail.com
Russian Federation, Moscow
Supplementary files
