  We present a butterfly-compressed representation of the Hadamard-Babich (HB)
ansatz for the Green's function of the high-frequency Helmholtz equation in
smooth inhomogeneous media. For a computational domain discretized with $N_v$
discretization cells, the proposed algorithm first solves and tabulates the
phase and HB coefficients via eikonal and transport equations with observation
points and point sources located at the Chebyshev nodes using a set of much
coarser computation grids, and then butterfly compresses the resulting HB
interactions from all $N_v$ cell centers to each other. The overall CPU time
and memory requirement scale as $O(N_v\log^2N_v)$ for any bounded 2D domains
with arbitrary excitation sources. A direct extension of this scheme to bounded
3D domains yields an $O(N_v^{4/3})$ CPU complexity, which can be further
reduced to quasi-linear complexities with proposed remedies. The scheme can
also efficiently handle scattering problems involving inclusions in
inhomogeneous media. Although the current construction of our HB integrator
does not accommodate caustics, the resulting HB integrator itself can be
applied to certain sources, such as concave-shaped sources, to produce caustic
effects. Compared to finite-difference frequency-domain (FDFD) methods, the
proposed HB integrator is free of numerical dispersion and requires fewer
discretization points per wavelength. As a result, it can solve
wave-propagation problems well beyond the capability of existing solvers.
Remarkably, the proposed scheme can accurately model wave propagation in 2D
domains with 640 wavelengths per direction and in 3D domains with 54
wavelengths per direction on a state-the-art supercomputer at Lawrence Berkeley
National Laboratory.
