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