Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast wave computation via Fourier integral operators

Authors: Laurent Demanet and Lexing Ying
Journal: Math. Comp. 81 (2012), 1455-1486
MSC (2010): Primary 65M80, 65T99
Published electronically: February 7, 2012
MathSciNet review: 2904586
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 exact 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^\infty $ over the torus), where the bandlimit $ N$ of the waves goes to infinity. In this setting, it is demonstrated that the algorithmic complexity for solving the wave equation to fixed time $ T \simeq 1$ can be as low as $ O(N^2 \log N)$ 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65M80, 65T99

Retrieve articles in all journals with MSC (2010): 65M80, 65T99

Additional Information

Laurent Demanet
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Lexing Ying
Affiliation: Department of Mathematics and ICES, The University of Texas at Austin, Austin, Texas 78712

Keywords: Wave equations, Fourier integral operators, discrete symbol calculus, random sampling, separated approximation, multiscale computations.
Received by editor(s): July 27, 2011
Received by editor(s) in revised form: April 11, 2011
Published electronically: February 7, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.