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

DOI10.1007/S00607-007-0222-6MaRDI QIDQ2369946zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

Cites work

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

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
• Accurate pairwise convolutions of non-negative vectors via FFT
• Separation of variables and the computation of Fourier transforms on finite groups. II
• 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

Describes a project that uses

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)