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 1 day ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 332 Views 40411
- by Eli 1 day ago Iran's President Ebrahim Raisi Aged 63 Dies in a Helicopter Crash View the latest post Replies 3 Views 63
- by Eli 1 day ago Re: What is in Your Mind? View the latest post Replies 717 Views 307158
- by Eli 3 days ago PySpark for Large Data Processing View the latest post Replies 2 Views 8172
- by Eli 3 days ago Online Bible View the latest post Replies 3 Views 23330
- by Eli 3 days ago Generating SSH Key and Adding it to the ssh-agent for Authentication on GitHub View the latest post Replies 1 Views 488
- by Eli 1 week ago Russia Invades Ukraine View the latest post Replies 663 Views 240961
- by Eli 2 weeks ago President Museveni's Speech During International Development Association (IDA) Summit View the latest post Replies 1 Views 509
- by Eli 2 weeks ago From Simple Linear Regression Analysis to Covariance & Correlation to Independent Determinant, and R-Squared View the latest post Replies 11 Views 25144
- by Eli 2 weeks ago Collection of Greatest Christian Hymns of all Times View the latest post Replies 34 Views 72558
-
Fastest Fourier Transform for Discrete Fourier Transform
- Eli
- Senior Expert Member
- Reactions: 183
- Posts: 5410
- 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