Ping Tak Peter Tang
Abstract
The Fast Fourier Transform (FFT) algorithm that calculates the Discrete Fourier Transform (DFT) is one of the major breakthroughs in scientific computing and is now an indispensable tool in a vast number of fields. Unfortunately, software applications that provide fast computation of DFT via FFT differ vastly in functionality and lack uniformity. A widely accepted Applications Programmer Interface (API) for DFT would advance the field of scientific computing significantly. In this article, we present the specification of DFTI, a new interface that combines functionality with ease of use. This API is our strawman proposal toward a common interface for DFT calculations.
- Brigham, E. O. 1988. The Fast Fourier Transform and Its Applications. Prentice Hall, Englewood Cliffs, NJ. Google Scholar
- Frigo, M. and Johnson, S. G. 1998. FFTW: An adaptive software architecture for the FFT. In Proceedings of ICASSP Conference. 3, 1381--1384.Google Scholar
- Johnsson, L. and Mirkovic, D. 2001. Automatic performance tuning in the UHFFT library. In Proceedings of the International Conference on Computational Science. Lecture Notes in Computer Science, vol. 2073. Springer-Verlag, Berlin, Germany. Google Scholar
- Moura, J., Johnson, J., Johnson, R., Padua, D., Prasanna, V., Pschel, M., and Veloso, M. 1998. SPIRAL: Automatic library generation and platform-adaptation for DSP algorithms. Go online to http://www.spiral.net.Google Scholar
- Papoulis, A. 1984. The Fourier Integral and its Applications, 2nd ed. McGraw-Hill, New York, NY.Google Scholar
- Schwartz, D. A., Judd, R. R., Harrod, W. J., and Manley, D. P. 2002. VSIPL API. Go online to http://www.vsipl.org.Google Scholar
- Van Loan, C. 1992. Computational Frameworks for the Fast Fourier Transform. SIAM Press, Philadelphia, PA. Google Scholar
Index Terms
- DFTI---a new interface for Fast Fourier Transform libraries
Recommendations
The Partial Fast Fourier Transform
An efficient algorithm for computing the one-dimensional partial fast Fourier transform $$f_j=\sum _{k=0}^{c(j)}e^{2\pi ijk/N} F_k$$fj=?k=0c(j)e2?ijk/NFk is presented. Naive computation of the partial fast Fourier transform requires $${\mathcal O}(N^2)$$...
A New Hybrid Algorithm for Computing a Fast Discrete Fourier Transform
In this paper for certain long transform lengths, Winograd's algorithm for computing the discrete Fourier transform (DFT) is extended considerably. This is accomplisbed by performing the cyclic convolution, required by Winograd's method, with the ...
The Fast Fourier Transform for Experimentalists, Part V: Filters
This fifth segment in what has turned out to be a six-part series on the fast Fourier transform (FFT) will be the last to deal solely with methods or ideas associated with the transform process itself.
Comments