The adaptive Levin method

The Levin method is a classical technique for evaluating oscillatory integrals that operates by solving a certain ordinary differential equation in order to construct an antiderivative of the integrand. It was long believed that the method suffers from ``low-frequency breakdown,'' meaning that the accuracy of the computed integral deteriorates when the integrand is only slowly oscillating. Recently presented experimental evidence suggests that, when a Chebyshev spectral method is used to discretize the differential equation and the resulting linear system is solved via a truncated singular value decomposition, no such phenomenon is observed. Here, we provide a proof that this is, in fact, the case, and, remarkably, our proof applies even in the presence of saddle points. We also observe that the absence of low-frequency breakdown makes the Levin method suitable for use as the basis of an adaptive integration method. We describe extensive numerical experiments demonstrating that the resulting adaptive Levin method can efficiently and accurately evaluate a large class of oscillatory integrals, including many with saddle points.