  This paper presents an efficient multiscale butterfly algorithm for computing
Fourier integral operators (FIOs) of the form $(\mathcal{L} f)(x) =
\int_{R^d}a(x,\xi) e^{2\pi \i \Phi(x,\xi)}\hat{f}(\xi) d\xi$, where
$\Phi(x,\xi)$ is a phase function, $a(x,\xi)$ 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,\xi) e^{2\pi \i
\Phi(x,\xi)}$ 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.
