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 13 hours ago Iran Launches Retaliatory Attack Against Israel View the latest post Replies 20 Views 526
- by Eli 14 hours ago Re: What is in Your Mind? View the latest post Replies 677 Views 273373
- by Eli 21 hours ago Russia Invades Ukraine View the latest post Replies 646 Views 210107
- by Eli 1 day ago Programmatically Move Files from One Folder to Another View the latest post Replies 6 Views 1326
- by Forbidden_Technology 2 days ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 312 Views 8432
- by Eli 1 week ago Collection of Greatest Christian Hymns of all Times View the latest post Replies 33 Views 43481
- by Eli 1 week ago What is Retrieval-Augmented Generation (RAG)? View the latest post Replies 2 Views 252
- by Eli 1 week ago Chat With ChatGPT - An Interactive Conversational AI View the latest post Replies 22 Views 24137
- by Eli 2 weeks ago Christian Podcasts View the latest post Replies 5 Views 28631
- by Eli 2 weeks ago Pondering Big Cosmology Questions Through Lectures and Dialogues View the latest post Replies 33 Views 45389
-
Fastest Fourier Transform for Discrete Fourier Transform
- Eli
- Senior Expert Member
- Reactions: 183
- Posts: 5303
- 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