Fast computation of partial Fourier transforms

DOI10.1137/080715457MaRDI QIDQ3549901zbMATH OpenOpenAlexFDO

Authors Lexing Ying, Sergey Fomel

Publication date 30 March 2010

Published in Multiscale Modeling & Simulation (Search for Journal in Brave)

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

zbMATH Keywords

butterfly algorithmcomplexityfast Fourier transformfractional Fourier transformmultiscale decompositionnumerical examplespartial Fourier transformreflection seismologywave extrapolation

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20) Seismology (including tsunami modeling), earthquakes (86A15)

Abstract: We introduce two efficient algorithms for computing the partial Fourier transforms in one and two dimensions. Our study is motivated by the wave extrapolation procedure in reflection seismology. In both algorithms, the main idea is to decompose the summation domain of into simpler components in a multiscale way. Existing fast algorithms are then applied to each component to obtain optimal complexity. The algorithm in 1D is exact and takes $O(Nlo{g}^{2}N)$ steps. Our solution in 2D is an approximate but accurate algorithm that takes $O(N^{2}lo{g}^{2}N)$ steps. In both cases, the complexities are almost linear in terms of the degree of freedom. We provide numerical results on several test examples.

Recommendations

• The partial fast Fourier transform
• Sparse Fourier Transform via Butterfly Algorithm
• A fast butterfly algorithm for the computation of Fourier integral operators
• Fast and accurate polar Fourier transform
• Rapid Computation of the Discrete Fourier Transform

Cited in

(19)

• Fast Hensel's lifting implementation using partial fraction decomposition
• Fast generalized Fourier transforms
• Methods for fast computation of integral transforms
• Multithreaded implicitly dealiased convolutions
• The partial fast Fourier transform
• Fast and approximate computation of Laplace and Fourier transforms
• Fast wave computation via Fourier integral operators
• A fast algorithm for multilinear operators
• scientific article; zbMATH DE number 1960289 (Why is no real title available?)
• A PARALLEL FAST FOURIER TRANSFORM
• Improved Twiddle Access for Fast Fourier Transforms
• Fast structured Jacobi-Jacobi transforms
• Fast Computation of Multidimensional Fourier Integrals
• Fast Fourier Transform Accelerated Fast Multipole Algorithm
• Rapid Computation of the Discrete Fourier Transform
• Parametric versions of the fast Fourier transform
• Fast Fourier transform of small orders.
• Efficient Fourier transforms for transverse momentum dependent distributions
• Fast transform from an adaptive multi-wavelet representation to a partial Fourier representation

This page was built for publication: Fast computation of partial Fourier transforms

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