The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
A fast Fourier transform compiler
Abstract
The FFTW library for computing the discrete Fourier transform (DFT) has gained a wide acceptance in both academia and industry, because it provides excellent performance on a variety of machines (even competitive with or faster than equivalent libraries supplied by vendors). In FFTW, most of the performance-critical code was generated automatically by a special-purpose compiler, called genfft, that outputs C code. Written in Objective Caml, genfft can produce DFT programs for any input length, and it can specialize the DFT program for the common case where the input data are real instead of complex. Unexpectedly, genfft "discovered" algorithms that were previously unknown, and it was able to reduce the arithmetic complexity of some other existing algorithms. This paper describes the internals of this special-purpose compiler in some detail, and it argues that a specialized compiler is a valuable tool.
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
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
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
Compilers: Principles, Techniques, and Tools
Aho, A. V., Sethi, R., & Ullman, J. D. (1986) · Cited by 8,448
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
Advanced Compiler Design and Implementation
Muchnick, S. S. (1997) · Cited by 2,312
The Art of Computer Programming
Worlton, W. J. (1968) · Nuclear Science and Engineering · doi:10.13182/nse68-a19548 · Cited by 2,251
FFTW: an adaptive software architecture for the FFT
Frigo, M., & Johnson, S. G. (2002) · Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181) · doi:10.1109/icassp.1998.681704 · Cited by 1,801
Self-citationFast 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
Automatically Tuned Linear Algebra Software
Whaley, R. C., & Dongarra, J. J. (1998) · Conference on High Performance Computing (Supercomputing) · doi:10.5555/509058.509096 · Cited by 854
On computing the discrete Fourier transform
Winograd, S. (1978) · Mathematics of Computation · doi:10.1090/s0025-5718-1978-0468306-4 · Cited by 613
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
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
I/O complexity: The red-blue pebble game
Hong, J., & Kung, H. T. (1981) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800076.802486 · Cited by 474
Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology
Bilmes, J., Asanovic, K., Chin, C.-W., & Demmel, J. (2014) · 25th Anniversary International Conference on Supercomputing Anniversary Volume - · doi:10.1145/2591635.2667174 · Cited by 453
The Art of Computer Programming. Volume 2: Seminumerical Algorithms (Donald E. Knuth)
MacLaren, M. D. (1970) · SIAM Review · doi:10.1137/1012065 · Cited by 306
The Fastest Fourier Transform in the West
Frigo, M., & Johnson, S. G. (1997) · doi:10.21236/ada479065 · Cited by 244
Self-citationAlgorithms for Discrete Fourier Transform and Convolution
Tolimieri, R., Lu, C., & An, M. (1997) · Signal Processing and Digital Filtering · doi:10.1007/978-1-4757-2767-8 · Cited by 201
Analysis of linear digital networks
Crochiere, R. E., & Oppenheim, A. V. (1975) · Proceedings of the IEEE · doi:10.1109/proc.1975.9793 · Cited by 200
Wadler, P. L. (1997) · ACM Computing Surveys · doi:10.1145/262009.262011 · Cited by 141
Optimizing the Performance of Sparse Matrix-Vector Multiplication
Im, E. (2000) · UC Berkeley · Cited by 120
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
Code Generators for Automatic Tuning of Numerical Kernels: Experiences with FFTW
Vuduc, R. W., & Demmel, J. W. (2000) · Cited by 11
Cited by
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-citationAutomated empirical optimizations of software and the ATLAS project
Clint Whaley, R., Petitet, A., & Dongarra, J. J. (2001) · Parallel Computing · doi:10.1016/s0167-8191(00)00087-9 · Cited by 1,317
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
Frigo, M., Leiserson, C. E., Prokop, H., & Ramachandran, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814600 · Cited by 803
Self-citationAuto-tuning a high-level language targeted to GPU codes
Grauer-Gray, S., Xu, L., Searles, R., Ayalasomayajula, S., & Cavazos, J. (2012) · 2012 Innovative Parallel Computing (InPar) · doi:10.1109/inpar.2012.6339595 · Cited by 470
Metadata
- Authors
- Frigo, M.
- Venue
- Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation
- Publisher
- ACM
- Published
- 1999-05
- Pages
- 169-180
- ISSN
- 1531-7102 (ISSN-L)
- OpenAlex
- W2164197394
- Cited by
- 438
- References
- 27
- FWCI
- 8.42
- 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.