A new matrix approach to real FFTs and convolutions of length 2ᵏ

DOI10.1007/S00607-007-0222-6zbMATH Open1138.65112DBLPjournals/computing/LundyB07OpenAlexW2000181170WikidataQ56048275 ScholiaQ56048275MaRDI QIDQ2369946FDOQ2369946

Authors: Thomas J. Lundy, James M. van Buskirk 

Publication date: 21 June 2007

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-007-0222-6

Recommendations

• scientific article; zbMATH DE number 3915602
• Modified FFTs for Fused Multiply-Add Architectures
• scientific article; zbMATH DE number 1174541
• scientific article; zbMATH DE number 3926792
• Real-valued decimation-in-time and decimation-in-frequency algorithms

zbMATH Keywords

matrix factorizationfast Fourier transformFortran programsplit-radix FFTFermat prime orderfewer arithmetic operationsminimum arithmetic costsRader's methodreal convolutionreal FFTscaled odd tail

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Convolution, factorization for one variable harmonic analysis (42A85) Numerical methods for discrete and fast Fourier transforms (65T50)

Cites Work

• Fast Fourier transforms: A tutorial review and a state of the art
• Fast mixed-radix real Fourier transforms
• Simple FFT and DCT algorithms with reduced number of operations.
• The design of optimal DFT algorithms using dynamic programming
• A new set of minimum-add small-n rotated DFT modules
• Split-radix algorithms for length-p/sup m/ DFT's
• Fast computation of real discrete Fourier transform for any number of data points
• Real-valued decimation-in-time and decimation-in-frequency algorithms

Cited In (13)

• The Tangent FFT
• A New Representation of FFT Algorithms Using Triangular Matrices
• Blind image deconvolution using a banded matrix method
• On the real complexity of a complex DFT
• Separation of variables and the computation of Fourier transforms on finite groups. II
• Accurate pairwise convolutions of non-negative vectors via FFT
• Generating and searching families of FFT algorithms
• On elliptic curves and random matrix theory
• Quasiperiodic spectra and orthogonality for iterated function system measures
• Multiplication
• The matrices form of 2FFT
• Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity
• Separation of variables and the computation of Fourier transforms on finite groups. II

Uses Software

• FFTPACK

This page was built for publication: A new matrix approach to real FFTs and convolutions of length \(2^k\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369946)