Fast wave computation via Fourier integral operators
HTML articles powered by AMS MathViewer
- by Laurent Demanet and Lexing Ying PDF
- Math. Comp. 81 (2012), 1455-1486 Request permission
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
- Samit Basu and Yoram Bresler, $O(N^2\log _2N)$ filtered backprojection reconstruction algorithm for tomography, IEEE Trans. Image Process. 9 (2000), no. 10, 1760–1773. MR 1807567, DOI 10.1109/83.869187
- 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, DOI 10.1016/j.jcp.2010.01.006
- Gang Bao and William W. Symes, Computation of pseudo-differential operators, SIAM J. Sci. Comput. 17 (1996), no. 2, 416–429. MR 1374288, DOI 10.1137/S1064827593258279
- G. Beylkin and K. Sandberg, Wave propagation using bases for bandlimited functions, Wave Motion 41 (2005), no. 3, 263–291. MR 2120171, DOI 10.1016/j.wavemoti.2004.05.008
- 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, DOI 10.1016/S1631-073X(03)00095-5
- 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, DOI 10.1002/cpa.20078
- 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, DOI 10.1137/060671139
- 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, DOI 10.1137/080734339
- Antonio Córdoba and Charles Fefferman, Wave packets and Fourier integral operators, Comm. Partial Differential Equations 3 (1978), no. 11, 979–1005. MR 507783, DOI 10.1080/03605307808820083
- 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.
- 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, DOI 10.1016/S0165-2125(99)00026-8
- A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput. 14 (1993), no. 6, 1368–1393. MR 1241591, DOI 10.1137/0914081
- J. J. Duistermaat, Fourier integral operators, Progress in Mathematics, vol. 130, Birkhäuser Boston, Inc., Boston, MA, 1996. MR 1362544
- Laurent Demanet and Lexing Ying, Wave atoms and time upscaling of wave equations, Numer. Math. 113 (2009), no. 1, 1–71. MR 2511758, DOI 10.1007/s00211-009-0226-6
- —, Discrete symbol calculus, SIAM Review 53 (2011), 71–104.
- 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, DOI 10.1137/0915048
- L. Hörmander, The analysis of linear partial differential operators, 4 volumes, Springer, 1985.
- Nicholas J. Higham, Stable iterations for the matrix square root, Numer. Algorithms 15 (1997), no. 2, 227–242. MR 1475179, DOI 10.1023/A:1019150005407
- 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, DOI 10.1088/0266-5611/19/6/051
- Peter D. Lax, Asymptotic solutions of oscillatory initial value problems, Duke Math. J. 24 (1957), 627–646. MR 97628
- 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.
- 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.
- 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, DOI 10.1016/j.acha.2009.08.005
- 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, DOI 10.1007/978-3-7643-8116-5_{5}
- 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
- Hart F. Smith, A parametrix construction for wave equations with $C^{1,1}$ coefficients, Ann. Inst. Fourier (Grenoble) 48 (1998), no. 3, 797–835 (English, with English and French summaries). MR 1644105
- Christopher D. Sogge, Fourier integrals in classical analysis, Cambridge Tracts in Mathematics, vol. 105, Cambridge University Press, Cambridge, 1993. MR 1205579, DOI 10.1017/CBO9780511530029
- 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, DOI 10.2307/2944346
- 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
- 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, DOI 10.1137/070698919
- William W. Symes, Velocity inversion: A case study in infinite-dimensional optimization, Math. Programming 48 (1990), no. 1, (Ser. B), 71–102. MR 1553009, DOI 10.1007/BF01582252
- —, Mathematical foundations of reflection seismology, Tech. report, Rice University, 1998.
- François Trèves, Introduction to pseudodifferential and Fourier integral operators. Vol. 2, University Series in Mathematics, Plenum Press, New York-London, 1980. Fourier integral operators. MR 597145
- V. Turunen, Commutator characterization of periodic pseudodifferential operators, Z. Anal. Anwendungen 19 (2000), no. 1, 95–108. MR 1748052, DOI 10.4171/ZAA/940
- Mark Tygert, Fast algorithms for spherical harmonic expansions, III, J. Comput. Phys. 229 (2010), no. 18, 6181–6192. MR 2660300, DOI 10.1016/j.jcp.2010.05.004
- 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.
- Lexing Ying and Sergey Fomel, Fast computation of partial Fourier transforms, Multiscale Model. Simul. 8 (2009), no. 1, 110–124. MR 2575047, DOI 10.1137/080715457
- Lexing Ying, Sparse Fourier transform via butterfly algorithm, SIAM J. Sci. Comput. 31 (2009), no. 3, 1678–1694. MR 2491541, DOI 10.1137/08071291X
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
- Received by editor(s): July 27, 2011
- Received by editor(s) in revised form: April 11, 2011
- Published electronically: February 7, 2012
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 81 (2012), 1455-1486
- MSC (2010): Primary 65M80, 65T99
- DOI: https://doi.org/10.1090/S0025-5718-2012-02557-9
- MathSciNet review: 2904586