A multiscale butterfly algorithm for multidimensional fourier integral operators
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) =∫ <inf>ℝ d</inf>a(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
Journal articlePermalink
https://hdl.handle.net/10161/11655Published Version (Please cite this version)
10.1137/140997658Publication Info
Li, Yingzhou; Yang, Haizhao; & Ying, Lexing (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
More Info
Show full item recordScholars@Duke
Yingzhou Li
Phillip Griffiths Assistant Research Professor
This author no longer has a Scholars@Duke profile, so the information shown here reflects
their Duke status at the time this item was deposited.
Haizhao Yang
Instructor* of Mathematics
Alphabetical list of authors with Scholars@Duke profiles.

Articles written by Duke faculty are made available through the campus open access policy. For more information see: Duke Open Access Policy
Rights for Collection: Scholarly Articles
Works are deposited here by their authors, and represent their research and opinions, not that of Duke University. Some materials and descriptions may include offensive content. More info