Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

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
Posted: February 7, 2012
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 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

[BB00] Samit Basu and Yoram Bresler, 𝑂(𝑁²𝑙𝑜𝑔₂𝑁) filtered backprojection reconstruction algorithm for tomography, IEEE Trans. Image Process. 9 (2000), no. 10, 1760–1773. MR 1807567 (2001j:92020), http://dx.doi.org/10.1109/83.869187
[BL10] Mark Lyon and Oscar P. Bruno, High-order unconditionally stable FC-AD solvers for general smooth domains. II. Elliptic, parabolic and hyperbolic PDEs; theoretical considerations, J. Comput. Phys. 229 (2010), no. 9, 3358–3381. MR 2601104 (2011b:76072), http://dx.doi.org/10.1016/j.jcp.2010.01.006
[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), http://dx.doi.org/10.1137/S1064827593258279
[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), http://dx.doi.org/10.1016/j.wavemoti.2004.05.008
[CD03] Emmanuel Candès and Laurent Demanet, Curvelets and Fourier integral operators, C. R. Math. Acad. Sci. Paris 336 (2003), no. 5, 395–398 (English, with English and French summaries). MR 1979352 (2004d:42059), http://dx.doi.org/10.1016/S1631-073X(03)00095-5
[CD05] Emmanuel J. Candès and Laurent Demanet, The curvelet representation of wave propagators is optimally sparse, Comm. Pure Appl. Math. 58 (2005), no. 11, 1472–1528. MR 2165380 (2006f:35165), http://dx.doi.org/10.1002/cpa.20078
[CDY07] Emmanuel Candès, Laurent Demanet, and Lexing Ying, Fast computation of Fourier integral operators, SIAM J. Sci. Comput. 29 (2007), no. 6, 2464–2493. MR 2357623 (2008i:35261), http://dx.doi.org/10.1137/060671139
[CDY09] Emmanuel Candès, Laurent Demanet, and Lexing Ying, A fast butterfly algorithm for the computation of Fourier integral operators, Multiscale Model. Simul. 7 (2009), no. 4, 1727–1750. MR 2539196 (2010k:65312), http://dx.doi.org/10.1137/080734339
[CF78] Antonio Córdoba and Charles Fefferman, Wave packets and Fourier integral operators, Comm. Partial Differential Equations 3 (1978), no. 11, 979–1005. MR 507783 (80a:35117), http://dx.doi.org/10.1080/03605307808820083
[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] Maarten V. de Hoop, Jérôme H. Le Rousseau, and Ru-Shan Wu, Generalization of the phase-screen approximation for the scattering of acoustic waves, Wave Motion 31 (2000), no. 1, 43–70. MR 1729711 (2000i:76114), http://dx.doi.org/10.1016/S0165-2125(99)00026-8
[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), http://dx.doi.org/10.1137/0914081
[Dui96] J. J. Duistermaat, Fourier integral operators, Progress in Mathematics, vol. 130, Birkhäuser Boston Inc., Boston, MA, 1996. MR 1362544 (96m:58245)
[DY09] Laurent Demanet and Lexing Ying, Wave atoms and time upscaling of wave equations, Numer. Math. 113 (2009), no. 1, 1–71. MR 2511758 (2010d:65272), http://dx.doi.org/10.1007/s00211-009-0226-6
[DY11] -, Discrete symbol calculus, SIAM Review 53 (2011), 71-104.
[EOZ94] Björn Engquist, Stanley Osher, and Sifen Zhong, Fast wavelet based algorithms for linear evolution equations, SIAM J. Sci. Comput. 15 (1994), no. 4, 755–775. MR 1278000 (95a:65146), http://dx.doi.org/10.1137/0915048
[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), http://dx.doi.org/10.1023/A:1019150005407
[JMRY03] Lin Ji, R. McLaughlin, Daniel Renzi, and Jeong-Rock Yoon, Interior elastodynamics inverse problems: shear wave speed reconstruction in transient elastography, Inverse Problems 19 (2003), no. 6, S1–S29. Special section on imaging. MR 2036518 (2005c:35291), http://dx.doi.org/10.1088/0266-5611/19/6/051
[Lax57] Peter D. 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 (2011h:65272), http://dx.doi.org/10.1016/j.acha.2009.08.005
[RT07] Michael Ruzhansky and Ville Turunen, On the Fourier analysis of operators on the torus, Modern trends in pseudo-differential operators, Oper. Theory Adv. Appl., vol. 172, Birkhäuser, Basel, 2007, pp. 87–105. MR 2308505 (2008b:35165), http://dx.doi.org/10.1007/978-3-7643-8116-5_5
[See67] R. T. Seeley, Complex powers of an elliptic operator, Singular Integrals (Proc. Sympos. Pure Math., Chicago, Ill., 1966) Amer. Math. Soc., Providence, R.I., 1967, pp. 288–307. MR 0237943 (38 #6220)
[Smi98] Hart F. Smith, A parametrix construction for wave equations with 𝐶^{1,1} coefficients, Ann. Inst. Fourier (Grenoble) 48 (1998), no. 3, 797–835 (English, with English and French summaries). MR 1644105 (99h:35119)
[Sog93] Christopher D. Sogge, Fourier integrals in classical analysis, Cambridge Tracts in Mathematics, vol. 105, Cambridge University Press, Cambridge, 1993. MR 1205579 (94c:35178)
[SSS91] Andreas Seeger, Christopher D. Sogge, and Elias M. Stein, Regularity properties of Fourier integral operators, Ann. of Math. (2) 134 (1991), no. 2, 231–251. MR 1127475 (92g:35252), http://dx.doi.org/10.2307/2944346
[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] Christiaan C. Stolk, A fast method for linear waves based on geometrical optics, SIAM J. Numer. Anal. 47 (2009), no. 2, 1168–1194. MR 2485449 (2010k:76105), http://dx.doi.org/10.1137/070698919
[Sym90] William W. Symes, Velocity inversion: A case study in infinite-dimensional optimization, Math. Programming 48 (1990), no. 1, (Ser. B), 71–102. MR 1553009, http://dx.doi.org/10.1007/BF01582252
[Sym98] -, Mathematical foundations of reflection seismology, Tech. report, Rice University, 1998.
[Tre80] François Trèves, Introduction to pseudodifferential and Fourier integral operators. Vol. 2, Plenum Press, New York, 1980. Fourier integral operators; The University Series in Mathematics. MR 597145 (82i:58068)
[Tur00] V. Turunen, Commutator characterization of periodic pseudodifferential operators, Z. Anal. Anwendungen 19 (2000), no. 1, 95–108. MR 1748052 (2001d:35203)
[Tyg09] Mark Tygert, Fast algorithms for spherical harmonic expansions, III, J. Comput. Phys. 229 (2010), no. 18, 6181–6192. MR 2660300 (2011h:65005), http://dx.doi.org/10.1016/j.jcp.2010.05.004
[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] Lexing Ying and Sergey Fomel, Fast computation of partial Fourier transforms, Multiscale Model. Simul. 8 (2009), no. 1, 110–124. MR 2575047 (2011a:65469), http://dx.doi.org/10.1137/080715457
[Yin09] Lexing Ying, Sparse Fourier transform via butterfly algorithm, SIAM J. Sci. Comput. 31 (2009), no. 3, 1678–1694. MR 2491541 (2009m:65273), http://dx.doi.org/10.1137/08071291X

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|