Smoothed aggregation for Helmholtz problems. (English) Zbl 1240.65359
Summary: We outline a smoothed aggregation (SA) algebraic multigrid method for 1D and 2D scalar Helmholtz problems with exterior radiation boundary conditions. We consider standard 1D finite difference discretizations and 2D discontinuous Galerkin discretizations. The scalar Helmholtz problem is particularly difficult for algebraic multigrid solvers. Not only can the discrete operator be complex-valued, indefinite, and non-self-adjoint, but it also allows for oscillatory error components that yield relatively small residuals. These oscillatory error components are not effectively handled by either standard relaxation or standard coarsening procedures. We address these difficulties through modifications of SA and by providing the SA setup phase with appropriate wave-like near null-space candidates. Much is known a priori about the character of the near null-space, and our method uses this knowledge in an adaptive fashion to find appropriate candidate vectors. Our results for the generalized minimal residual (GMRES) method preconditioned with the proposed SA method exhibit consistent performance for fixed points-per-wavelength and decreasing mesh size.
MSC:
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |
| 65F10 | Iterative numerical methods for linear systems |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65F08 | Preconditioners for iterative methods |
Keywords:
algebraic multigrid method; smoothed aggregation; Helmholtz equation; discontinuous Galerkin method; finite difference; generalized minimal residual (GMRES) method; preconditioningReferences:
| [1] | Vaněk, Algebraic multigrid based on smoothed aggregation for second and fourth order problems, Computing 56 pp 179– (1996) |
| [2] | Mandel, Energy optimization of algebraic multigrid bases, Computing 62 pp 205– (1999) · Zbl 0942.65034 |
| [3] | Vaněk, Convergence of algebraic multigrid based on smoothed aggregation, Numerische Mathematik 88 (3) pp 559– (2001) |
| [4] | Brandt, Sparsity and Its Applications pp 257– (1984) |
| [5] | Ruge, Multigrid Methods pp 73– (1987) · doi:10.1137/1.9781611971057.ch4 |
| [6] | Lahaye, Algebraic multigrid for complex symmetric systems, IEEE Transactions on Magnetics 36 (4) pp 1535– (2000) · doi:10.1109/20.877730 |
| [7] | Day, Solving complex-valued linear systems via equivalent real formulations, SIAM Journal on Scientific Computing 23 (2) pp 480– (2001) · Zbl 0992.65020 |
| [8] | MacLachlan, Algebraic multigrid solvers for complex-valued matrices, SIAM Journal on Scientific Computing 30 (3) pp 1548– (2008) · Zbl 1165.65013 |
| [9] | Sala, A new Petrov-Galerkin smoothed aggregation preconditioner for nonsymmetric linear systems, SIAM Journal on Scientific Computing 31 (1) pp 143– (2008) · Zbl 1183.76673 |
| [10] | Brezina, Towards adaptive smoothed aggregation ({\(\alpha\)} SA) for nonsymmetric problems, SIAM Journal on Scientific Computing (2009) · Zbl 1210.65075 |
| [11] | Erlangga, On a class of preconditioners for solving the Helmholtz equation, Applied Numerical Mathematics 50 (3-4) pp 409– (2004) · Zbl 1051.65101 |
| [12] | Erlangga, A novel multigrid based preconditioner for heterogeneous Helmholtz problems, SIAM Journal on Scientific Computing 27 pp 1471– (2006) · Zbl 1095.65109 |
| [13] | Airaksinen, An algebraic multigrid based shifted-Laplacian preconditioner for the Helmholtz equation, Journal of Computational Physics 226 (1) pp 1196– (2007) · Zbl 1310.76087 |
| [14] | Airaksinen, A damping preconditioner for time-harmonic wave equations in fluid and elastic material, Journal of Computational Physics 228 (5) pp 1466– (2009) · Zbl 1157.76046 |
| [15] | Bollhöfer, Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media, SIAM Journal on Scientific Computing 31 (5) pp 3781– (2009) · Zbl 1203.65273 · doi:10.1137/080725702 |
| [16] | Shapira Y. Multigrid techniques for highly indefinite equations. The 8th Copper Mountain Conference on Multigrid Methods, Copper Mountain, Colorado, 1995; 689-705. |
| [17] | Elman, A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations, SIAM Journal on Scientific Computing 23 (4) pp 1291– (2001) · Zbl 1004.65134 |
| [18] | Brandt, Multigrid Methods II pp 99– (1986) |
| [19] | Brandt, Wave-ray multigrid method for standing wave equations, Transactions on Numerical Analysis 6 pp 162– (1997) · Zbl 0891.65127 |
| [20] | Lee, First-order system least-squares for the Helmholtz equation, SIAM Journal on Scientific Computing 21 (5) pp 1927– (2000) · Zbl 0957.65097 |
| [21] | Vaněk, Tenth International Conference on Domain Decomposition, Volume 218 of Contemporary Mathematics pp 349– (1998) · doi:10.1090/conm/218/3028 |
| [22] | Bramble, The analysis of multigrid algorithms for nonsymmetric and indefinite elliptic problems, Mathematics of Computation 51 (184) pp 389– (1988) |
| [23] | Bramble, Uniform convergence of multigrid V-cycle iterations for indefinite and nonsymmetric problems, SIAM Journal on Scientific Computing 31 (6) pp 1746– (1994) · Zbl 0813.65130 |
| [24] | Ainsworth, Dispersive and dissipative behaviour of high order discontinuous Galerkin finite element methods, Journal of Computational Physics 198 (1) pp 106– (2004) · Zbl 1058.65103 |
| [25] | Atkins H, Helenbrook B. Application of p-multigrid to discontinuous Galerkin formulations of the Poisson operator. AIAA Computational Fluid Dynamics Conference, Toronto, Ontario, 2005. |
| [26] | Fidkowski, p-multigrid solution of high-order discontinuous Galerkin discretizations of the compressible Navier-Stokes equations, Journal of Computational Physics 207 (1) pp 92– (2005) · Zbl 1177.76194 · doi:10.1016/j.jcp.2005.01.005 |
| [27] | Dobrev, Two-level preconditioning of discontinuous Galerkin approximations of second-order elliptic equations, Numerical Linear Algebra with Applications 13 (9) pp 753– (2006) · Zbl 1224.65263 |
| [28] | Kanschat, Preconditioning methods for local discontinuous Galerkin discretizations, SIAM Journal on Scientific Computing 25 (3) pp 815– (2003) · Zbl 1048.65110 · doi:10.1137/S1064827502410657 |
| [29] | Gopalakrishnan, A multilevel discontinuous Galerkin method, Numerische Mathematik 95 (3) pp 527– (2003) · Zbl 1044.65084 |
| [30] | Hemker, Two-level Fourier analysis of a multigrid approach for discontinuous Galerkin discretization, SIAM Journal on Scientific Computing 25 (3) pp 1018– (2003) · Zbl 1048.65108 |
| [31] | Bochev, An improved algebraic multigrid method for solving Maxwell’s equations, SIAM Journal on Scientific Computing 25 (2) pp 623– (2003) · Zbl 1163.76337 |
| [32] | Hu, Toward an h-independent algebraic multigrid method for Maxwell’s equations, SIAM Journal on Scientific Computing 27 (5) pp 1669– (2006) · Zbl 1136.76341 |
| [33] | Bell, Algebraic multigrid for k-form Laplacians, Numerical Linear Algebra with Applications 15 (2-3) pp 165– (2008) · Zbl 1212.65481 |
| [34] | Olson, A new perspective on strength measures in algebraic multigrid, Numerical Linear Algebra with Applications (2008) · Zbl 1240.65360 · doi:10.1002/nla.669 |
| [35] | Olson, Algebraic multigrid preconditioning of high-order spectral elements for elliptic problems on a simplicial mesh, SIAM Journal on Scientific Computing 29 (5) pp 2189– (2007) · Zbl 1149.65094 |
| [36] | Brannick, An energy-based AMG coarsening strategy, Numerical Linear Algebra with Applications 13 (2-3) pp 133– (2006) · Zbl 1174.65542 |
| [37] | Saad, Iterative Methods for Sparse Linear Systems (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [38] | Saunders, Two conjugate-gradient-type methods for unsymmetric linear equations, SIAM Journal on Numerical Analysis 25 (4) pp 927– (1988) · Zbl 0652.65022 · doi:10.1137/0725052 |
| [39] | Brezina, Adaptive smoothed aggregation ({\(\alpha\)}SA) multigrid, SIAM Review 47 (2) pp 317– (2005) · Zbl 1075.65042 |
| [40] | Brent, Algorithms for Minimization without Derivatives (1973) · Zbl 0245.65032 |
| [41] | Bell WN, Olson LN, Schroder J. PyAMG: algebraic multigrid solvers in Python v1.0, 2008. Available from: http://www.pyamg.org. |
| [42] | Babuska, Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?, SIAM Journal on Numerical Analysis 34 (6) pp 2392– (1997) · Zbl 0956.65095 |
| [43] | Ihlenburg, Finite element solution of the Helmholtz equation with high wave number part I: the h-version of the FEM, Computers and Mathematics with Applications 30 (9) pp 9– (1995) · Zbl 0838.65108 · doi:10.1016/0898-1221(95)00144-N |
| [44] | Ihlenburg, Finite element solution of the Helmholtz equation with high wave number part ii: the h-p version of the FEM, SIAM Journal on Numerical Analysis 34 (1) pp 315– (1997) · Zbl 0884.65104 |
| [45] | Harari, Reducing spurious dispersion, anisotropy and reflection in finite element analysis of time-harmonic acoustics, Computer Methods in Applied Mechanics and Engineering 140 (1-2) pp 39– (1997) · Zbl 0898.76058 · doi:10.1016/S0045-7825(96)01034-1 |
| [46] | Ainsworth, Discrete dispersion relation for hp-version finite element approximation at high wave number, SIAM Journal on Numerical Analysis 42 (2) pp 553– (2004) · Zbl 1074.65112 |
| [47] | Strouboulis, The generalized finite element method for Helmholtz equation: theory, computation, and open problems, Computer Methods in Applied Mechanics and Engineering 195 (37-40) pp 4711– (2006) · Zbl 1120.76044 · doi:10.1016/j.cma.2005.09.019 |
| [48] | Farhat, Higher-order extensions of a discontinuous Galerkin method for mid-frequency Helmholtz problems, International Journal for Numerical Methods in Engineering 61 (11) pp 1938– (2004) |
| [49] | Gittelson, Plane wave discontinuous Galerkin methods: analysis of the h-version, M2AN Mathematical Model in Numerical Analysis 43 (2) pp 297– (2009) · Zbl 1165.65076 |
| [50] | Castillo, Local discontinuous Galerkin methods for elliptic problems, Communications in Numerical Methods in Engineering 18 (1) pp 69– (2002) · Zbl 0994.65121 |
| [51] | Arnold, Unified analysis of discontinuous Galerkin methods for elliptic problems, SIAM Journal on Numerical Analysis 39 pp 1749– (2002) · Zbl 1008.65080 |
| [52] | Antonietti, Discontinuous Galerkin approximation of the Laplace eigenproblem, Computer Methods in Applied Mechanics and Engineering 195 (25-28) pp 3483– (2006) · Zbl 1168.65410 |
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.
