×

Acoustic inverse scattering via Helmholtz operator factorization and optimization. (English) Zbl 1201.65193

Summary: We present a joint acoustic/seismic inverse scattering and finite-frequency (reflection) tomography program, formulated as a coupled set of optimization problems, in terms of inhomogeneous Helmholtz equations. We use a higher order finite difference scheme for these Helmholtz equations to guarantee sufficient accuracy.
We adapt a structured approximate direct solver for the relevant systems of algebraic equations, which addresses storage requirements through compression, to yield a complexity for computing the gradients or images in the optimization problems that consists of two parts, viz., the cost for all the matrix factorizations which is roughly \(\mathcal O(rN)\) (for example \(\mathcal O(rN \log N)\) when \(d = 2\)) times the number of frequencies, and the cost for all solutions by substitution which is roughly \(\mathcal O(N)\) (for example \(\mathcal O(N \log (r \log N)) \) when \(d = 2\)) times the number of frequencies times the number of sources (events), where \(N = n^d\) if \(n\) is the number of grid samples in any direction, and \(r\) is a parameter depending on the preset accuracy and the problem at hand. With this complexity, the multi-frequency approach to inverse scattering and finite-frequency tomography becomes computationally feasible with large data sets, in dimensions \(d = 2\) and 3.

MSC:

65N06 Finite difference methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
78A46 Inverse problems (including inverse scattering) in optics and electromagnetic theory
86A15 Seismology (including tsunami modeling), earthquakes
76Q05 Hydro- and aero-acoustics

Software:

JDQZ; JDQR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Marfurt, K., Accuracy of finite-difference and finite-element modeling of the scalar and elastic wave equations, Geophysics, 49, 533-549 (1984)
[2] J. Xia, M. Gu, Robust structured multifrontal factorization and preconditioning for discretized PDEs, preprint, <http://math.purdue.edu/∼;xiaj/work/mfhssr.pdf; J. Xia, M. Gu, Robust structured multifrontal factorization and preconditioning for discretized PDEs, preprint, <http://math.purdue.edu/∼;xiaj/work/mfhssr.pdf
[3] J. Xia, M. Gu, Robust structured factorization and preconditioning for spd matrices, SIAM J. Matrix Anal. Appl., <http://math.purdue.edu/∼;xiaj/work/schurmonospd.pdf>; J. Xia, M. Gu, Robust structured factorization and preconditioning for spd matrices, SIAM J. Matrix Anal. Appl., <http://math.purdue.edu/∼;xiaj/work/schurmonospd.pdf>
[4] Elman, H.; Ernst, O.; O’Leary, D., A multigrid method enhanced by krylov subspace iteration for discrete helmholtz equations, SIAM J. Scient. Comp., 23, 1291-1315 (2001) · Zbl 1004.65134
[5] Plessix, R.-E., A helmholtz iterative solver for 3D seismic-imaging problems, Geophysics, 72, SM185-SM194 (2007)
[6] Erlangga, Y.; Vuik, C.; Oosterlee, C., On a class of preconditioners for solving the helmholtz equation, Appl. Numer. Math., 50, 409-425 (2004) · Zbl 1051.65101
[7] Erlangga, Y.; Oosterlee, C.; Vuik, C., A novel multigrid based preconditioner for heterogeneous helmholtz problems, SIAM J. Scient. Comput., 27, 1471-1492 (2006) · Zbl 1095.65109
[8] Riyanti, C.; Erlangga, Y.; Plessix, R.-E.; Mulder, W.; Vuik, C.; Oosterlee, C., A new iterative solver for the time-harmonic wave equation, Geophysics, 71, E57-E63 (2006)
[9] Operto, S.; Virieux, J.; Amestoy, P.; L’Excellent, J.; Giraud, L.; Hadj Ali, H., A helmholtz iterative solver for 3D seismic-imaging problems, Geophysics, 72, SM185-SM194 (2007)
[10] Larsson, E., A domain decomposition method for the helmholtz equation in a multilayer domain, SIAM J. Scient. Comp., 20, 1713-1731 (1999) · Zbl 0936.65140
[11] Sirgue, L.; Pratt, R., Efficient waveform inversion and imaging: a strategy for selecting temporal frequencies, Geophysics, 69, 231-248 (2004)
[12] Mulder, W.; Plessix, R.-E., How to choose a subset of frequencies in frequency-domain finite-difference migration, Geophys. J. Int., 158, 801-812 (2004)
[13] Shin, C.; Ha, W., A comparison between the behavior of objective functions for waveform inversion in the frequency and laplace domains, Geophysics, 73, VE119-VE133 (2008)
[14] Virieux, J.; Operto, S., An overview of full-waveform inversion in exploration geophysics, Geophysics, 74, WCC1-WCC26 (2009)
[15] Lailly, P., The seismic inverse problem as a sequence of before stack migrations, (Proceedings of the International Conference on Inverse Scattering, Theory and Applications (1983), SIAM: SIAM Tulsa, OK), 206-220
[16] Tarantola, A., Inverse Problem Theory (1987), Elsevier: Elsevier New York
[17] Kühl, H.; Sacchi, M., Least-squares wave-equation migration for avp/ava inversion, Geophysics, 68, 262-273 (2003)
[18] Pratt, R., Seismic waveform inversion in the frequency domain, part 1: Theory and verification in a physical scale model, Geophysics, 64, 888-901 (1999)
[19] Ravaut, C.; Operto, S.; Improta, L.; Virieux, J.; Herrero, A.; Dell’Aversana, P., Multiscale imaging of complex structures from multifold wide-aperture seismic data by frequency-domain full-waveform tomography: application to a thrust belt, Geophys. J. Int., 159, 1032-1056 (2004)
[20] Stolk, C.; De Hoop, M., Microlocal analysis of seismic inverse scattering in anisotropic elastic media, Commun. Pure Appl. Math., 55, 261-301 (2002) · Zbl 1018.86002
[21] De Hoop, M.; Van der Hilst, R.; Shen, P., Wave-equation reflection tomography: annihilators and sensitivity kernels, Geophys. J. Int., 167, 1332-1352 (2006)
[22] Xie, X.; Yang, H., The finite-frequency sensitivity kernel for migration residual moveout and its applications in migration velocity analysis, Geophysics, 73, S241-S249 (2008)
[23] Duchkov, A.; De Hoop, M.; Sá Barreto, A., Evolution-equation approach to seismic image, and data, continuation, Wave Motion, 45, 952-969 (2008) · Zbl 1231.86010
[24] S. Wang, M. De Hoop, Illumination analysis of wave-equation imaging with “curvelets”, submitted for publication.; S. Wang, M. De Hoop, Illumination analysis of wave-equation imaging with “curvelets”, submitted for publication. · Zbl 1204.35180
[25] V. Brytik, M. De Hoop, M. Salo, Sensitivity analysis of wave equation tomography: a multi-scale approach, Journal of Fourier Analysis and Applications, submitted for publication.; V. Brytik, M. De Hoop, M. Salo, Sensitivity analysis of wave equation tomography: a multi-scale approach, Journal of Fourier Analysis and Applications, submitted for publication. · Zbl 1200.35180
[26] W.W. Symes, Lecture notes: Short Course on Mathematical Foundations of Reflection Seismology, T.R.I.P. consortium.; W.W. Symes, Lecture notes: Short Course on Mathematical Foundations of Reflection Seismology, T.R.I.P. consortium.
[27] Stolk, C.; De Hoop, M.; Symes, W., Kinematics of shot-geophone migration, Geophysics, 74, WCA19-WCA34 (2009)
[28] Nolan, C.; Symes, W., Global solution of a linearized inverse problem for the wave equation, Commun. Partial Differ. Equat., 22, 919-952 (1997) · Zbl 0889.35122
[29] Levy, B.; Esmersoy, C., Variable background born inversion by wavefield backpropagation, SIAM J. Appl. Math., 48, 952-972 (1988) · Zbl 0673.35100
[30] C. Stolk, M. De Hoop, T. Op’t Root, Inverse scattering of seismic data in the reverse time migration (rtm) approach, <http://www.math.purdue.edu/∼;mdehoop/10_topics/rtm.pdf>; C. Stolk, M. De Hoop, T. Op’t Root, Inverse scattering of seismic data in the reverse time migration (rtm) approach, <http://www.math.purdue.edu/∼;mdehoop/10_topics/rtm.pdf> · Zbl 1273.86015
[31] Zhao, L.; Jordan, T.; Chapman, C., Three-dimensional fréchet differential kernels for seismic delay times, Geophys. J. Int., 141, 558-576 (2000)
[32] De Hoop, M.; Van der Hilst, R., On sensitivity kernels for ‘wave-equation’ transmission tomography, Geophys. J. Int., 160, 621-633 (2005)
[33] Liu, Q.; Tromp, J., Finite-frequency kernels based upon adjoint methods, Bull. Seism. Soc. Amer., 96, 2383-2397 (2006)
[34] Turkel, E.; Yefet, A., Absorbing pml boundary layers for wave-like equations, Appl. Numer. Math., 27, 533-557 (1998) · Zbl 0933.35188
[35] Singer, I.; Turkel, E., A perfectly matched layer for the Helmholtz equation in a semi-infinite strip, J. Comput. Phys., 201, 439-465 (2004) · Zbl 1061.65109
[36] Bamberger, A.; Joly, P.; Roberts, J., Second-order absorbing boundary conditions for the wave equation: a solution for the corner problem, SIAM J. Numer. Anal., 27, 323-352 (1990) · Zbl 0716.35036
[37] Singer, I.; Turkel, E., High-order finite difference methods for the Helmholtz equation, Comput. Methods Appl. Mech. Eng., 163, 343-358 (1998) · Zbl 0940.65112
[38] Lele, S., Compact finite difference schemes with spectral-like resolution, J. Comput. Phys., 103, 16-42 (1992) · Zbl 0759.65006
[39] Bai, Z.; Demmel, J.; Dongarra, J.; Ruhe, A.; Van den Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (2000), SIAM: SIAM Philadelphia, PA
[40] Saad, Y., Iterative methods for sparse linear systems (2003), SIAM: SIAM Philadelpha, PA · Zbl 1002.65042
[41] Xia, J.; Chandrasekaran, S.; Gu, M.; Li, X., Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31, 1382-1411 (2009) · Zbl 1195.65031
[42] George, J., Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10, 345-363 (1973) · Zbl 0259.65087
[43] Hoffman, A.; Martin, M.; Rose, D., Complexity bounds for regular finite difference and finite element grids, SIAM J. Numer. Anal., 10, 364-369 (1973) · Zbl 0261.65026
[44] Duff, I.; Reid, J., The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Softw., 9, 302-325 (1983) · Zbl 0515.65022
[45] Liu, J., The multifrontal method for sparse matrix solution: theory and practice, SIAM Rev., 34, 82-109 (1992) · Zbl 0919.65019
[46] Eisenstat, S.; Liu, J., The theory of elimination trees for sparse unsymmetric matrices, SIAM J. Matrix Anal. Appl., 26, 686-705 (2005) · Zbl 1079.65025
[47] Gilbert, E. N.J. R., Predicting Structure in Nonsymmetric Sparse Matrix Factorizations: Graph Theory and Sparse Matrix Computation (1993), Springer-Verlag
[48] Liu, J., The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl., 18, 134-172 (1990) · Zbl 0697.65013
[49] Schreiber, R., A new implementation of sparse gaussian elimination, ACM Trans. Math. Softw., 8, 256-276 (1982) · Zbl 0491.65013
[50] Eisenstat, S. C.; Liu, J. W.H., A tree based dataflow model for the unsymmetric multifrontal method, Electron. Trans. Numer. Anal., 21, 1-19 (2005) · Zbl 1120.65316
[51] Amestoy, P.; Puglisi, C., An unsymmetrized multifrontal lu factorization, SIAM J. Matrix Anal. Appl., 24, 553-569 (2002) · Zbl 1017.65017
[52] Bebendorf, M., Efficient inversion of galerkin matrices of general second-order elliptic differential operators with nonsmooth coefficients, Math. Comp., 74, 1179-1199 (2005) · Zbl 1330.65173
[53] Bebendorf, M.; Hackbusch, W., Existence of \(H\)-matrix approximants to the inverse fe-matrix of elliptic operators with \(l^∞\) coefficients, Numer. Math., 95, 1-28 (2003) · Zbl 1033.65100
[54] Chandrasekaran, S.; Dewilde, P.; Gu, M.; Somasunderam, N., On the numerical rank of the off-diagonal blocks of schur complements of discretized elliptic PDES, SIAM J. Matrix Anal. Appl., 31, 2261-2290 (2010) · Zbl 1209.65032
[55] Chandrasekaran, S.; Dewilde, P.; Gu, M.; Lyons, W.; Pals, T., A fast solver for HSS representations via sparse matrices, SIAM J. Matrix Anal. Appl., 29, 67-81 (2006) · Zbl 1135.65317
[56] J. Xia, S. Chandrasekaran, M. Gu, X. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl. (2010), in press, doi:10.1002/nla.691; J. Xia, S. Chandrasekaran, M. Gu, X. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl. (2010), in press, doi:10.1002/nla.691 · Zbl 1240.65087
[57] Chandrasekaran, S.; Gu, M.; Pals, T., A fast ulv decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl., 28, 603-622 (2006) · Zbl 1120.65031
[58] Erlangga, Y.; Herrmann, F., An iterative multilevel method for computing wavefields in frequency-domain seismic inversion, SEG Tech. Prog. Expanded Abstr., 27, 1956-1960 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.