Cooley–Tukey FFT algorithm

Summary

The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N_1N_2 in terms of N1 smaller DFTs of sizes N2, recursively, to reduce the computation time to O(N log N) for highly composite N (smooth numbers). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. Because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT. For example, Rader's or Bluestein's algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the prime-factor algorithm can be exploited for greater efficiency in separating out relatively prime factors. The algorithm, along with its recursive application, was invented by Carl Friedrich Gauss. Cool

Official source

https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (7)

Related publications

Related people

Related units

Related concepts (6)

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time F

Johann Carl Friedrich Gauss (Gauß kaʁl ˈfʁiːdʁɪç ˈɡaʊs; Carolus Fridericus Gauss; 30 April 1777 23 February 1855) was a German mathematician, geodesist, and physicist who made significant contrib

Related concepts

Related courses (5)

Related courses

Related lectures (7)

Related lectures

pyFFS: A Python Library for Fast Fourier Series Computation and Interpolation with GPU Acceleration

Eric Bezzam, Paul Hurley, Sepand Kashani, Matthieu Martin Jean-André Simeoni, Martin Vetterli

Fourier transforms are an often necessary component in many computational tasks, and can be computed efficiently through the fast Fourier transform (FFT) algorithm. However, many applications involve an underlying continuous signal, and a more natural choice would be to work with e.g. the Fourier series (FS) coefficients in order to avoid the additional overhead of translating between the analog and discrete domains. Unfortunately, there exists very little literature and tools for the manipulation of FS coefficients from discrete samples. This paper introduces a Python library called pyFFS for efficient FS coefficient computation, convolution, and interpolation. While the libraries SciPy and NumPy provide efficient functionality for discrete Fourier transform coefficients via the FFT algorithm, pyFFS addresses the computation of FS coefficients through what we call the fast Fourier series (FFS). Moreover, pyFFS includes an FS interpolation method based on the chirp Z-transform that can make it more than an order of magnitude faster than the SciPy equivalent when one wishes to perform interpolation. GPU support through the CuPy library allows for further acceleration, e.g. an order of magnitude faster for computing the 2-D FS coefficients of 1000 x 1000 samples and nearly two orders of magnitude faster for 2-D interpolation. As an application, we discuss the use of pyFFS in Fourier optics. pyFFS is available as an open source package at https://github.com/imagingofthings/pyFFS, with documentation at https://pyffs.readthedocs.io.

2022

Fourier Tools

Paul Hurley, Sepand Kashani, Matthieu Martin Jean-André Simeoni

The FFT algorithm is a key pillar of modern numerical computing. This document is a collection of working notes on FFT-based algorithms. Efficient implementations of the former are made available through the pyFFS package.

2020

MINLP model and two-stage algorithm for the simultaneous synthesis of heat exchanger networks, utility systems and heat recovery cycles

François Maréchal, Emanuele Martelli, Alberto Mian

This work proposes a novel approach for the simultaneous synthesis of Heat Exchanger Networks (HEN) and Utility Systems of chemical processes and energy systems. Given a set of hot and cold process streams and a set of available utility systems, the method determines the optimal selection, arrangement and design of utility systems and the heat exchanger network aiming to rigorously consider the trade-off between efficiency and capital costs. The mathematical formulation uses the SYNHEAT superstructure for the HEN, and ad hoc superstructures and nonlinear models to represent the utility systems. The challenging nonconvex MINLP is solved with a two-stage algorithm. A sequential synthesis algorithm is specifically developed to generate a good starting solution. The algorithm is tested on a literature test problem and two industrial problems, the optimization of the Heat Recovery Steam Cycle of a Natural Gas Combined Cycle and the heat recovery system of an Integrated Gasification Combined Cycle. (C) 2017 Elsevier Ltd. All rights reserved.

2017