Fast wave computation via Fourier integral operators

Demanet, Laurent; Ying, Lexing

doi:10.1090/S0025-5718-2012-02557-9

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