Abstract
In contrast to the positive definite Helmholtz equation, the deceivingly similar looking indefinite Helmholtz equation is difficult to solve using classical iterative methods. Simply using a Krylov method is much less effective, especially when the wave number in the Helmholtz operator becomes large, and also algebraic preconditioners such as incomplete LU factorizations do not remedy the situation. Even more powerful preconditioners such as classical domain decomposition and multigrid methods fail to lead to a convergent method, and often behave differently from their usual behavior for positive definite problems. For example increasing the overlap in a classical Schwarz method degrades its performance, as does increasing the number of smoothing steps in multigrid. The purpose of this review paper is to explain why classical iterative methods fail to be effective for Helmholtz problems, and to show different avenues that have been taken to address this difficulty.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Y. Achdou and F. Nataf. Dimension-wise iterated frequency filtering decomposition. Num. Lin. Alg. and Appl., 41(5):1643–1681, 2003.
Y. Achdou and F. Nataf. Low frequency tangential filtering decomposition. Num. Lin. Alg. and Appl., 14:129–147, 2007.
M. Ainsworth. Discrete dispersion relation for hp-version finite element approximation at high wave number. SIAM J. Numer. Anal., 42(2):553–575, 2004.
N. Bakhvalov. Convergence of one relaxation method under natural constraints on the elliptic operator. Zh. Vychisl. Mat. Mat. Fiz., 6:861–883, 1966.
A. Bayliss, C. Goldstein, and E. Turkel. An iterative method for the Helmholtz equation. J. Comput. Phys., 49:443–457, 1983.
T. Betcke, S.N., Chandler-Wilde, I. Graham, S. Langdon, and M. Lindner. Condition number estimates for combined potential operators in acoustics and their boundary element discretisation. Numerical Methods for PDEs, 27(1):31–69, 2010.
A. Brandt. Multigrid techniques: 1984 guide with applications to fluid dynamics. GMD Studien 55, Gesellschaft für Mathematik und Datenverarbeitung, St. Augustin, Bonn, 1984.
A. Brandt and I. Livshits. Wave-ray multigrid method for standing wave equations. Electron. Trans. Numer. Anal., 6:162–181, 1997.
A. Brandt and S. Ta’asan. Multigrid methods for nearly singular and slightly indefinite problems. In Multigrid Methods II, pages 99–121. Springer, 1986.
W. L. Briggs, V. E. Henson, and S. F. McCormick. A Multigrid Tutorial. SIAM, 2000.
B. Buzbee, F. W. Dorr, J. A. George, and G. Golub. The direct solution of the discrete Poisson equation on irregular regions. SIAM J. Numer. Anal., 8:722–736, 1974.
A. Buzdin. Tangential decomposition. Computing, 61:257–276, 1998.
D. Colton and R. Kress. Integral Equation Methods in Scattering Theory. Wiley, New York, 1983.
L. Debreu and E. Blayo. On the Schwarz alternating method for ocean models on parallel computers. J. Computational Physics, 141:93–111, 1998.
B. Després. Méthodes de décomposition de demains pour les problèms de propagation d‘ondes en régime harmonique. PhD thesis, Université Paris IX Dauphine, 1991.
H. C. Elman, O. G. Ernst, and D. P. O’Leary. A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations. SIAM J. Sci. Comp., 23:1290–1314, 2001.
B. Engquist and L. Ying. Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation. Preprint, 2010.
B. Engquist and L. Ying. Sweeping preconditioner for the Helmholtz equation: Moving perfectly matched layers. Preprint, 2010.
B. Engquist and L. Ying. Fast algorithms for high-frequency wave propagation. this volume, page 127, 2011.
Y. Erlangga. Advances in iterative methods and preconditioners for the Helmholtz equation. Archives Comput. Methods in Engin., 15:37–66, 2008.
Y. Erlangga, C. Vuik, and C. Oosterlee. On a class of preconditioners for solving the Helmholtz equation. Applied Numerical Mathematics, 50:409–425, 2004.
O. G. Ernst. Fast Numerical Solution of Exterior Helmholtz Problems with Radiation Boundary Condition by Imbedding. PhD thesis, Stanford University, 1994.
O. G. Ernst. A finite element capacitance matrix method for exterior Helmholtz problems. Numer. Math., 75:175–204, 1996.
O. G. Ernst. Residual-minimizing Krylov subspace methods for stabilized discretizations of convection-diffusion equations. SIAM J. Matrix Anal. Appl., 22(4):1079–1101, 2000.
C. Farhat, P. Avery, R. Tesaur, and J. Li. FETI-DPH: a dual-primal domain decomposition method for acoustic scattering. Journal of Computational Acoustics, 13(3):499–524, 2005.
C. Farhat, P. Avery, R. Tezaur, and J. Li. FETI-DPH: a dual-primal domain decomposition method for accoustic scattering. Journal of Computational Acoustics, 13:499–524, 2005.
C. Farhat, A. Macedo, and R. Tezaur. FETI-H: a scalable domain decomposition method for high frequency exterior Helmholtz problem. In C.-H. Lai, P. Bjørstad, M. Cross, and O. Widlund, editors, Eleventh International Conference on Domain Decomposition Method, pages 231–241. DDM.ORG, 1999.
C. Farhat and F.-X. Roux. A method of Finite Element Tearing and Interconnecting and its parallel solution algorithm. Int. J. Numer. Meth. Engrg., 32:1205–1227, 1991.
R. Federenko. A relaxation method for solving elliptic difference equations. USSR Comput. Math. and Math. Phys., 1(5):1092–1096, 1961.
R. W. Freund and N. M. Nachtigal. QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math., 60:315–339, 1991.
M. J. Gander. Optimized Schwarz methods. SIAM J. Numer. Anal., 44(2):699–731, 2006.
M. J. Gander. Schwarz methods over the course of time. Electronic Transactions on Numerical Analysis (ETNA), 31:228–255, 2008.
M. J. Gander, L. Halpern, and F. Magoulès. An optimized Schwarz method with two-sided robin transmission conditions for the Helmholtz equation. Int. J. for Num. Meth. in Fluids, 55(2):163–175, 2007.
M. J. Gander, L. Halpern, and F. Nataf. Optimized Schwarz methods. In T. Chan, T. Kako, H. Kawarada, and O. Pironneau, editors, Twelfth International Conference on Domain Decomposition Methods, Chiba, Japan, pages 15–28, Bergen, 2001. Domain Decomposition Press.
M. J. Gander, F. Magoulès, and F. Nataf. Optimized Schwarz methods without overlap for the Helmholtz equation. SIAM J. Sci. Comput., 24(1):38–60, 2002.
M. J. Gander, V. Martin, and J.-P. Chehab. GMRES convergence analysis for diffusion, convection diffusion and Helmholtz problems. In preparation, 2011.
M. J. Gander and F. Nataf. AILU: A preconditioner based on the analytic factorization of the elliptic operator. Num. Lin. Alg. and Appl., 7(7-8):543–567, 2000.
M. J. Gander and F. Nataf. An incomplete LU preconditioner for problems in acoustics. Journal of Computational Acoustics, 13(3):1–22, 2005.
M. J. Gander and G. Wanner. From Euler, Ritz and Galerkin to modern computing. SIAM Review, 2011. to appear.
M. J. Gander and H. Zhang. Domain Decomposition Methods for the Helmholtz equation: A Numerical Study, submitted to Domain Decomposition Methods in Science and Engineering XX, Lecture Notes in Computational Science and Engineering, Springer-Verlag, 2012.
M. V. Gijzen, Y. Erlangga, and C. Vuik. Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian. SIAM J. Sci. Comput., 29(5):1942–1958, 2007.
E. Giladi and J. B. Keller. Iterative solution of elliptic problems by approximate factorization. Journal of Computational and Applied Mathematics, 85:287–313, 1997.
W. Hackbusch. Multi-Grid Methods and Applications. Springer-Verlag, 1985.
T. Hagstrom, R. P. Tewarson, and A. Jazcilevich. Numerical experiments on a domain decomposition algorithm for nonlinear elliptic boundary value problems. Appl. Math. Lett., 1(3), 1988.
E. Heikkola, J. Toivanen, and T. Rossi. A parallel fictitious domain method for the three-dimensional Helmholtz equation. SIAM J. Sci. Comput, 24(5):1567–1588, 2003.
M. A. Hyman. Non-iterative numerical solution of boundary-value problems. Appl. Sci. Res. Sec. B2, 2:325–351, 1952.
F. Ihlenburg and I. Babuška. Finite element solution to the Helmholtz equation with high wave number. Part I: The h-version of the FEM. Computer Methods in Applied Mechanics and Engineering, 39:9–37, 1995.
F. Ihlenburg and I. Babuška. Finite element solution to the Helmholtz equation with high wave number. Part II: The h-p version of the FEM. SIAM Journal on Numerical Analysis, 34:315–358, 1997.
J. B. Keller. Rays, waves and asymptotics. Bull. Amer. Math. Soc., 84(5):727–750, 1978.
B. Lee, T. Manteuffel, S. McCormick, and J. Ruge. First-order system least squares (FOSLS) for the Helmholtz equation. SIAM J. Sci. Comp., 21:1927–1949, 2000.
L. M. Leslie and B. J. McAveney. Comparative test of direct and iterative methods for solving Helmholtz-type equations. Mon. Wea. Rev., 101:235–239, 1973.
R. M. Lewis. Asymptotic theory of wave-propagation. Archive for Rational Mechanics and Analysis, 20(3):191–250, 1965.
J. Liesen and Z. Strakoš. GMRES convergence analysis for a convection-diffusion model problem. SIAM J. Sci. Comput, 26(6):1989–2009, 2005.
P.-L. Lions. On the Schwarz alternating method. III: a variant for nonoverlapping subdomains. In T. F. Chan, R. Glowinski, J. Périaux, and O. Widlund, editors, Third International Symposium on Domain Decomposition Methods for Partial Differential Equations , held in Houston, Texas, March 20-22, 1989, Philadelphia, PA, 1990. SIAM.
I. Livshits. Multigrid Solvers for Wave Equations. PhD thesis, Bar-Ilan University, Ramat-Gan, Israel, 1996.
F. Nataf. Résolution de l’équation de convection-diffusion stationaire par une factorisation parabolique. C. R. Acad. Sci., I 310(13):869–872, 1990.
Q. Niu, L. Grigori, P. Kumar, and F. Nataf. Modified tangential frequency filtering decomposition and its Fourier analysis. Numerische Mathematik, 116(1), 2010.
W. Proskurowski and O. B. Widlund. On the numerical solution of Helmholtz’s equation by the capacitance matrix method. Math. Comp., 30:433–468, 1976.
T. E. Rosmond and F. D. Faulkner. Direct solution of elliptic equations by block cyclic reduction and factorization. Mon. Wea. Rev., 104:641–649, 1976.
Y. Saad. Iterative Methods for Sparse Linear Systems. PWS Publishing Company, 1996.
V. Saul’ev. On solution of some boundary value problems on high performance computers by fictitious domain method. Siberian Math. J., 4:912–925, 1963 (in Russian).
H. A. Schwarz. Über einen Grenzübergang durch alternierendes Verfahren. Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich, 15:272–286, May 1870.
R. V. Southwell. Relaxation Methods in Theoretical Physics. Oxford University Press, 1946.
E. Stiefel. Über einige Methoden der Relaxationsrechnung. Z. Angew. Math. Phys., 3:1–33, 1952.
C. Wagner. Tangential frequency filtering decompositions for symmetric matrices. Numer. Math., 78(1):119–142, 1997.
C. Wagner. Tangential frequency filtering decompositions for unsymmetric matrices. Numer. Math., 78(1):143–163, 1997.
G. Wittum. An ILU-based smoothing correction scheme. In Parallel algorithms for partial differential equations, volume 31, pages 228–240. Notes Numer. Fluid Mech., 1991. 6th GAMM-Semin., Kiel/Ger.
G. Wittum. Filternde Zerlegungen. Schnelle Löser für grosse Gleichungssysteme. Teubner Skripten zur Numerik, Stuttgart, 1992.
E. Zauderer. Partial Differential Equations of Applied Mathematics. John Wiley & Sons, second edition, 1989.
Acknowledgements
The authors would like to acknowledge the support of the Swiss National Science Foundation Grant number 200020-121828.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Ernst, O.G., Gander, M.J. (2012). Why it is Difficult to Solve Helmholtz Problems with Classical Iterative Methods. In: Graham, I., Hou, T., Lakkis, O., Scheichl, R. (eds) Numerical Analysis of Multiscale Problems. Lecture Notes in Computational Science and Engineering, vol 83. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22061-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-22061-6_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22060-9
Online ISBN: 978-3-642-22061-6
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)