Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2019 | OriginalPaper | Chapter

6. High-Performance FFT Algorithms

Author : Daisuke Takahashi

Published in: Fast Fourier Transform Algorithms for Parallel Computers

Publisher: Springer Singapore

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter presents high-performance FFT algorithms. First, the four-step FFT algorithm and five-step FFT algorithm are described. Next, the six-step FFT algorithm and blocked six-step FFT algorithm are explained. Then, nine-step FFT algorithm and recursive six-step FFT, and blocked multidimensional FFT algorithms are described. Finally, FFT algorithms suitable for fused multiply–add instructions and FFT algorithms for SIMD instructions are explained.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Multidimensional FFT Algorithms
next chapter Parallel FFT Algorithms for Shared-Memory Parallel Computers
Literature
1.
Bailey, D.H.: FFTs in external or hierarchical memory. J. Supercomput. 4, 23–35 (1990)CrossRef
2.
Brigham, E.O.: The Fast Fourier Transform and Its Applications. Prentice-Hall, Englewood Cliffs, NJ (1988)
3.
Burrus, C.S., Eschenbacher, P.W.: An in-place, in-order prime factor FFT algorithm. IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 806–817 (1981)CrossRef
4.
Franchetti, F., Karner, H., Kral, S., Ueberhuber, C.W.: Architecture independent short vector FFTs. In: Proceedings of 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2001), vol. 2, pp. 1109–1112 (2001)
5.
Frigo, M., Johnson, S.G.: The design and implementation of FFTW3. Proc. IEEE 93, 216–231 (2005)CrossRef
6.
Goedecker, S.: Fast radix 2, 3, 4, and 5 kernels for fast Fourier transformations on computers with overlapping multiply-add instructions. SIAM J. Sci. Comput. 18, 1605–1611 (1997)MathSciNetCrossRef
7.
Hegland, M.: A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing. Numer. Math. 68, 507–547 (1994)MathSciNetCrossRef
8.
9.
10.
Karner, H., Auer, M., Ueberhuber, C.W.: Multiply-add optimized FFT kernels. Math. Models Methods Appl. Sci. 11, 105–117 (2001)MathSciNetCrossRef
11.
Kolba, D.P., Parks, T.W.: A prime factor FFT algorithm using high-speed convolution. IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 281–294 (1977)CrossRef
12.
Kral, S., Franchetti, F., Lorenz, J., Ueberhuber, C.W.: SIMD vectorization of straight line FFT code. In: Proceedings of 9th International Euro-Par Conference (Euro-Par 2003). Lecture Notes in Computer Science, vol. 2790, pp. 251–260. Springer, Berlin (2003)CrossRef
13.
14.
Linzer, E.N., Feig, E.: Implementation of efficient FFT algorithms on fused multiply-add architectures. IEEE Trans. Signal Process. 41, 93–107 (1993)CrossRef
15.
McFarlin, D.S., Arbatov, V., Franchetti, F., Püschel, M.: Automatic SIMD vectorization of fast Fourier transforms for the Larrabee and AVX instruction sets. In: Proceedings of 25th International Conference on Supercomputing (ICS’11), pp. 265–274 (2011)
16.
Nadehara, K., Miyazaki, T., Kuroda, I.: Radix-4 FFT implementation using SIMD multimedia instructions. In: Proceedings of 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’99), vol. 4, pp. 2131–2134 (1999)
17.
Nussbaumer, H.J.: Fast Fourier Transform and Convolution Algorithms, updated edn. Springer-Verlag, New York (1982). Second corrected and updated editionCrossRef
18.
Popovici, D.T., Franchetti, F., Low, T.M.: Mixed data layout kernels for vectorized complex arithmetic. In: Proceedings of 2017 IEEE High Performance Extreme Computing Conference (HPEC 2017) (2017)
19.
Püschel, M., Moura, J.M.F., Johnson, J.R., Padua, D., Veloso, M.M., Singer, B.W., Xiong, J., Franchetti, F., Gačić, A., Voronenko, Y., Chen, K., Johnson, R.W., Rizzolo, N.: SPIRAL: code generation for DSP transforms. Proc. IEEE 93, 232–275 (2005)CrossRef
20.
Rodriguez, P.: A radix-2 FFT algorithm for modern single instruction multiple data (SIMD) architectures. In: Proceedings of 2002 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2002), vol. 3, pp. 3220–3223 (2002)
21.
Takahashi, D.: A new radix-6 FFT algorithm suitable for multiply-add instruction. In: Proceedings of 2000 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2000), vol. 6, pp. 3343–3346 (2000)
22.
Takahashi, D.: A blocking algorithm for parallel 1-D FFT on shared-memory parallel computers. In: Proceedings of 6th International Conference on Applied Parallel Computing (PARA 2002). Lecture Notes in Computer Science, vol. 2367, pp. 380–389. Springer, Berlin (2002)
23.
24.
Takahashi, D.: A radix-16 FFT algorithm suitable for multiply-add instruction based on Goedecker method. In: Proceedings of 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2003), vol. 2, pp. 665–668 (2003)
25.
Takahashi, D.: An implementation of parallel 1-D FFT using SSE3 instructions on dual-core processors. In: Proceedings of 8th International Workshop on State of the Art in Scientific Computing (PARA 2006). Lecture Notes in Computer Science, vol. 4699, pp. 1178–1187. Springer, Berlin (2007)
26.
Takahashi, D.: An implementation of parallel 2-D FFT using Intel AVX instructions on multi-core processors. In: Proceedings of 12th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2012), Part II. Lecture Notes in Computer Science, vol. 7440, pp. 197–205. Springer, Berlin (2012)CrossRef
27.
Takahashi, D., Boku, T., Sato, M.: A blocking algorithm for parallel 1-D FFT on clusters of PCs. In: Proceedings of 8th International Euro-Par Conference (Euro-Par 2002). Lecture Notes in Computer Science, vol. 2400, pp. 691–700. Springer, Berlin (2002)CrossRef
28.
Takahashi, D., Uno, A., Yokokawa, M.: An implementation of parallel 1-D FFT on the K computer. In: Proceedings of 2012 IEEE 14th International Conference on High Performance Computing and Communications (HPCC-2012), pp. 344–350 (2012)
29.
Van Loan, C.: Computational Frameworks for the Fast Fourier Transform. SIAM Press, Philadelphia, PA (1992)CrossRef
30.
Metadata
Title
High-Performance FFT Algorithms
Author
Daisuke Takahashi
Copyright Year
2019
Publisher
Springer Singapore
Book
Fast Fourier Transform Algorithms for Parallel Computers

Print ISBN: 978-981-13-9964-0

Electronic ISBN: 978-981-13-9965-7

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-981-13-9965-7_6

Premium Partner

    Image Credits