Mathematics – Numerical Analysis
Scientific paper
2008-02-12
Mathematics
Numerical Analysis
12 pages
Scientific paper
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(N\log^2 N)$ steps. Our solution in 2D is an approximate but accurate algorithm that takes $O(N^2 \log^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.
Fomel Sergey
Ying Lexing
No associations
LandOfFree
Fast Computation of Partial Fourier Transforms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fast Computation of Partial Fourier Transforms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Computation of Partial Fourier Transforms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-107809