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

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?)

  • [BB00] S. Basu and Y. Bresler, $ O(N^2 \log N)$ filtered backprojection algorithm for tomography, IEEE Trans. Im. Proc. 9 (2000), no. 10, 1760-1773. MR 1807567 (2001j:92020)
  • [BL10] O. Bruno and M. Lyon, High-order unconditionally stable FC-AD solvers for general smooth domains I. basic elements, J. Comput. Phys. 229 (2010), no. 9, 3358-3381. MR 2601104 (2011b:76072)
  • [BS96] Gang Bao and William W. Symes, Computation of pseudo-differential operators, SIAM J. Sci. Comput. 17 (1996), no. 2, 416-429. MR 1374288 (96j:65152)
  • [BS05] G. Beylkin and K. Sandberg, Wave propagation using bases for bandlimited functions, Wave Motion 41 (2005), no. 3, 263-291. MR 2120171 (2005i:76097)
  • [CD03] Emmanuel Candès and Laurent Demanet, Curvelets and Fourier integral operators, C. R. Math. Acad. Sci. Paris 336 (2003), no. 5, 395-398. MR 1979352 (2004d:42059)
  • [CD05] -, The curvelet representation of wave propagators is optimally sparse, Comm. Pure Appl. Math. 58 (2005), no. 11, 1472-1528. MR 2165380 (2006f:35165)
  • [CDY07] Emmanuel Candès, Laurent Demanet, and Lexing Ying, Fast computation of Fourier integral operators, SIAM Journal on Scientific Computing 29 (2007), no. 6, 2464-2493. MR 2357623 (2008i:35261)
  • [CDY09] -, A fast butterfly algorithm for the computation of fourier integral operators, SIAM Multiscale Model. Simul. 7 (2009), no. 4, 1727-1750. MR 2539196 (2010k:65312)
  • [CF78] A. Córdoba and C. Fefferman, Wave packets and Fourier integral operators, Comm. PDE 3 (1978), no. 11, 979-1005. MR 507783 (80a:35117)
  • [CMSJ01] W.C. Chew, E. Michielssen, J. M. Song, and J. M. Jin (eds.), Fast and efficient algorithms in computational electromagnetics, Artech House, Inc., Norwood, MA, USA, 2001.
  • [dHlRW00] M. V. de Hoop, J. le Rousseau, and R. Wu, Generlization of the phase-screen approximation for the scattering of acoustic waves, Wave Motion 31 (2000), no. 1, 43-70. MR 1729711 (2000i:76114)
  • [DR93] A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput. 14 (1993), no. 6, 1368-1393. MR 1241591 (95d:65114)
  • [Dui96] J. Duistermaat, Fourier integral operators, Birkhauser, Boston, 1996. MR 1362544 (96m:58245)
  • [DY09] L. Demanet and L. Ying, Wave atoms and time upscaling of wave equations, Numer. Math. 113 (2009), no. 1, 1-71. MR 2511758 (2010d:65272)
  • [DY11] -, Discrete symbol calculus, SIAM Review 53 (2011), 71-104.
  • [EOZ94] B. Engquist, S. Osher, and S. Zhong, Fast wavelet based algorithms for linear evolution equations, SIAM J. Sci. Comput. 15 (1994), no. 4, 755-775. MR 1278000 (95a:65146)
  • [Hö85] L. Hörmander, The analysis of linear partial differential operators, 4 volumes, Springer, 1985.
  • [Hig97] Nicholas J. Higham, Stable iterations for the matrix square root, Numer. Algorithms 15 (1997), no. 2, 227-242. MR 1475179 (98d:65055)
  • [JMRY03] L. Ji, J. R. McLaughlin, D. Renzi, and J-R. Yoon, Interior elastodynamics inverse problems: shear wave speed reconstruction in transient elastography, Inverse Problems 19 (2003), S1-S29. MR 2036518 (2005c:35291)
  • [Lax57] P. Lax, Asymptotic solutions of oscillatory initial value problems, Duke Math J. 24 (1957), 627-646. MR 0097628 (20:4096)
  • [MB96] E. Michielssen and A. Boag, A multilevel matrix decomposition algorithm for analyzing scattering from large structures, IEEE Transactions on Antennas and Propagation 44 (1996), no. 8, 1086-1093.
  • [NA98] S. Nilsson and L.E. Andersson, Application of fast backprojection techniques for some inverse problems of synthetic aperture radar, Proc. SPIE 3370 (1998), 62-72.
  • [OWR10] Michael O'Neil, Franco Woolfe, and Vladimir Rokhlin, An algorithm for the rapid evaluation of special function transforms, Appl. Comput. Harmon. Anal. 28 (2010), no. 2, 203-226. MR 2595885
  • [RT07] M. Ruzhansky and V. Turunen, On the Fourier analysis of operators on the torus, Operator Theory: Advances and Applications 172 (2007), 87-105. MR 2308505 (2008b:35165)
  • [See67] R. T. Seeley, Complex powers of an elliptic operator, Proc. Symp. Pure Math 10 (1967), 288-307. MR 0237943 (38:6220)
  • [Smi98] H. Smith, A parametrix construction for wave equations with $ C^{1,1}$ coefficients, Ann. Inst. Fourier (Grenoble) 48 (1998), 797-835. MR 1644105 (99h:35119)
  • [Sog93] C. Sogge, Fourier integrals in classical analysis, Cambridge University Press, 1993. MR 1205579 (94c:35178)
  • [SSS91] A. Seeger, C. Sogge, and E. Stein, Regularity properties of Fourier integral operators, Annals of Math. 134 (1991), 231-251. MR 1127475 (92g:35252)
  • [Ste93] Elias M. Stein, Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, Princeton Mathematical Series, vol. 43, Princeton University Press, Princeton, NJ, 1993, With the assistance of Timothy S. Murphy, Monographs in Harmonic Analysis, III. MR 1232192 (95c:42002)
  • [Sto09] C. C. Stolk, A fast method for linear waves based on geometrical optics, SIAM J. Num. Anal. 47 (2009), no. 2, 1168-1194. MR 2485449 (2010k:76105)
  • [Sym90] W. W. Symes, Velocity inversion: a case study in infinite-dimensional optimization, Mathematical Programming: Series A and B 48 (1990), no. 1, 71-102. MR 1553009
  • [Sym98] -, Mathematical foundations of reflection seismology, Tech. report, Rice University, 1998.
  • [Tre80] F. Treves, Introduction to pseudodifferential and fourier integral operators, Plenum Press, New York, 1980. MR 597145 (82i:58068)
  • [Tur00] V. Turunen, Commutator characterization of periodic pseudodifferential operators, Z. Anal. Anw. 19 (2000), 95-108. MR 1748052 (2001d:35203)
  • [Tyg09] M. Tygert, Fast algorithms for spherical harmonic expansions, III, Tech. report, New York University, 2009. MR 2660300
  • [UHS03] L. Ulander, H. Hellsten, and G. Stenstrom, Synthetic-aperture radar processing using fast factorized back-projection, IEEE Trans. Aero. Elect. Systems 39 (2003), no. 3, 760-776.
  • [YF09] L. Ying and S. Fomel, Fast computation of partial Fourier transforms, SIAM Multiscale Model. Simul. 8 (2009), 110-124. MR 2575047 (2011a:65469)
  • [Yin09] Lexing Ying, Sparse Fourier transform via butterfly algorithm, SIAM J. Sci. Comput. 31 (2009), no. 3, 1678-1694. MR 2491541 (2009m:65273)

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.

American Mathematical Society