×

Analysis of a Helmholtz preconditioning problem motivated by uncertainty quantification. (English) Zbl 1473.35122

Summary: This paper analyses the following question: let \(\mathbf{A}_j\), \(j=1,2\), be the Galerkin matrices corresponding to finite-element discretisations of the exterior Dirichlet problem for the heterogeneous Helmholtz equations \(\nabla\cdot (A_j\nabla u_j)+k^2n_ju_j=-f\). How small must \(\|A_1-A_2\|_{L^q}\) and \(\|n_1-n_2\|_{L^q}\) be (in terms of \(k\)-dependence) for GMRES applied to either \((\mathbf{A}_1)^{-1}\mathbf{A}_2\) or \(\mathbf{A}_2(\mathbf{A}_1)^{-1}\) to converge in a \(k\)-independent number of iterations for arbitrarily large \(k\)? (In other words, for \(\mathbf{A}_1\) to be a good left or right preconditioner for \(\mathbf{A}_2\)?) We prove results answering this question, give theoretical evidence for their sharpness, and give numerical experiments supporting the estimates. Our motivation for tackling this question comes from calculating quantities of interest for the Helmholtz equation with random coefficients \(A\) and \(n\). Such a calculation may require the solution of many deterministic Helmholtz problems, each with different \(A\) and \(n\), and the answer to the question above dictates to what extent a previously calculated inverse of one of the Galerkin matrices can be used as a preconditioner for other Galerkin matrices.

MSC:

35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35J25 Boundary value problems for second-order elliptic equations
65F08 Preconditioners for iterative methods
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Amestoy, PR; Duff, IS; L’Excellent, J-Y; Koster, J., A Fully A synchronous Multifrontal Solver Using Distributed Dynamic Scheduling, SIAM J. Matrix Anal. Appl., 23, 1, 15-41 (2001) · Zbl 0992.65018 · doi:10.1137/S0895479899358194
[2] Amestoy, PR; Guermouche, A.; L’Excellent, J-Y; Pralet, S., Hybrid scheduling for the parallel solution of linear systems, Parallel Comput., 32, 2, 136-156 (2006) · doi:10.1016/j.parco.2005.07.004
[3] Balay, S., Gropp, W.D., McInnes, L.C., Smith, B.F.: Efficient Management of Parallelism in Object Oriented Numerical Software Libraries. In: Arge, E., Bruaset, A. M., Langtangen, H. P. (eds.) Modern Software Tools in Scientific Computing, pp 163-202. Birkhäuser Press (1997) · Zbl 0882.65154
[4] Bardos, C.; Lebeau, G.; Rauch, J., Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary, SIAM J. Control Optim., 30, 1024-1065 (1992) · Zbl 0786.93009 · doi:10.1137/0330055
[5] Bayliss, A.; Gunzburger, M.; Turkel, E., Boundary conditions for the numerical solution of elliptic equations in exterior regions, SIAM J. Appl. Math., 42, 2, 430-451 (1982) · Zbl 0479.65056 · doi:10.1137/0142032
[6] Beckermann, B.; Goreinov, SA; Tyrtyshnikov, EE, Some remarks on the Elman estimate for GMRES, SIAM J Matrix Anal. Appl., 27, 3, 772-778 (2006) · Zbl 1101.65032 · doi:10.1137/040618849
[7] Bonazzoli, M.; Dolean, V.; Graham, IG; Spence, EA; Tournier, P-H, Domain decomposition preconditioning for the high-frequency time-harmonic Maxwell equations with absorption, Math Comp., 88, 2559-2604 (2019) · Zbl 1420.35398 · doi:10.1090/mcom/3447
[8] Brenner, S.C., Scott, L.R.: The Mathematical Theory of Finite Element Methods, volume 15 of Texts in Applied Mathematics, 3rd edn. Springer (2008) · Zbl 1135.65042
[9] Cai, X-C; Widlund, OB, Domain decomposition algorithms for indefinite elliptic problems, SIAM J. Sci. Comp., 13, 1, 243-258 (1992) · Zbl 0746.65085 · doi:10.1137/0913013
[10] Cardoso, F.; Popov, G.; Vodev, G., Distribution of resonances and local energy decay in the transmission problem II, Math. Res. Lett., 6, 377-396 (1999) · Zbl 0968.35035 · doi:10.4310/MRL.1999.v6.n4.a2
[11] Chandler-Wilde, SN; Monk, P., Wave-number-explicit bounds in time-harmonic scattering, SIAM J. Math. Anal., 39, 5, 1428-1455 (2008) · Zbl 1154.35022 · doi:10.1137/060662575
[12] Chaumont-Frelet, T.; Nicaise, S., Wavenumber explicit convergence analysis for finite element discretizations of general wave propagation problem, IMA J. Numer. Anal., 40, 2, 1503-1543 (2020) · Zbl 1465.65130 · doi:10.1093/imanum/drz020
[13] Dalcin, L.D., Paz, R.R., Kler, P.A., Cosimo, A.: Parallel distributed computing using Python. Adv. Water Resour. 34(9):1124-1139. New Computational Methods and Software Tools (2011)
[14] Du, Y.; Wu, H., Preasymptotic error analysis of higher order FEM and CIP-FEM for Helmholtz equation with high wave number, SIAM J. Numer. Anal., 53, 2, 782-804 (2015) · Zbl 1312.65189 · doi:10.1137/140953125
[15] Duff, IS; Erisman, AM; Reid, JK, On George’s Nested Dissection Method, SIAM J. Numer. Anal., 13, 5, 686-695 (1976) · Zbl 0345.65015 · doi:10.1137/0713056
[16] Duistermaat, JJ; Hörmander, L., Fourier integral operators. II, Acta Math., 128, 1, 183-269 (1972) · Zbl 0232.47055 · doi:10.1007/BF02392165
[17] Eisenstat, S.C., Elman, H.C., Schultz, M.H.: Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal., 345-357 (1983) · Zbl 0524.65019
[18] Elman, H.C.: Iterative Methods for Sparse Nonsymmetric Systems of Linear Equations. PhD thesis, Yale University (1982)
[19] Erlangga, YA; Vuik, C.; Oosterlee, CW, On a class of preconditioners for solving the helmholtz equation, Appl. Numer. Math., 50, 3-4, 409-425 (2004) · Zbl 1051.65101 · doi:10.1016/j.apnum.2004.01.009
[20] Ernst; Powell, CE; Silvester, DJ; Ullmann, E., Efficient Solvers for a Linear Stochastic Galerkin Mixed Formulation of Diffusion Problems with Random Data, SIAM J. Sci. Comput., 31, 2, 1424-1447 (2009) · Zbl 1187.35298 · doi:10.1137/070705817
[21] Essai, A., Weighted FOM and GMRES for solving nonsymmetric linear systems, Numer. Algorithm., 18, 3-4, 277-292 (1998) · Zbl 0926.65036 · doi:10.1023/A:1019177600806
[22] Filonov, N., Second-order elliptic equation of divergence form having a compactly supported solution, J. Math. Sci., 106, 3, 3078-3086 (2001) · Zbl 0991.35020 · doi:10.1023/A:1011379807662
[23] Galkowski, J., Lafontaine, D., Spence, E.A.: Local absorbing boundary conditions on fixed domains give order-one errors for high-frequency waves. arXiv:2101.02154 (2021)
[24] Galkowski, J.; Müller, EH; Spence, EA, Wavenumber-explicit analysis for the Helmholtz h-BEM: error estimates and iteration counts for the Dirichlet problem, Numer. Math., 142, 2, 329-357 (2019) · Zbl 1414.35054 · doi:10.1007/s00211-019-01032-y
[25] Galkowski, J.; Spence, EA; Wunsch, J., Optimal constants in nontrapping resolvent estimates, Pure Appl. Anal., 2, 1, 157-202 (2020) · Zbl 1439.35142 · doi:10.2140/paa.2020.2.157
[26] Gander, MJ; Graham, IG; Spence, EA, A pplying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?, Numer. Math., 131, 3, 567-614 (2015) · Zbl 1328.65238 · doi:10.1007/s00211-015-0700-2
[27] Gander, MJ; Zhang, H., A Class of Iterative Solvers for the Helmholtz Equation Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods, SIAM Rev., 61, 1, 3-76 (2019) · Zbl 1417.65216 · doi:10.1137/16M109781X
[28] Ganesh, M., Kuo, F.Y., Sloan, I.H.: Quasi-Monte Carlo finite element analysis for wave propagation in heterogeneous random media. arXiv:2004.12268 (2020) · Zbl 1459.65010
[29] Ganesh, M.; Morgenstern, C., A coercive heterogeneous media Helmholtz model: formulation, wavenumber-explicit analysis, and preconditioned high-order FEM, Numer. Algorithm., 83, 1441-1487 (2019) · Zbl 1436.35079 · doi:10.1007/s11075-019-00732-8
[30] Ghanem, RG; Kruger, RM, Numerical solution of spectral stochastic finite element systems, Comput. Methods Appl. Mech. Eng., 129, 3, 289-303 (1996) · Zbl 0861.73071 · doi:10.1016/0045-7825(95)00909-4
[31] Gong, S.; Graham, IG; Spence, EA, Domain decomposition preconditioners for high-order discretisations of the heterogeneous Helmholtz equation, IMA J. Num. Anal., 41, 3, 2139-2185 (2021) · Zbl 1501.65151 · doi:10.1093/imanum/draa080
[32] Graham, IG; Pembery, OR; Spence, EA, The Helmholtz equation in heterogeneous media: a priori bounds, well-posedness, and resonances, J. Differ. Equ., 266, 6, 2869-2923 (2019) · Zbl 1421.35056 · doi:10.1016/j.jde.2018.08.048
[33] Graham, IG; Sauter, SA, Stability and finite element error analysis for the Helmholtz equation with variable coefficients, Math. Comp., 89, 321, 105-138 (2020) · Zbl 1427.35016 · doi:10.1090/mcom/3457
[34] Graham, IG; Spence, EA; Vainikko, E., Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption, Math. Comp., 86, 307, 2089-2127 (2017) · Zbl 1368.65250 · doi:10.1090/mcom/3190
[35] Graham, IG; Spence, EA; Zou, J., Domain Decomposition with local impedance conditions for the Helmholtz equation, SIAM J. Num. Anal., 58, 5, 2515-2543 (2020) · Zbl 1465.65162 · doi:10.1137/19M1272512
[36] Grisvard, P., Elliptic Problems in Nonsmooth Domains (1985), Boston: Pitman, Boston · Zbl 0695.35060
[37] Güttel, S.; Pestana, J., Some observations on weighted GMRES, Numer. Algorithm., 67, 4, 733-752 (2014) · Zbl 1304.65127 · doi:10.1007/s11075-013-9820-x
[38] Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Supercomputing ’95: Proceedings of the 1995 ACM/IEEE Conference on Supercomputing (CDROM), pp. 28. ACM Press, New York (1995) · Zbl 0816.68093
[39] Hörmander, L.: The analysis of linear partial differential operators III: pseudo-differential operators. Springer (1985) · Zbl 0601.35001
[40] Ihlenburg, F.: Finite element analysis of acoustic scattering. Springer (1998) · Zbl 0908.65091
[41] Jin, C.; Cai, X-C, A Preconditioned Recycling GMRES Solver for Stochastic Helmholtz Problems, Commun Comput. Phys., 6, 2, 342-353 (2009) · Zbl 1364.65278 · doi:10.4208/cicp.2009.v6.p342
[42] Keese, A.: Numerical Solution of Systems with Stochastic Uncertainties—A General Purpose Framework for Stochastic Finite Elements. PhD thesis, Technischen Universität Braunschweig (2004) · Zbl 1096.60027
[43] Lafontaine, D., Spence, E.A., Wunsch, J.: A sharp relative-error bound for the Helmholtz h-FEM at high frequency. arXiv:1911.11093 (2019)
[44] Luporini, F.; Varbanescu, AL; Rathgeber, F.; Bercea, G-T; Ramanujam, J.; Ham, DA; Kelly, PHJ, Cross-Loop Optimization of A rithmetic Intensity for Finite Element Local A ssembly, ACM Trans. Arch. Code Optim., 11, 4, 57:1-57:25 (2015)
[45] McLean, W.: Strongly elliptic systems and boundary integral equations. Cambridge University Press (2000) · Zbl 0948.35001
[46] Melrose, RB; Sjöstrand, J., Singularities of boundary value problems. I, Commun. Pure Appl. Math., 31, 5, 593-617 (1978) · Zbl 0368.35020 · doi:10.1002/cpa.3160310504
[47] Melrose, RB; Sjöstrand, J., Singularities of boundary value problems. II, Commun. Pure Appl. Math., 35, 2, 129-168 (1982) · Zbl 0546.35083 · doi:10.1002/cpa.3160350202
[48] Moiola, A.; Spence, EA, Is the Helmholtz equation really sign-indefinite?, SIAM Rev., 56, 2, 274-312 (2014) · Zbl 1305.35021 · doi:10.1137/120901301
[49] Moiola, A.; Spence, EA, Acoustic transmission problems: wavenumber-explicit bounds and resonance-free regions, Math. Models Methods Appl. Sci., 29, 2, 317-354 (2019) · Zbl 1414.35057 · doi:10.1142/S0218202519500106
[50] Nédélec, J. C.: Acoustic and electromagnetic equations: integral representations for harmonic problems. Springer (2001) · Zbl 0981.35002
[51] Nuyens, D.: The ‘Magic Point Shop’ of QMC point generators and generating vectors. https://people.cs.kuleuven.be/ dirk.nuyens/qmc-generators/
[52] Pellissetti, MF; Ghanem, RG, Iterative solution of systems of linear equations arising in the context of stochastic finite elements, Adv. Eng. Softw., 31, 8-9, 607-616 (2000) · Zbl 1003.68553 · doi:10.1016/S0965-9978(00)00034-X
[53] Pembery, O.R.: The Helmholtz Equation in Heterogeneous and Random Media: Analysis and Numerics. PhD thesis, University of Bath. https://researchportal.bath.ac.uk/en/studentTheses/the-helmholtz-equation-in-heterogeneous-and-random-media-analysis (2020)
[54] Pembery, O.R.: Experimental code and data for nearby preconditioning experiments for the Helmholtz equation. doi:10.5281/zenodo.4745380 (2021)
[55] Pembery, O.R.: Finite-element discretisations of the heterogenenous and stochastic Helmholtz equation in Firedrake. doi:10.5281/zenodo.4745372 (2021)
[56] Pembery, O.R.: Nearby preconditioning experiments for the Helmholtz equation. doi:10.5281/zenodo.4745379 (May 2021)
[57] Popov, G.; Vodev, G., Distribution of the resonances and local energy decay in the transmission problem, Asymptot. Anal., 19, 3-4, 253-265 (1999) · Zbl 0931.35115
[58] Powell, CE; Elman, HC, Block-diagonal preconditioning for spectral stochastic finite-element systems, IMA J. Numer. Anal., 29, 2, 350-375 (2009) · Zbl 1169.65007 · doi:10.1093/imanum/drn014
[59] Rathgeber, F.; Ham, DA; Mitchell, L.; Lange, M.; Luporini, F.; McRae, ATT; Bercea, G-T; Markall, GR; Kelly, PHJ, Firedrake: A utomating the Finite Element Method by Composing A bstractions, ACM Trans. Math. Softw., 43, 3, 24:1-24:27 (2016) · Zbl 1396.65144
[60] Saad, Y.; Schultz, MH, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[61] Sauter, SA; Schwab, C., Boundary Element Methods (2011), Berlin: Springer, Berlin · Zbl 1215.65183 · doi:10.1007/978-3-540-68093-2
[62] Sauter, SA; Torres, C., Stability estimate for the Helmholtz equation with rapidly jumping coefficients, Z. Angewandte Math. Phys., 69, 6, 139 (2018) · Zbl 1401.65139 · doi:10.1007/s00033-018-1031-9
[63] Spence, EA, Wavenumber-explicit bounds in time-harmonic acoustic scattering, SIAM J. Math. Anal., 46, 4, 2987-3024 (2014) · Zbl 1302.35139 · doi:10.1137/130932855
[64] Vainberg, BR, On the short wave asymptotic behaviour of solutions of stationary problems and the asymptotic behaviour as \(t\rightarrow \infty\) t →∞ of solutions of non-stationary problems, Russ. Math. Surv., 30, 2, 1-58 (1975) · Zbl 0318.35006 · doi:10.1070/RM1975v030n02ABEH001406
[65] Wang, G.; Liao, QI, Efficient Spectral Stochastic Finite Element Methods for Helmholtz Equations with Random Inputs, East Asian J. Appl. Math., 9, 3, 601-621 (2019) · Zbl 1462.65014 · doi:10.4208/eajam.140119.160219
[66] Wu, H., Pre-asymptotic error analysis of CIP-FEM and FEM for the Helmholtz equation with high wave number, Part I: Linear version, IMA J. Numer. Anal., 34, 3, 1266-1288 (2014) · Zbl 1296.65144 · doi:10.1093/imanum/drt033
[67] Zhu, L.; Wu, H., Preasymptotic error analysis of CIP-FEM and FEM for Helmholtz equation with high wave number Part II: hp version, SIAM J. Numer. Anal., 51, 3, 1828-1852 (2013) · Zbl 1416.65468 · doi:10.1137/120874643
[68] Zworski, M., Semiclassical Analysis (2012), Providence: American Mathematical Society, Providence · Zbl 1252.58001 · doi:10.1090/gsm/138
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.