Fast Fourier transforms: A tutorial review and a state of the art

DOI10.1016/0165-1684(90)90158-UzbMath0704.65106OpenAlexW2123119012WikidataQ54087145 ScholiaQ54087145MaRDI QIDQ917259

Publication date: 1990

Published in: Signal Processing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0165-1684(90)90158-u

zbMATH Keywords

computational complexity fast algorithms fast Fourier transform implementation divide and conquer historical review multi-dimensional transforms tutorial review

Mathematics Subject Classification ID

Trigonometric interpolation (42A15) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items

Fast Fourier transform revisited ⋮ Revised fast convolution ⋮ A COOLEY-TUKEY MODIFIED ALGORITHM IN FAST FOURIER TRANSFORM ⋮ Wavelet inpainting with the \(\ell_{0}\) sparse regularization ⋮ A new matrix approach to real FFTs and convolutions of length \(2^k\) ⋮ Calculation scheme based on a weighted primitive: application to image processing transforms ⋮ A new superfast bit reversal algorithm ⋮ Five-step FFT algorithm with reduced computational complexity ⋮ The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data ⋮ A program for performing exact quantum dynamics calculations using cylindrical polar coordinates: a nanotube application ⋮ pyFFS: A Python Library for Fast Fourier Series Computation and Interpolation with GPU Acceleration ⋮ A review and a synthesis of the fast Fourier transform algorithms for exact analysis of discrete data ⋮ Two classes of elliptic discrete Fourier transforms: properties and examples ⋮ Fast matrix splitting iteration method for the linear system from spatial fractional diffusion equations ⋮ SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials ⋮ Does the dual-sieve attack on learning with errors even work? ⋮ Frequency-domain features for ECG beat discrimination using grey relational analysis-based classifier ⋮ Computationally efficient database and spectral interpolation for fully plastic Taylor-type crystal plasticity calculations of face-centered cubic polycrystals ⋮ The Tangent FFT ⋮ Multilevel Optimal Transport: A Fast Approximation of Wasserstein-1 Distances ⋮ An effective procedure for extracting the first few bridge frequencies from a test vehicle ⋮ Vector coding algorithms for multidimensional discrete Fourier transform ⋮ Calibrated FFT-based density approximations for \(\alpha\)-stable distributions ⋮ Fast and memory-efficient algorithms for computing quadratic time-frequency distributions ⋮ Maximum likelihood estimation of stochastic frontier models by the Fourier transform ⋮ A comparison of algorithms for exact goodness-of-fit tests for multinomial data ⋮ Fast Fourier optimization ⋮ Improvement of the discrete cosine transform calculation by means of a recursive method ⋮ Natural frequencies of nonlinear vibration of axially moving beams ⋮ Wavelet transforms versus Fourier transforms ⋮ Construction of distinct discrete time scattering quantum walk formulations on the honeycomb lattice ⋮ DFT spectrum-sparsity-based quasi-periodic signal identification and application ⋮ Characterizing empirical mode decomposition algorithm using signal processing techniques ⋮ Gaussian DCT coefficient models ⋮ Performance estimation when the distribution of inefficiency is unknown ⋮ Seismic waveform inversion using the finite-difference contrast source inversion method