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 Iran Launches Retaliatory Attack Against Israel, and Israel Retaliates by Attacking Iranian Isfahan Millitary Base View the latest post Replies 28 Views 881
- by Eli 2 days ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 319 Views 8939
- by Eli 3 days ago Re: What is in Your Mind? View the latest post Replies 685 Views 274050
- by Eli 5 days ago Python Packages for Scientific Computing View the latest post Replies 8 Views 3000
- by Eli 5 days ago Dunia Yetu: Building Tanzania's Digital Future Together View the latest post Replies 5 Views 1839
- by Eli 1 week ago Russia Invades Ukraine View the latest post Replies 646 Views 210446
- by Eli 1 week ago Programmatically Move Files from One Folder to Another View the latest post Replies 6 Views 1426
- by Eli 1 week ago Collection of Greatest Christian Hymns of all Times View the latest post Replies 33 Views 43733
- by Eli 2 weeks ago What is Retrieval-Augmented Generation (RAG)? View the latest post Replies 2 Views 358
- by Eli 2 weeks ago Chat With ChatGPT - An Interactive Conversational AI View the latest post Replies 22 Views 24353
-
Fastest Fourier Transform for Discrete Fourier Transform
- Eli
- Senior Expert Member
- Reactions: 183
- Posts: 5330
- 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 2 guests