Fast wave computation via Fourier integral operators, submitted

Abstract. This paper presents a numerical method for “time upscaling ” wave equations, i.e., performing time steps not limited by the Courant-Friedrichs-Lewy (CFL) condition. The proposed method leverages recent work on fast algorithms for pseudodifferential and Fourier integral operators (FIO). This algorithmic approach is not asymptotic: it is shown how to construct an ex-act FIO propagator by 1) solving Hamilton-Jacobi equations for the phases, and 2) sampling rows and columns of low-rank matrices at random for the amplitudes. The setting of interest is that of scalar waves in two-dimensional smooth periodic media (of class C ∞ over the torus), where the bandlimit N of the waves goes to infinity. In this setting, it is demonstrated that the al-gorithmic complexity for solving the wave equation to fixed time T 1 can be as low as O(N2 logN) with controlled accuracy. Numerical experiments show that the time complexity can be lower than that of a spectral method in certain situations of physical interest. 1