The DOI matches its Crossref record; 44 of the 45 references it cites were found in a registry or an index.
A Modified Split-Radix FFT With Fewer Arithmetic Operations
Abstract
Recent results by Van Buskirk have broken the record set by Yavne in 1968 for the lowest exact count of real additions and multiplications to compute a power-of-two discrete Fourier transform (DFT). Here, we present a simple recursive modification of the split-radix algorithm that computes the DFT with asymptotically about 6% fewer operations than Yavne, matching the count achieved by Van Buskirk's program-generation framework. We also discuss the application of our algorithm to real-data and real-symmetric (discrete cosine) transforms, where we are again able to achieve lower arithmetic counts than previously published algorithms
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Therefore, unlike the case of the DFT that can be self-factored to obtain FFT algorithms [19,20,21], we are generally unable to factorize the DVM to obtain a self-contained and radix-2 factorization, leading to an FFT-like algorithm.”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [21]
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
The Design and Implementation of FFTW3
Frigo, M., & Johnson, S. G. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840301 · Cited by 5,086
Self-citationThe On-Line Encyclopedia of Integer Sequences
Sloane, N. J. A. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73086-6_12 · Cited by 3,348
JPEG: Still Image Data Compression Standard
Pennebaker, W. B., & Mitchell, J. L. (1992) · Medical Entomology and Zoology · Cited by 2,351
Discrete Cosine Transform: Algorithms, Advantages, Applications
Rao, K. R., Yip, P. C. Y., & Britaňák, V. (1990) · Cited by 1,873
JPEG: Still image data compression standard
Sebestyen, I. (1993) · Computer Standards & Interfaces · doi:10.1016/0920-5489(93)90038-s · Cited by 1,772
Computational Frameworks for the Fast Fourier Transform
Loan, C. F. V. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970999 · Cited by 1,292
Fast fourier transforms: A tutorial review and a state of the art
Duhamel, P., & Vetterli, M. (1990) · Signal Processing · doi:10.1016/0165-1684(90)90158-u · Cited by 1,155
Signal processing with lapped transforms
Malvar, H. S. (1992) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,025
SPIRAL: Code Generation for DSP Transforms
Puschel, M., Moura, J. M. F., Johnson, J. R., Padua, D., Veloso, M. M., Singer, B. W., Xiong, J., Franchetti, F., Gacic, A., Voronenko, Y., et al. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840306 · Cited by 826
On computing the discrete Fourier transform
Winograd, S. (1978) · Mathematics of Computation · doi:10.1090/s0025-5718-1978-0468306-4 · Cited by 613
Gentleman, W. M., & Sande, G. (1966) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1464291.1464352 · Cited by 545
Real-valued fast Fourier transform algorithms
Sorensen, H., Jones, D., Heideman, M., & Burrus, C. (1987) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1987.1165220 · Cited by 500
A fast Fourier transform compiler
Frigo, M. (1999) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/301618.301661 · Cited by 445
Self-citationDuhamel, P., & Hollmann, H. D. L. (1984) · Electronics Letters · doi:10.1049/el:19840012 · Cited by 425
Vasconcelos, W. V. (1998) · Algorithms and computation in mathematics · doi:10.1007/978-3-642-58951-5_2 · Cited by 406
A Fast DCT-SQ Scheme for Images
Arai, Y., Agui, T., & Nakajima, M. (1988) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · Cited by 360
Simple FFT and DCT algorithms with reduced number of operations
Vetterli, M., Eurasip, M., & Nussbaumer, H. J. (1984) · Signal Processing · doi:10.1016/0165-1684(84)90059-8 · Cited by 334
The On-Line Encyclopedia of Integer Sequences
Finch, S. R. (2021) · The Mathematical Intelligencer · doi:10.1007/s00283-021-10060-2 · Cited by 301
On Computing the Discrete Fourier Transform
Winograd, S. (1978) · Mathematics of Computation · doi:10.2307/2006266 · Cited by 280
Implementation of "Split-radix" FFT algorithms for complex, real, and real-symmetric data
Duhamel, P. (1986) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1986.1164811 · Cited by 268
On computing the split-radix FFT
Sorensen, H. V., Heideman, M. T., & Burrus, C. S. (1986) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1986.1164804 · Cited by 233
Analysis of linear digital networks
Crochiere, R. E., & Oppenheim, A. V. (1975) · Proceedings of the IEEE · doi:10.1109/proc.1975.9793 · Cited by 201
A new principle for fast Fourier transformation
Rader, C. M., & Brenner, N. (1976) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1976.1162805 · Cited by 155
An economical method for calculating the discrete Fourier transform
Yavne, R. (1968) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1476589.1476610 · Cited by 113
Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
Morgenstern, J. (1973) · Journal of the ACM · doi:10.1145/321752.321761 · Cited by 108
Accuracy of the Discrete Fourier Transform and the Fast Fourier Transform
Schatzman, J. C. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827593247023 · Cited by 108
Fast and numerically stable algorithms for discrete cosine transforms
Plonka, G., & Tasche, M. (2004) · Linear Algebra and its Applications · doi:10.1016/j.laa.2004.07.015 · Cited by 85
Recursive cyclotomic factorization--A new algorithm for calculating the discrete Fourier transform
Martens, J. B. O. S. (1984) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1984.1164395 · Cited by 69
On the number of multiplications necessary to compute a length-2nDFT
Heideman, M. T., & Burrus, C. S. (1986) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1986.1164785 · Cited by 64
A New Radix- $2/8$ FFT Algorithm for Length- $qtimes 2^m$ DFTs
Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2004) · IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications · doi:10.1109/tcsi.2004.834508 · Cited by 48
A new matrix approach to real FFTs and convolutions of length 2 k
Lundy, T., & Buskirk, J. V. (2007) · Computing · doi:10.1007/s00607-007-0222-6 · Cited by 47
Duhamel, P. (1990) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/29.60070 · Cited by 45
Optimality of the Fast Fourier transform
Papadimitriou, C. H. (1979) · Journal of the ACM · doi:10.1145/322108.322118 · Cited by 35
Conjugate pair fast Fourier transform
Kamar, I., & Elcherif, Y. (1989) · Electronics Letters · doi:10.1049/el:19890225 · Cited by 27
Comment: Conjugate pair fast Fourier transform
Krot, A. M., & Minervina, H. B. (1992) · Electronics Letters · doi:10.1049/el:19920721 · Cited by 16
Improved Roundoff Error Analysis for Precomputed Twiddle Factors
Tasche, M., & Zeuner, H. (2002) · Journal of Computational Analysis and Applications · doi:10.1023/a:1012991330474 · Cited by 13
Pan, V. Y. (1986) · Information Processing Letters · doi:10.1016/0020-0190(86)90035-9 · Cited by 12
Comment: Conjugate pair fast Fourier transform
Qian, H., & Zhao, Z.-J. (1990) · Electronics Letters · doi:10.1049/el:19900351 · Cited by 11
Testing multivariate linear functions
Ergün, F. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225167 · Cited by 11
Modified FFTs for fused multiply-add architectures
Linzer, E., & Feig, E. (1993) · Mathematics of Computation · doi:10.1090/s0025-5718-1993-1159169-0 · Cited by 10
Conjugate pair fast Fourier tranform
Gopinath, R. (1989) · Electronics Letters · doi:10.1049/el:19890725 · Cited by 10
Modified FFTs for Fused Multiply-Add Architectures
Linzer, E., & Feig, E. (1993) · Mathematics of Computation · doi:10.2307/2153172 · Cited by 4
Research works printed but not linked: 4
- van buskirk, 2004, Usenet posts
- knuth, 1998, Seminumerical Algorithms, 2
- plonka, 0, Split-radix algorithms for discrete trigonometric transforms
- volynets, 1993, algorithms of the hartley fast transformation with conjugate pairs, Radioelectron Comm Syst, 36, 57
Cited by
Sorted by citations
Fast Algorithms for Signal Processing
Blahut, R. E. (2010) · doi:10.1017/cbo9780511760921 · Cited by 274
TOWARD EARLY-WARNING DETECTION OF GRAVITATIONAL WAVES FROM COMPACT BINARY COALESCENCE
Cannon, K. C., Cariou, R., Chapman, A., Crispin‐Ortuzar, M., Fotopoulos, N., Frei, M., Hanna, C., Kara, E., Keppel, D., Liao, L., et al. (2012) · The Astrophysical Journal · doi:10.1088/0004-637x/748/2/136 · Cited by 261
Fürer, M. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250800 · Cited by 246
Arts, L. P. A., & van den Broek, E. L. (2022) · Nature Computational Science · doi:10.1038/s43588-021-00183-z · Cited by 238
Fürer, M. (2009) · SIAM Journal on Computing · doi:10.1137/070711761 · Cited by 217
Metadata
- Authors
- Johnson, S. G., & Frigo, M.
- Affiliations
- Massachusetts Institute of Technology (US)
- IBM Research - Austin (US)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2007-01
- Volume
- 55
- Issue
- 1
- Pages
- 111-119
- ISSN
- 1053-587X (ISSN-L)
- OpenAlex
- W2135031801
- Cited by
- 380
- References
- 45
- Citations by year
- 2026: 4 · 2025: 14 · 2024: 18 · 2023: 13 · 2022: 23 · 2021: 26 · 2020: 27 · 2019: 15 · 2018: 16 · 2017: 12 · 2016: 19 · 2015: 24 · 2014: 26 · 2013: 19 · 2012: 20
- FWCI
- 27.97
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Signal Processing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Digital Filter Design and Implementation
- Physical Sciences › Mathematics › Applied Mathematics › Mathematical Analysis and Transform Methods
- Physical Sciences › Engineering › Electrical and Electronic Engineering › Advanced Electrical Measurement Techniques
- Keywords
- split-radix FFT, discrete Fourier transform, recursive algorithm, discrete cosine transform, algorithm optimization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
