A new truncated Fourier transform algorithm

DOI10.1145/2465506.2465957MaRDI QIDQ2963208zbMATH OpenOpenAlexFDO

Authors Andrew Arnold

Publication date 10 February 2017

Published in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4960

zbMATH Keywords

in-place algorithmstruncated Fourier transform

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: Truncated Fourier Transforms (TFTs), first introduced by Van der Hoeven, refer to a family of algorithms that attempt to smooth "jumps" in complexity exhibited by FFT algorithms. We present an in-place TFT whose time complexity, measured in terms of ring operations, is comparable to existing not-in-place TFT methods. We also describe a transformation that maps between two families of TFT algorithms that use different sets of evaluation points.

Recommendations

• An in-place truncated Fourier transform and applications to polynomial multiplication
• An in-place truncated Fourier transform
• The truncated fourier transform and applications
• The truncated Fourier transform for mixed radices
• High performance implementation of the TFT

Cited in

(14)

• A cache-friendly truncated FFT
• An in-place truncated Fourier transform
• Computing characteristic polynomials of matrices of structured polynomials
• An in-place truncated Fourier transform and applications to polynomial multiplication
• Structured FFT and TFT: symmetric and lattice polynomials
• scientific article; zbMATH DE number 3862403 (Why is no real title available?)
• High performance implementation of the TFT
• The truncated fourier transform and applications
• A New Representation of FFT Algorithms Using Triangular Matrices
• The truncated Fourier transform for mixed radices
• Multiplication
• Fast in-place accumulation
• In-place accumulation of fast multiplication formulae
• A new Fourier transform

This page was built for publication: A new truncated Fourier transform algorithm

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