The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
FFTW: an adaptive software architecture for the FFT
Abstract
FFT literature has been mostly concerned with minimizing the number of floating-point operations performed by an algorithm. Unfortunately, on present-day microprocessors this measure is far less important than it used to be, and interactions with the processor pipeline and the memory hierarchy have a larger impact on performance. Consequently, one must know the details of a computer architecture in order to design a fast algorithm. In this paper, we propose an adaptive FFT program that tunes the computation automatically for any particular hardware. We compared our program, called FFTW, with over 40 implementations of the FFT on 7 machines. Our tests show that FFTW's self-optimizing approach usually yields significantly better performance than all other publicly available software. FFTW also compares favorably with machine-specific, vendor-optimized libraries.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Numerical recipes in C: the art of scientific computing
(1993) · Choice Reviews Online · doi:10.5860/choice.30-5638 · Cited by 17,933
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
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
Discrete-Time Signal Processing
Oppenheim, A. V., & Schafer, R. W. (1989) · Cited by 12,572
Numerical recipes in Pascal: the art of scientific computing
(1990) · Choice Reviews Online · doi:10.5860/choice.27-5158 · Cited by 11,811
Numerical recipes in Fortran (The art of scientific computing)
Ames, W. F., & Brezinski, C. (1993) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(93)90043-t · Cited by 4,304
Computational Frameworks for the Fast Fourier Transform
Van Loan, C. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970999 · Cited by 1,283
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,143
Cilk: an efficient multithreaded runtime system
Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H., & Zhou, Y. (1995) · Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/209936.209958 · Cited by 1,021
Cilk: An Efficient Multithreaded Runtime System
Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H., & Zhou, Y. (1996) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1996.0107 · Cited by 784
An algorithm for computing the mixed radix fast Fourier transform
Singleton, R. (1969) · IEEE Transactions on Audio and Electroacoustics · doi:10.1109/tau.1969.1162042 · Cited by 539
Discrete Fourier transforms when the number of data samples is prime
Rader, C. M. (1968) · Proceedings of the IEEE · doi:10.1109/proc.1968.6477 · Cited by 535
On computing the split-radix FFT
Sorensen, H., Heideman, M., & Burrus, C. (1986) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1986.1164804 · Cited by 233
FFT algorithms for vector computers
Swarztrauber, P. N. (1984) · Parallel Computing · doi:10.1016/s0167-8191(84)90413-7 · Cited by 179
Swarztrauber, P. N. (1982) · Elsevier eBooks · doi:10.1016/b978-0-12-592101-5.50007-5 · Cited by 135
An analysis of dag-consistent distributed shared-memory algorithms
Blumofe, R. D., Frigo, M., Joerg, C. F., Leiserson, C. E., & Randall, K. H. (1996) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/237502.237574 · Cited by 115
Self-citationThe design of optimal DFT algorithms using dynamic programming
Johnson, H., & Burrus, C. S. (1983) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1983.1164071 · Cited by 41
Automatic generation of prime length FFT programs
Selesnick, I., & Burrus, C. S. (1996) · IEEE Transactions on Signal Processing · doi:10.1109/78.482008 · Cited by 31
A Framework for Generating Distributed-Memory Parallel Programs for Block Recursive Algorithms
Gupta, S. K. S., Huang, C., Sadayappan, P., & Johnson, R. W. (1996) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1996.0051 · Cited by 26
A Framework for Generating Distributed-Memory Parallel Programs for Block Recursive Algorithms
SadayappanP. (1996) · Journal of Parallel and Distributed Computing · doi:10.5555/229306.229308 · Cited by 12
Cited by
GROMACS: Fast, flexible, and free
Van Der Spoel, D., Lindahl, E., Hess, B., Groenhof, G., Mark, A. E., & Berendsen, H. J. C. (2005) · Journal of Computational Chemistry · doi:10.1002/jcc.20291 · Cited by 19,182
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
“Previous work on adaptive systems includes [3]–[11].”
BackgroundInfluentialSelf-citationBlock-iterative frequency-domain methods for Maxwell's equations in a planewave basis
Johnson, S., & Joannopoulos, J. (2001) · Optics Express · doi:10.1364/oe.8.000173 · Cited by 3,217
Self-citationA Survey of General‐Purpose Computation on Graphics Hardware
Owens, J. D., Luebke, D., Govindaraju, N., Harris, M., Krüger, J., Lefohn, A. E., & Purcell, T. J. (2007) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2007.01012.x · Cited by 2,101
(2006) · Cited by 1,979
Metadata
- Authors
- Frigo, M., & Johnson, S. G.
- Venue
- Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181)
- Publisher
- IEEE
- Published
- 2002-11-27
- Volume
- 3
- Pages
- 1381-1384
- ISSN
- 1520-6149 (ISSN-L)
- OpenAlex
- W2096070062
- Cited by
- 1,801
- References
- 20
- FWCI
- 71.49
- Type
- conference paper
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.