Sweeping preconditioners for elastic wave propagation with spectral element methods
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 2, p. 433-447
The full text of recent articles is available to journal subscribers only. See the article on the journal's website

We present a parallel preconditioning method for the iterative solution of the time-harmonic elastic wave equation which makes use of higher-order spectral elements to reduce pollution error. In particular, the method leverages perfectly matched layer boundary conditions to efficiently approximate the Schur complement matrices of a block LDLT factorization. Both sequential and parallel versions of the algorithm are discussed and results for large-scale problems from exploration geophysics are presented.

DOI : https://doi.org/10.1051/m2an/2013114
Classification:  65F08,  65N22,  65N80
Keywords: elastic wave, seismic wave, time-harmonic, frequency domain, spectral elements, parallel preconditioner, iterative solver, sparse-direct, perfectly matched layers, full waveform inversion
     author = {Tsuji, Paul and Poulson, Jack and Engquist, Bj\"orn and Ying, Lexing},
     title = {Sweeping preconditioners for elastic wave propagation with spectral element methods},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {2},
     year = {2014},
     pages = {433-447},
     doi = {10.1051/m2an/2013114},
     mrnumber = {3177852},
     language = {en},
     url = {http://www.numdam.org/item/M2AN_2014__48_2_433_0}
Tsuji, Paul; Poulson, Jack; Engquist, Björn; Ying, Lexing. Sweeping preconditioners for elastic wave propagation with spectral element methods. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 2, pp. 433-447. doi : 10.1051/m2an/2013114. http://www.numdam.org/item/M2AN_2014__48_2_433_0/

[1] F. Aminzadeh, J. Brac and T. Kunz, 3-D Salt and Overthrust models. In SEG/EAGE 3-D Modeling Series 1. Tulsa, OK (1997).

[2] J.P. Berenger, A perfectly matched layer for the absorption of electromagnetic waves. J. Comput. Phys. 114 (1994) 185-200. | MR 1294924 | Zbl 0814.65129

[3] J. Bramble and J. Pasciak, A note on the existence and uniqueness of solutions of frequency domain elastic wave problems: a priori estimates in H1. J. Math Anal. Appl. 345 (2008) 396-404. | MR 2422659 | Zbl 1146.35323

[4] W.C. Chew and W.H. Weedon, A 3D perfectly matched medium from modified Maxwell's equations with stretched coordinates. Microwave Optical Tech. Lett. 7 (1994) 599-604.

[5] J. Choi, J.J. Dongarra, R. Pozo and D.W. Walker, ScaLAPACK: A scalable linear algebra library for distributed memory concurrent computers, in Proc. of the Fourth Symposium on the Frontiers of Massively Parallel Computation, IEEE Comput. Soc. Press(1992) 120-127. | Zbl 0926.65148

[6] B. Engquist and L. Ying, Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation. Commun. Pure Appl. Math. 64 (2011) 697-735. | MR 2789492 | Zbl 1229.35037

[7] B. Engquist and L. Ying, Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers. Multiscale Model. Simul. 9 (2011) 686-710. | MR 2818416 | Zbl 1228.65234

[8] Y.A. Erlangga, C. Vuik and C.W. Oosterlee, On a class of preconditioners for solving the Helmholtz equation. Appl. Numer. Math. 50 (2004) 409-425. | MR 2074012 | Zbl 1051.65101

[9] O.G. Ernst and M.J. Gander, Why it is difficult to solve Helmholtz problems with classical iterative methods, in vol. 83 of Numerical Analysis of Multiscale Problems. Edited by I. Graham, T. Hou, O. Lakkis and R. Scheichl. Springer-Verlag (2011) 325-361. | MR 3050918 | Zbl 1248.65128

[10] L. Grasedyck and W. Hackbusch, Construction and arithmetics of ℋ-matrices. Computing 70 (2003) 295-334. | MR 2011419 | Zbl 1030.65033

[11] A. Gupta, G. Karypis and V. Kumar, A highly scalable parallel algorithm for sparse matrix factorization. IEEE Transactions on Parallel and Distributed Systems 8 (1997) 502-520.

[12] A. Gupta, S. Koric and T. George, Sparse matrix factorization on massively parallel computers, in Proc. of the Conference on High Performance Computing, Networking, Storage and Analysis. Portland, OR (2009).

[13] I. Harari and U. Albocher, Studies of FE/PML for exterior problems of time-harmonic elastic waves. Comput. Methods Appl. Mech. Eng. 195 (2006) 3854-3879. | MR 2221777 | Zbl 1119.74048

[14] T. Hughes, The finite element method: linear static and dynamic finite element analysis. Prentice-Hall, Inc. (1987). | MR 1008473 | Zbl 0634.73056

[15] G. Karniadakis, Spectral/hp element methods for CFD. Oxford University Press (1999). | MR 1696933 | Zbl 0954.76001

[16] D. Komatitsch and J. Tromp, Introduction to the spectral element method for three-dimensional seismic wave propagation. Geophys. J. Int. 139 (1999) 806-822.

[17] J. Liu. The multifrontal method for sparse matrix solution: theory and practice. SIAM Review 34 (1992) 82-109. | MR 1156290 | Zbl 0919.65019

[18] A. Patera, A spectral element method for fluid dynamics: laminar flow in a channel expansion. J. Comput. Phys. 54 (1984) 468-488. | Zbl 0535.76035

[19] J. Poulson, B. Engquist, S. Li and L. Ying, A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations e-prints ArXiv (2012). | MR 3048222 | Zbl 1275.65073

[20] J. Poulson, B. Marker, R.A. Van De Geijn, J.R. Hammond and N.A. Romero, Elemental: A new framework for distributed memory dense matrix computations. ACM Trans. Math. Software 39. | MR 3031632 | Zbl 1295.65137

[21] P. Raghavan, Efficient parallel sparse triangular solution with selective inversion. Parallel Proc. Lett. 8 (1998) 29-40. | MR 1632870

[22] Y. Saad and M.H. Schultz, A generalized minimum residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7 (1986) 856-869. | MR 848568 | Zbl 0599.65018

[23] R. Schreiber, A new implementation of sparse Gaussian elimination. ACM Trans. Math. Software 8 (1982) 256-276. | MR 695356 | Zbl 0491.65013

[24] P. Tsuji, B. Engquist and L. Ying, A sweeping preconditioner for time-harmonic Maxwell's equations with finite elements. J. Comput. Phys. 231 (2012) 3770-3783. | MR 2902419 | Zbl 1251.78013

[25] P. Tsuji and L. Ying, A sweeping preconditioner for Yee's finite difference approximation of time-harmonic Maxwell's equations. Frontiers of Mathematics in China 7 (2012) 347-363. | MR 2897708 | Zbl 1253.78049