  Starting from the Kirchhoff-Huygens representation and Duhamel's principle of
time-domain wave equations, we propose novel butterfly-compressed Hadamard
integrators for self-adjoint wave equations in both time and frequency domain
in an inhomogeneous medium. First, we incorporate the leading term of
Hadamard's ansatz into the Kirchhoff-Huygens representation to develop a
short-time valid propagator. Second, using the Fourier transform in time, we
derive the corresponding Eulerian short-time propagator in frequency domain; on
top of this propagator, we further develop a time-frequency-time (TFT) method
for the Cauchy problem of time-domain wave equations. Third, we further propose
the time-frequency-time-frequency (TFTF) method for the corresponding
point-source Helmholtz equation, which provides Green's functions of the
Helmholtz equation for all angular frequencies within a given frequency band.
Fourth, to implement TFT and TFTF methods efficiently, we introduce butterfly
algorithms to compress oscillatory integral kernels at different frequencies.
As a result, the proposed methods can construct wave field beyond caustics
implicitly and advance spatially overturning waves in time naturally with
quasi-optimal computational complexity and memory usage. Furthermore, once
constructed the Hadamard integrators can be employed to solve both time-domain
wave equations with various initial conditions and frequency-domain wave
equations with different point sources. Numerical examples for two-dimensional
wave equations illustrate the accuracy and efficiency of the proposed methods.
