A multiscale butterfly algorithm for multidimensional fourier integral operators
Date
2015-01-01
Authors
Journal Title
Journal ISSN
Volume Title
Repository Usage Stats
views
downloads
Citation Stats
Attention Stats
Abstract
© 2015 Society for Industrial and Applied Mathematics.This paper presents an efficient multiscale butterfly algorithm for computing Fourier integral operators (FIOs) of the form (Lf)(x) =∫ ℝ da(x, ξ)e2πiΦ(x,ξ)f(ξ)dξ, where Φ(x, ξ) is a phase function, a(x, ξ) is an amplitude function, and f(x) is a given input. The frequency domain is hierarchically decomposed into a union of Cartesian coronas. The integral kernel a(x, ξ)e2πiΦ(x,ξ)in each corona satisfies a special low-rank property that enables the application of a butterfly algorithm on the Cartesian phase-space grid. This leads to an algorithm with quasi-linear operation complexity and linear memory complexity. Different from previous butterfly methods for the FIOs, this new approach is simple and reduces the computational cost by avoiding extra coordinate transformations. Numerical examples in two and three dimensions are provided to demonstrate the practical advantages of the new algorithm.
Type
Department
Description
Provenance
Subjects
Citation
Permalink
Published Version (Please cite this version)
Publication Info
Li, Yingzhou, Haizhao Yang and Lexing Ying (2015). A multiscale butterfly algorithm for multidimensional fourier integral operators. Multiscale Modeling and Simulation, 13(2). pp. 614–631. 10.1137/140997658 Retrieved from https://hdl.handle.net/10161/11655.
This is constructed from limited available data and may be imprecise. To cite this article, please review & use the official citation provided by the journal.
Collections
Unless otherwise indicated, scholarly articles published by Duke faculty members are made available here with a CC-BY-NC (Creative Commons Attribution Non-Commercial) license, as enabled by the Duke Open Access Policy. If you wish to use the materials in ways not already permitted under CC-BY-NC, please consult the copyright owner. Other materials are made available here through the author’s grant of a non-exclusive license to make their work openly accessible.