×

An improved two-grid preconditioner for the solution of three-dimensional Helmholtz problems in heterogeneous media. (English) Zbl 1313.65284

The authors present the new two-grid preconditioner for the solution of realistic three-dimensional heterogeneous Helmholtz problems discretized with second-order finite difference methods with application to acoustic waveform inversion in geophysics as e.g. monitoring of pollution in groundwater, earthquake modelling or location of hydrocarbon in fractured rocks. The homogeneous Helmholtz problems can be solved by efficient multilevel solvers, e.g. by the wave-ray multigrid method or by the FETI-H non-overlapping domain decomposition method whose rate of convergence is found to be independent of the fine grid step size, the number of subdomains, and the wavenumber. This paper focuses to the approximate solution of large indefinite linear systems of equations in the frequency domain being a topic of current research. The new proposed approach is based on an iterative two-grid method acting on the Helmholtz operator where the coarse grid problem is solved inaccurately with preconditioner consisting in a multigrid method cycle applied to a complex shifted Laplacian operator. These efficient algebraic one-level preconditioners are missing in other methods. A single cycle of the new method is then used as a variable preconditioner of a flexible Krylov subspace method whose properties are analysed by means of Fourier analysis giving us also appropriate relaxation parameters in the Jacobi method that lead to acceptable smoothing factors on all the grids of a complex shifted multigrid method in three dimensions. Numerical results demonstrate the effectiveness and robustness of the algorithm on three-dimensional heterogeneous media wave propagation applications even with high frequencies (or equivalently with large wavenumbers causing steep increase in the number of iterations for other methods) on a reasonable number of cores of a distributed memory computer. The paper is written in well understandable English.

MSC:

65N06 Finite difference methods for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs

Software:

MPI; FWT2D
Full Text: DOI

References:

[1] BrandtA, LivshitsI. Wave‐ray multigrid method for standing wave equations. Electronic Transactions on Numerical Analysis1997; 6:162-181. · Zbl 0891.65127
[2] BrandtA, Ta’asanS. Multigrid method for nearly singular and slightly indefinite problems. In Multigrid Methods II, HackbuschW (ed.), TrottenbergU (ed.) (eds). Springer: Berlin Heidelberg, 1986; 99-121. · Zbl 0605.65022
[3] FarhatC, MacedoA, LesoinneM. A two‐level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems. Numerische Mathematik2000; 85:283-308. · Zbl 0965.65133
[4] FarhatC, RouxFX. A method of finite element tearing and interconnecting and its parallel solution algorithm. International Journal for Numerical Methods in Engineering1991; 32:1205-1227. · Zbl 0758.65075
[5] ToselliA, WidlundO. Domain Decomposition Methods ‐ Algorithms and Theory, Springer Series on Computational Mathematics, Vol. 34. Springer: Berlin Heidelberg, 2005. · Zbl 1069.65138
[6] ErlanggaYA. Advances in iterative methods and preconditioners for the Helmholtz equation. Archives of Computational Methods in Engineering2008; 15:37-66. · Zbl 1158.65078
[7] ErnstO, GanderMJ. Why it is difficult to solve Helmholtz problems with classical iterative methods. In Numerical Analysis of Multiscale Problems, GrahamI (ed.), LakkisO (ed.), HouT (ed.), ScheichlR (ed.) (eds), Springer: Berlin Heidelberg, 2011; 325-361.
[8] BaylissA, GoldsteinCI, TurkelE. An iterative method for the Helmholtz equation. Journal of Computational Physics1983; 49:443-457. · Zbl 0524.65068
[9] LairdAL, GilesMB. Preconditioned iterative solution of the 2D Helmholtz equation. Technical Report Report NA‐02/12, Oxford University Computing Laboratory, University of Oxford, United Kingdom, 2002.
[10] ErlanggaYA. A robust and efficient iterative method for the numerical solution of the Helmholtz equation. Ph.D. Thesis, TU Delft, Delft, The Netherlands, 2005.
[11] ErlanggaYA, VuikC, OosterleeC. On a class of preconditioners for solving the Helmholtz equation. Applied Numerical Mathematics2004; 50:409-425. · Zbl 1051.65101
[12] ErlanggaYA, OosterleeC, VuikC. A novel multigrid based preconditioner for heterogeneous Helmholtz problems. SIAM Journal on Scientific Computing2006; 27:1471-1492. · Zbl 1095.65109
[13] vanGijzenMB, ErlanggaYA, VuikC. Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian. SIAM Journal on Scientific Computing2007; 29:1942-1958. · Zbl 1155.65088
[14] RiyantiCD, KononovA, ErlanggaYA, PlessixR‐E, MulderWA, VuikC, OosterleeC. A parallel multigrid‐based preconditioner for the 3D heterogeneous high‐frequency Helmholtz equation. Journal of Computational Physics2007; 224:431-448. · Zbl 1120.65127
[15] BollhöferM, GroteMJ, SchenkO. Algebraic multilevel preconditioner for the solution of the Helmholtz equation in heterogeneous media. SIAM Journal on Scientific Computing2009; 31:3781-3805. · Zbl 1203.65273
[16] ErlanggaYA, NabbenR. On a multilevel Krylov method for the Helmholtz equation preconditioned by shifted Laplacian. Electronic Transactions on Numerical Analysis2008; 31:403-424. · Zbl 1190.65050
[17] SheikhAH, LahayeD, VuikC. A scalable Hemholtz solver combining the shifted Laplace preconditioner with multigrid deflation. Report 11‐01, Delft University of Technology, Delft Institute of Applied Mathematics, Delft, 2011.
[18] ElmanH, ErnstO, O’LearyD, StewartM. Efficient iterative algorithms for the stochastic finite element method with application to acoustic scattering. Computer Methods in Applied Mechanics and Engineering2005; 194(1):1037-1055. · Zbl 1091.76032
[19] ElmanHC, ErnstOG, O’LearyDP. A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations. SIAM Journal on Scientific Computing2001; 23:1291-1315. · Zbl 1004.65134
[20] PinelX. A perturbed two‐level preconditioner for the solution of three‐dimensional heterogeneous Helmholtz problems with applications to geophysics. Ph.D. Thesis, CERFACS, Toulouse, France, 2010. TH/PA/10/55, available at http://www.cerfacs.fr/algor/reports/Dissertations/TH_PA_10_55.pdf [Accessed date on 2010].
[21] StübenK, TrottenbergU. Multigrid methods: fundamental algorithms, model problem analysis and applications. In Multigrid Methods, Koeln‐Porz, 1981, Lecture Notes in Mathematics, Volume 960, HackbuschW (ed.), TrottenbergU (ed.) (eds). Springer: Berlin Heidelberg, 1982; 1-176. · Zbl 0505.65035
[22] CalandraH, GrattonS, LangouJ, PinelX, VasseurX. Flexible variants of block restarted GMRES methods with application to geophysics. SIAM Journal on Scientific Computing2012; 34(2):A714-A736. · Zbl 1248.65036
[23] CalandraH, GrattonS, LagoR, PinelX, VasseurX. Two‐level preconditioned Krylov subspace methods for the solution of three‐dimensional heterogeneous Helmholtz problems in seismics. Numerical Analysis and Applications2012; 5:175-181.
[24] VirieuxJ, OpertoS. An overview of full waveform inversion in exploration geophysics. Geophysics2009; 74(6):WCC127-WCC152.
[25] TarantolaA. Inverse Problem Theory and Methods for Model Parameter Estimation. SIAM: Philadelphia, 2005. · Zbl 1074.65013
[26] BerengerJ‐P. A perfectly matched layer for absorption of electromagnetic waves. Journal of Computational Physics1994; 114:185-200. · Zbl 0814.65129
[27] BerengerJ‐P. Three‐dimensional perfectly matched layer for absorption of electromagnetic waves. Journal of Computational Physics1996; 127:363-379. · Zbl 0862.65080
[28] OpertoS, VirieuxJ, AmestoyPR, L’ExcellentJ‐Y, GiraudL, Ben‐Hadj‐AliH. 3D finite‐difference frequency‐domain modeling of visco‐acoustic wave propagation using a massively parallel direct solver: a feasibility study. Geophysics2007; 72‐5:195-211.
[29] CohenG. Higher‐order Numerical Methods for Transient Wave Equations. Springer: Berlin Heidelberg, 2002. · Zbl 0985.65096
[30] SourbierF, OpertoS, VirieuxJ, AmestoyP, L’ExcellentJY. FWT2D : a massively parallel program for frequency‐domain full‐waveform tomography of wide‐aperture seismic data ‐ part 1: algorithm. Computer & Geosciences2009; 35:487-495.
[31] SourbierF, OpertoS, VirieuxJ, AmestoyP, L’ExcellentJY. FWT2D : a massively parallel program for frequency‐domain full‐waveform tomography of wide‐aperture seismic data ‐ part 2: numerical examples and scalability analysis. Computer & Geosciences2009; 35:496-514.
[32] WangS, deHoopMV, XiaJ. Acoustic inverse scattering via Helmholtz operator factorization and optimization. Journal of Computational Physics2010; 229:8445-8462. · Zbl 1201.65193
[33] WangS, deHoopMV, XiaJ. On 3D modeling of seismic wave propagation via a structured parallel multifrontal direct Helmholtz solver. Geophysical Prospecting2011; 59:857-873.
[34] EngquistB, YingL. Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers. Multiscale Modeling and Simulation2011; 9:686-710. · Zbl 1228.65234
[35] RepsB, VanrooseW, binZubairH. On the indefinite Helmholtz equation: complex stretched absorbing boundary layers, iterative analysis, and preconditioning. Journal of Computational Physics2010; 229:8384-8405. · Zbl 1210.65182
[36] VirieuxJ, OpertoS, Ben‐Hadj‐AliH, BrossierR, EtienneV, SourbierF, GiraudL, HaidarA. Seismic wave modeling for seismic imaging. The Leading Edge2009; 25(8):538-544.
[37] TrottenbergU, OosterleeCW, SchüllerA. Multigrid. Academic Press Inc.: San Diego, 2001.
[38] VanrooseW, RepsB, binZubairH. A polynomial multigrid smoother for the iterative solution of the heterogeneous Helmholtz problem. Technical Report, University of Antwerp, Belgium, 2010. http://arxiv.org/abs/1012.5379 [Accessed date on 2010].
[39] SaadY, SchultzMH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing1986; 7:856-869. · Zbl 0599.65018
[40] De ZeeuwPM. Matrix‐dependent prolongations and restrictions in a blackbox multigrid solver. Journal of Computational and Applied Mathematics1990; 33:1-27. · Zbl 0717.65099
[41] NotayY, VassilevskiPS. Recursive Krylov‐based multigrid cycles. Numerical Linear Algebra with Applications2008; 15:473-487. · Zbl 1212.65132
[42] SimonciniV, SzyldDB. Flexible inner‐outer Krylov subspace methods. SIAM Journal on Numerical Analysis2003; 40:2219-2239. · Zbl 1047.65021
[43] SimonciniV, SzyldDB. Recent computational developments in Krylov subspace methods for linear systems. Numerical Linear Algebra with Applications2007; 14:1-59. · Zbl 1199.65112
[44] VassilevskiPS. Multilevel Block Factorization Preconditioners, Matrix‐Based Analysis and Algorithms for Solving Finite Element Equations. Springer: New York, 2008. · Zbl 1170.65001
[45] SaadY. A flexible inner-outer preconditioned GMRES algorithm. SIAM Journal on Scientific and Statistical Computing1993; 14:461-469. · Zbl 0780.65022
[46] TholeCA, TrottenbergU. Basic smoothing procedures for the multigrid treatment of elliptic 3D operators. Applied Mathematics and Computation1986; 19:333-345. · Zbl 0612.65065
[47] WienandsR, OosterleeCW, WashioT. Fourier analysis of GMRES(m) preconditioned by multigrid. SIAM Journal on Scientific Computing2000; 22:582-603. · Zbl 0967.65101
[48] CoolsS, VanrooseW. Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems. Technical report, University of Antwerp, Department of Mathematics and Computer Science, Belgium, 2011.
[49] DuffIS, GrattonS, PinelX, VasseurX. Multigrid based preconditioners for the numerical solution of two‐dimensional heterogeneous problems in geophysics. International Journal of Computer Mathematics2007; 84‐88:1167-1181. · Zbl 1123.65030
[50] SaadY. Iterative Methods for Sparse Linear Systems, 2nd ed. SIAM: Philadelphia, 2003. · Zbl 1031.65046
[51] HackbuschW, TrottenbergU. Multigrid Methods. Springer: Berlin Heidelberg, 1982. Lecture notes in Mathematics, Vol. 960, Proceedings of the conference held at Köln‐Porz, November 23‐27 1981.
[52] GroppW, LuskE, SkjellumA. Using MPI: Portable Parallel Programming with the Message‐Passing Interface. MIT Press: Cambridge, Massachusetts, 1999.
[53] UmetaniN, MacLachlanSP, OosterleeCW. A multigrid‐based shifted Laplacian preconditioner for fourth‐order Helmholtz discretization. Numerical Linear Algebra with Applications2009; 16:603-626. · Zbl 1224.65078
[54] AminzadehF, BracJ, KunzT. 3D salt and overthrust models. SEG/EAGE modeling series I, Society of Exploration Geophysicists, Tulsa, USA, 1997.
[55] GiraudL, GrattonS, PinelX, VasseurX. Flexible GMRES with deflated restarting. SIAM Journal on Scientific Computing2010; 32:1858-1878. · Zbl 1215.65057
[56] SimonciniV. On a non‐stagnation condition for GMRES and application to saddle point matrices. Electronic Transactions on Numerical Analysis2010; 37:202-213. · Zbl 1206.65136
[57] SimonciniV, SzyldDB. New conditions for non‐stagnation of minimal residual methods. Numerische Mathematik2008; 109:477-487. · Zbl 1151.65026
[58] DattaK, KamilS, WilliamsS, OlikerL, ShalfJ, YelickK. Optimization and performance modeling of stencil computations on modern microprocessors. SIAM Review2009; 51(1):129-159. · Zbl 1160.65359
[59] HoemmenM. Communication‐avoiding Krylov subspace methods. Ph.D. Thesis, University of California, Berkeley, Department of Computer Science, 2010.
[60] SzyldDB, VogelJA. FQMR: a flexible quasi‐minimal residual method with inexact preconditioning. SIAM Journal on Scientific Computing2001; 23(2):363-380. · Zbl 0997.65062
[61] VogelJA. Flexible BiCG and flexible Bi‐CGSTAB for nonsymmetric linear systems. Applied Mathematics and Computation2007; 188:226-233. · Zbl 1114.65318
[62] CarvalhoLM, GrattonS, LagoR, VasseurX. A flexible generalized conjugate residual method with inner orthogonalization and deflated restarting. SIAM Journal on Matrix Analysis and Applications2011; 32(4):1212-1235. · Zbl 1244.65047
[63] HarariI, TurkelE. Accurate finite difference methods for time‐harmonic wave propagation. Journal of Computational Physics1995; 119:252-270. · Zbl 0848.65072
[64] MacLachlanSP, OosterleeCW. Algebraic multigrid solvers for complex‐valued matrices. SIAM Journal on Scientific Computing2008; 30:1548-1571. · Zbl 1165.65013
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.