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,453
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
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
There’s plenty of room at the Top: What will drive computer performance after Moore’s law?
Leiserson, C. E., Thompson, N. C., Emer, J. S., Kuszmaul, B. C., Lampson, B. W., Sanchez, D., & Schardl, T. B. (2020) · Science · doi:10.1126/science.aam9744 · Cited by 469
Memory---Sequoia: programming the memory hierarchy
Fatahalian, K., Dally, W. J., Hanrahan, P., Horn, D. R., Knight, T. J., Leem, L., Houston, M., Park, J. Y., Erez, M., Ren, M., et al. (2006) · Proceedings of the 2006 ACM/IEEE conference on Supercomputing - SC '06 · doi:10.1145/1188455.1188543 · Cited by 452
A modified split-radix fft with fewer arithmetic operations
Johnson, S. G., & Frigo, M. (2007) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.882087 · Cited by 380
Self-citationPrecimonious: tuning assistant for floating-point precision
Rubio-González, C., Nguyen, C., Nguyen, H. D., Demmel, J., Kahan, W., Sen, K., Bailey, D. H., Iancu, C., & Hough, D. (2013) · Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis · doi:10.1145/2503210.2503296 · Cited by 281
Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs
Rompf, T., & Odersky, M. (2010) · Proceedings of the ninth international conference on Generative programming and component engineering · doi:10.1145/1868294.1868314 · Cited by 277
Spatially-Stationary Model for Holographic MIMO Small-Scale Fading
Pizzo, A., Marzetta, T. L., & Sanguinetti, L. (2020) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2020.3000877 · Cited by 263
Three-Dimensional Molecular Theory of Solvation Coupled with Molecular Dynamics in Amber
Luchko, T., Gusarov, S., Roe, D. R., Simmerling, C., Case, D. A., Tuszynski, J., & Kovalenko, A. (2010) · Journal of Chemical Theory and Computation · doi:10.1021/ct900460m · Cited by 262
An auto-tuning framework for parallel multicore stencil computations
Kamil, S., Chan, C., Oliker, L., Shalf, J., & Williams, S. (2010) · 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS) · doi:10.1109/ipdps.2010.5470421 · Cited by 209
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.