Abstract | ||
---|---|---|
This paper presents an efficient multiscale butterfly algorithm forcomputing Fourier integral operators (FIOs) of the form $(\\mathcal{L} f)(x) = \\int_{\\mathbb{R}^d}a(x,\\xi) e^{2\\pi \\imath \\Phi(x,\\xi)}\\widehat{f}(\\xi) d\\xi$, where $\\Phi(x,\\xi)$ is a phase function, $a(x,\\xi)$ is anamplitude function, and $f(x)$ is a given input. The frequencydomain is hierarchically decomposed into a union of Cartesiancoronas. The integral kernel $a(x,\\xi) e^{2\\pi \\imath \\Phi(x,\\xi)}$ ineach corona satisfies a special low-rank property that enables theapplication of a butterfly algorithm on the Cartesian phase-spacegrid. This leads to an algorithm with quasi-linear operationcomplexity and linear memory complexity. Different from previousbutterfly methods for the FIOs, this new approach is simple andreduces the computational cost by avoiding extra coordinatetransformations. Numerical examples in two and three dimensions areprovided to demonstrate the practical advantages of the newalgorithm. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1137/140997658 | Multiscale Modeling and Simulation |
Keywords | Field | DocType |
fourier integral operators | Fourier integral operator,Kernel (linear algebra),Frequency domain,Combinatorics,Mathematical analysis,Algorithm,Phase function,Amplitude,Mathematics,Cartesian coordinate system | Journal |
Volume | Issue | ISSN |
13 | 2 | 1540-3459 |
Citations | PageRank | References |
1 | 0.39 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
yingzhou li | 1 | 1 | 0.39 |
Haizhao Yang | 2 | 46 | 13.03 |
Lexing Ying | 3 | 1273 | 103.92 |