Fastest Fourier Transform in the West - FFTW is a C subroutine library for computing the discrete Fourier transform (DFT) in one or more dimensions, of arbitrary input size, and of both real and complex data (as well as of even/odd data, i.e. the discrete cosine/sine transforms or DCT/DST).
Usually, the DFT is computed by a very clever (and truly revolutionary) algorithm known as the fast Fourier transform (FFT). The FFT was discovered by Gauss in 1805 and rediscovered many times since then, but most people attribute its modern incarnation to James W. Cooley and John W. Tukey in 1965. The key advantage of the FFT over the DFT is that the operational complexity decreases from \(O(N^{2})\) for a DFT to \(O(N {\rm log}_{2}(N))\) for the FFT.
FFTW is a modern implementation of the FFT that allows \(O(N {\rm log}_{2}(N))\) complexity for any value of \(N\), not just those that are powers of two or the products of only small primes.
You can download the latest version of FFTW from http://www.fftw.org/download.html
-
- Active Topics
-
-
- by Eli 10 hours ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 328 Views 37791
- by Eli 11 hours ago Re: What is in Your Mind? View the latest post Replies 705 Views 303519
- by Eli 4 days ago Russia Invades Ukraine View the latest post Replies 663 Views 238516
- by Eli 6 days ago PySpark for Large Data Processing View the latest post Replies 1 Views 7934
- by Eli 1 week ago President Museveni's Speech During International Development Association (IDA) Summit View the latest post Replies 1 Views 325
- by Eli 1 week ago From Simple Linear Regression Analysis to Covariance & Correlation to Independent Determinant, and R-Squared View the latest post Replies 11 Views 24934
- by Eli 2 weeks ago Collection of Greatest Christian Hymns of all Times View the latest post Replies 34 Views 70493
- by Eli 2 weeks ago Pondering Big Cosmology Questions Through Lectures and Dialogues View the latest post Replies 34 Views 58504
- by Eli 2 weeks ago Programmatically Manipulate Files: Renaming, Reading, Writing, Deleting, and Moving Files Between Folders View the latest post Replies 7 Views 18598
- by Eli 3 weeks ago Iran Launches Retaliatory Attack Against Israel, and Israel Retaliates by Attacking Iranian Isfahan Millitary Base View the latest post Replies 28 Views 20915
-
Fastest Fourier Transform for Discrete Fourier Transform
- Eli
- Senior Expert Member
- Reactions: 183
- Posts: 5387
- Joined: 9 years ago
- Location: Tanzania
- Has thanked: 75 times
- Been thanked: 88 times
- Contact:
Here is an interesting series of lectures mostly by Steve Brunton from Washington University on Fourier Transform:
The Fourier Transform
The Discrete Fourier Transform - Simple Step by Step
Computing the DFT Matrix
FFT Algorithm
FFT
Denoising Data with FFT
Wavelets and Multiresolution Analysis
Computing Derivatives with FFT
Solving the Heat Equation with the Fourier Transform
Solving PDEs with the FFT
Solving PDEs with the FFT, Part 2
The Fourier Transform
The Discrete Fourier Transform - Simple Step by Step
Computing the DFT Matrix
FFT Algorithm
FFT
Denoising Data with FFT
Wavelets and Multiresolution Analysis
Computing Derivatives with FFT
Solving the Heat Equation with the Fourier Transform
Solving PDEs with the FFT
Solving PDEs with the FFT, Part 2
TSSFL -- A Creative Journey Towards Infinite Possibilities!
-
- Information
-
Who is online
Users browsing this forum: No registered users and 0 guests