×

Accelerating the shifted Laplace preconditioner for the Helmholtz equation by multilevel deflation. (English) Zbl 1352.65456

Summary: Many important physical phenomena can be described by the Helmholtz equation. We investigate to what extent the convergence of the shifted Laplacian preconditioner for the Helmholtz equation can be accelerated using deflation with multigrid vectors. We therefore present a unified framework for two published algorithms. The first deflates the preconditioned operator and requires no further preconditioning. The second deflates the original operator and combines deflation and preconditioning in a multiplicative fashion. We pursue two scientific contributions. First we show, using a model problem analysis, that both algorithms cluster the eigenvalues. The new and key insight here is that the near-kernel of the coarse grid operator causes a limited set of eigenvalues to shift away from the center of the cluster with a distance proportional to the wave number. This effect is less pronounced in the first algorithmic variant at the expense of a higher computational cost. In the second contribution we quantify for the first time the large amount of reduction in CPU-time that results from the clustering of eigenvalues and the reduction in iteration count. We report to this end on the findings of an implementation in PETSc on two and three-dimensional problems with constant and variable wave number.

MSC:

65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods

Software:

PETSc
Full Text: DOI

References:

[1] Ihlenburg, F.; Babuška, I., Finite element solution of the Helmholtz equation with high wave number, part I: the h-version of the FEM, Comput. Math. Appl., 30, 9, 9-37 (1995) · Zbl 0838.65108
[2] Ernst, O. G.; Gander, M. J., Why it is difficult to solve Helmholtz problems with classical iterative methods, (Graham, I. G.; Hou, T. Y.; Lakkis, O.; Scheichl, R., Numerical Analysis of Multiscale Problems. Numerical Analysis of Multiscale Problems, Lecture Notes in Computational Science and Engineering, vol. 83 (2012), Springer: Springer Berlin, Heidelberg), 325-363 · Zbl 1248.65128
[3] Brandt, A.; Livshits, I., Wave-ray multigrid method for standing wave equations, Electron. Trans. Numer. Anal., 6, 162-181 (1997) · Zbl 0891.65127
[4] Livshits, I., A scalable multigrid method for solving indefinite Helmholtz equations with constant wave numbers, Numer. Linear Algebra Appl., 21, 2, 177-193 (2014) · Zbl 1340.65299
[5] Elman, H. C.; Ernst, O. G.; O’Leary, D. P., A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations, SIAM J. Sci. Comput., 23, 4, 1291-1315 (April 2001) · Zbl 1004.65134
[6] Engquist, B.; Ying, L., Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation, Commun. Pure Appl. Math., 64, 5, 697-735 (2011) · Zbl 1229.35037
[7] Vion, A.; Geuzaine, C., Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem, J. Comput. Phys., 266, 171-190 (2014) · Zbl 1296.65169
[8] Conen, L.; Dolean, V.; Krause, R.; Nataf, F., A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator, J. Comput. Appl. Math., 271, 83-99 (2014) · Zbl 1321.65172
[9] Bartsch, G.; Wulf, C., Adaptive multigrid for Helmholtz problems, J. Comput. Acoust., 11, 03, 341-350 (2003) · Zbl 1360.76123
[10] Olson, L. N.; Schroder, J., Smoothed aggregation for Helmholtz problems, Numer. Linear Algebra Appl., 17, 2-3, 361-386 (2010) · Zbl 1240.65359
[11] van Gijzen, M. B.; Erlangga, Y. A.; Vuik, C., Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian, SIAM J. Sci. Comput., 29, 1942-1958 (2007) · Zbl 1155.65088
[12] Cools, S.; Vanroose, W., Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems, Numer. Linear Algebra Appl., 20, 4, 575-597 (2013) · Zbl 1313.65320
[13] Erlangga, Y. A.; Vuik, C.; Oosterlee, C. W., On a class of preconditioners for solving the Helmholtz equation, Appl. Numer. Math., 50, 3-4, 409-425 (2004) · Zbl 1051.65101
[14] Mardochê, M. M.M., Incomplete factorization-based preconditionings for solving the Helmholtz equation, Int. J. Numer. Methods Eng., 50, 1077-1101 (2001) · Zbl 0977.65102
[15] Erlangga, Y. A.; Oosterlee, C. W.; Vuik, C., A novel multigrid based preconditioner for heterogeneous Helmholtz problems, SIAM J. Sci. Comput., 27, 1471-1492 (2006) · Zbl 1095.65109
[16] Erlangga, Y. A.; Vuik, C.; Oosterlee, C. W., Comparison of multigrid and incomplete LU shifted-Laplace preconditioners for the inhomogeneous Helmholtz equation, Appl. Numer. Math., 56, 648-666 (2006) · Zbl 1094.65041
[17] Reps, B.; Vanroose, W.; Zubair, H. Bin, On the indefinite Helmholtz equation: complex stretched absorbing boundary layers, iterative analysis, and preconditioning, J. Comput. Phys., 229, 8384-8405 (November 2010) · Zbl 1210.65182
[18] Bollhöfer, M.; Grote, M. J.; Schenk, O., Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media, SIAM J. Sci. Comput., 31, 3781-3805 (2009) · Zbl 1203.65273
[19] Airaksinen, T.; Heikkola, E.; Pennanen, A.; Toivanen, J., An algebraic multigrid based shifted-Laplacian preconditioner for the Helmholtz equation, J. Comput. Phys., 226, 1196-1210 (2007) · Zbl 1310.76087
[20] Erlangga, Y. A.; Nabben, R., On a multilevel Krylov method for the Helmholtz equation preconditioned by shifted Laplacian, Electron. Trans. Numer. Anal., 31, 403-424 (2008) · Zbl 1190.65050
[21] Gander, M. J.; Graham, I. G.; Spence, E. A., Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: what is the largest shift for which wavenumber-independent convergence is guaranteed?, Numer. Math., 1-48 (2015) · Zbl 1328.65238
[22] Zhu, J.; Ping, X. W.; Chen, R. S.; Fan, Z. H.; Ding, D. Z., An incomplete factorization preconditioner based on shifted Laplace operators for FEM analysis of microwave structures, Microw. Opt. Technol. Lett., 52, 1036-1042 (2010)
[23] Airaksinen, T.; Pennanen, A.; Toivanen, J., A damping preconditioner for time-harmonic wave equations in fluid and elastic material, J. Comput. Phys., 228, 1466-1479 (March 2009) · Zbl 1157.76046
[24] Riyanti, C. D.; Kononov, A.; Erlangga, Y. A.; Vuik, C.; Oosterlee, C.; Plessix, R. E.; Mulder, W. A., A parallel multigrid-based preconditioner for the 3D heterogeneous high-frequency Helmholtz equation, J. Comput. Phys., 224, 431-448 (2007) · Zbl 1120.65127
[25] Erlangga, Y. A., Advances in iterative methods and preconditioners for the Helmholtz equation, Arch. Comput. Methods Eng., 15, 37-66 (2008) · Zbl 1158.65078
[26] Vuik, C.; Segal, A.; Meijerink, J. A., An efficient preconditioned CG method for the solution of a class of layered problems with extreme contrasts in the coefficients, J. Comput. Phys., 152, 1, 385-403 (1999) · Zbl 0945.76048
[27] Tang, J. M.; Nabben, R.; Vuik, C.; Erlangga, Y. A., Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods, J. Sci. Comput., 39, 3, 340-370 (2009) · Zbl 1203.65073
[28] Tang, J. M., Two level preconditioned conjugate gradient methods with applications to bubbly flow problems (2008), DIAM, TU Delft, PhD thesis
[29] Sheikh, A. H.; Lahaye, D.; Vuik, C., On the convergence of shifted Laplace preconditioner combined with multilevel deflation, Numer. Linear Algebra Appl., 20, 4, 645-662 (2013) · Zbl 1313.65293
[30] Balay, S.; Brown, J.; Buschelman, K.; Eijkhout, V.; Gropp, W. D.; Kaushik, D.; Knepley, M. G.; Curfman McInnes, L.; Smith, B. F.; Zhang, H., PETSc users manual (2013), Argonne National Laboratory, Technical report ANL-95/11 - revision 3.4
[31] Versteeg, R. J.; Grau, G., The Marmousi experience, (Proc. EAGE workshop on Practical Aspects of Seismic Data Inversion. Proc. EAGE workshop on Practical Aspects of Seismic Data Inversion, Copenhagen, 1990 (1991), Eur. Assoc. Explor. Geophysicists: Eur. Assoc. Explor. Geophysicists Zeist)
[32] Babuska, I. M.; Sauter, S. A., Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?, SIAM Rev., 42, 3, 451-484 (2000) · Zbl 0956.65095
[33] Erlangga, Y. A.; Turkel, E., Iterative schemes for high order compact discretizations to the exterior Helmholtz equation, Modél. Math. Anal. Numér., 46, 03, 647-660 (2012) · Zbl 1272.65082
[34] Erlangga, Y. A., A robust and effecient iterative method for numerical solution of the Helmholtz equation (2005), DIAM, TU Delft, PhD thesis
[35] Erlangga, Y. A.; Nabben, R., Algebraic multilevel Krylov methods, SIAM J. Sci. Comput., 31, 3417-3437 (2009) · Zbl 1200.65021
[36] Erlangga, Y. A.; Nabben, R., Multilevel projection-based nested Krylov iteration for boundary value problems, SIAM J. Sci. Comput., 30, 1572-1595 (2008) · Zbl 1178.65032
[37] Trottenberg, U.; Oosterlee, C. W.; Schüller, A., Multigrid (2000), Academic Press: Academic Press London
[38] Sheikh, A. H., Development of the Helmholtz solver based on a shifted Laplace preconditioner and a multilevel deflation technique (2014), DIAM, TU Delft, PhD thesis
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.