Mathematics – Numerical Analysis
Scientific paper
2008-09-03
Mathematics
Numerical Analysis
25 pages, 2 figures
Scientific paper
This paper is concerned with the fast computation of Fourier integral operators of the general form $\int_{\R^d} e^{2\pi\i \Phi(x,k)} f(k) d k$, where $k$ is a frequency variable, $\Phi(x,k)$ is a phase function obeying a standard homogeneity condition, and $f$ is a given input. This is of interest for such fundamental computations are connected with the problem of finding numerical solutions to wave equations, and also frequently arise in many applications including reflection seismology, curvilinear tomography and others. In two dimensions, when the input and output are sampled on $N \times N$ Cartesian grids, a direct evaluation requires $O(N^4)$ operations, which is often times prohibitively expensive. This paper introduces a novel algorithm running in $O(N^2 \log N)$ time, i. e. with near-optimal computational complexity, and whose overall structure follows that of the butterfly algorithm [Michielssen and Boag, IEEE Trans Antennas Propagat 44 (1996), 1086-1093]. Underlying this algorithm is a mathematical insight concerning the restriction of the kernel $e^{2\pi\i \Phi(x,k)}$ to subsets of the time and frequency domains. Whenever these subsets obey a simple geometric condition, the restricted kernel has approximately low-rank; we propose constructing such low-rank approximations using a special interpolation scheme, which prefactors the oscillatory component, interpolates the remaining nonoscillatory part and, lastly, remodulates the outcome. A byproduct of this scheme is that the whole algorithm is highly efficient in terms of memory requirement. Numerical results demonstrate the performance and illustrate the empirical properties of this algorithm.
Candes Emmanuel
Demanet Laurent
Ying Lexing
No associations
LandOfFree
A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators 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 A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-141286