Wave atoms and time upscaling of wave equations

We present a new geometric strategy for the numerical solution of hyperbolic wave equations in smoothly varying, two-dimensional time-independent periodic media. The method consists in representing the time-dependent Green’s func-tion in wave atoms, a tight frame of multiscale, directional wave packets obeying a precise parabolic balance between oscillations and support size, namely wavelength ∼(diameter).2 Wave atoms offer a uniquely structured representation of the Green’s function in the sense that • the resulting matrix is universally sparse over the class of C ∞ coefficients, even for “large ” times; • the matrix has a natural low-rank block-structure after separation of the spatial indices. The parabolic scaling is essential for these properties to hold. As a result, it becomes realistic to accurately build the full matrix exponential in the wave atom frame, using repeated squaring up to some time typically of the form t ∼ √x, which is bigger than the standard CFL timestep. Once the “expensive ” precomputation of the Green’s function has been carried out, it can be used to perform unusually large, upscaled, “cheap ” time steps. The algorithm is relatively simple in that it does not require an underlying geometric optics solver. We prove accuracy and complexity results based on a priori estimates of sparsity and separation ranks. On a N-by-N grid, the “expen-sive ” precomputation takes somewhere between O(N 3 log N) and O(N 4 log N) step