Finite-Difference Solution of the Helmholtz Equation Based on Two Domain Decomposition Algorithms

Wensheng Zhang, Yunyin Dai

Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China.
Institute of Computational Mathematics and Scientific/Engineering Computing, LSEC, Beijing, China.

DOI: 10.4236/jamp.2013.14004                

Abstract

In this paper, wave simulation with the finite difference method for the Helmholtz equation based on the domain decomposition method is investigated. The method solves the problem by iteratively solving subproblems defined on smaller subdomains. Two domain decomposition algorithms both for nonoverlapping and overlapping methods are described. More numerical computations including the benchmark Marmousi model show the effectiveness of the proposed algorithms. This method can be expected to be used in the full-waveform inversion in the future.

Keywords

Finite Difference; Domain Decomposition; Nonoverlapping; Overlapping; Helmholtz Equation; Preconditioner

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. Bayliss, C. I. Goldstein and E. Turkel, “The Numerical Solution of the Helmholtz Equation for Wave Propagation Problems in Underwater Acoustics,” Computers and Mathematics with Applications, Vol. 11, No. 7-8, 1985, pp. 655-665. http://dx.doi.org/10.1016/0898-1221(85)90162-2
[2]	R. E. Plexxis, “A Helmholtz Iterative Solver for 3D Seismic-Imaging Problems,” Geophysics, Vol. 72, No. 5, 2007, pp. SM185-SM197. http://dx.doi.org/10.1190/1.2738849
[3]	A. Bayliss, C. I. Goldstein and E. Turkel, “An Iterative Method for the Helmholtz Equation,” Journal of Computational Physics, Vol. 49, No. 3, 1983, pp.443-457. http://dx.doi.org/10.1016/0021-9991(83)90139-0
[4]	C. W. Oosterlee and T. Washio, “Iterative Solution of the Helmholtz Equation by a Second Order Method,” SIAM Journal on Matrix Analysis and Applications, Vol. 21, No. 1, 1999, pp. 209-229. http://dx.doi.org/10.1137/S0895479897316588
[5]	Y. A. Erlangga, “Advances in Iterative Methods and Preconditioners for the Helmholtz Equation,” Archives of Computational Methods in Engineering, Vol. 15, No. 1, 2008, pp. 37-66. http://dx.doi.org/10.1007/s11831-007-9013-7
[6]	R.-E. Plessix and W. A. Mulder, “Separation of Variables as a Preconditioner for an Iterative Helmholtz Solver,” Applied Numerical Mathematics, Vol. 44, No. 3, 2003, pp. 385-400. http://dx.doi.org/10.1016/S0168-9274(02)00165-4
[7]	M. M. M. Made, “Incomplete Factorization-Based Preconditionings for Solving the Helmholtz Equation,” International Journal for Numerical Methods in Engineering, Vol. 50, No. 5, 2001, pp. 1077-1101. http://dx.doi.org/10.1002/1097-0207(20010220)50:5<1077::AID-NME65>3.0.CO;2-P
[8]	N. Umetani, S. P. Maclachlan and C. W. Oosterlee, “A Multigrid-Based Shifted Laplacian Preconditioner for a Fourth-Order Helmholtz Discretization,” Numerical Linear Algebra with Applications, Vol. 16, No. 8, 2009, pp. 603-626. http://dx.doi.org/10.1002/nla.634
[9]	T. Airaksinen, E. Heikkola, A. Pennanen and J. Toivanen, “An Algebraic Multigrid Based Shifted-Laplacian Preconditioner for the Helmholtz Equation,” Journal of Computational Physics, Vol. 226, No. 1, 2007, pp. 1196- 1210. http://dx.doi.org/10.1016/j.jcp.2007.05.013
[10]	Y. A. Erlangga, C. Vuik and C. W. Oosterlee, “On a Class of Preconditioners for Solving the Helmholtz Equation,” Applied Numerical Mathematics, Vol. 50, No. 3-4, 2004, pp. 409-425. http://dx.doi.org/10.1016/j.apnum.2004.01.009
[11]	Y. A. Erlangga, C. W. Oosterlee and C. Vuik, “A Novel Multigrid Based Preconditioner for Heterogeneous Helmholtz Problems,” SIAM Journal on Scientific Computing, Vol. 27, No. 4, 2006, pp. 1471-1492. http://dx.doi.org/10.1137/040615195
[12]	T. F. Chan and T. P. Mathew, “Domain Decomposition Algorithms,” Acta Numerica, Vol. 3, 1994, pp. 61-143. http://dx.doi.org/10.1017/S0962492900002427
[13]	J. D. Benamou and B. Despres, “A Domain Decomposition Method for the Helmholtz Equation and Related Optimal Control Problems,” Journal of Computational Physics, Vol. 136, No. 1, 1997, pp. 62-68. http://dx.doi.org/10.1006/jcph.1997.5742
[14]	B. Smith, P. Bjorstad and W. Grop, “Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations,” Cambridge University Press, Cambridge, 1996.
[15]	A. Quarteroni and A. Valli, “Domain Decomposition Methods for Partial Differential Equations,” Oxford Science Publications, Oxford, 1999.
[16]	A. Tosseli and O. Widlund, “Domain Decomposition Methods—Algorithms and Theory,” Springer, Berlin, 2005.
[17]	J. Xu, “Iterative Methods by Space Decomposition and Subspace Correction,” SIAM Review, Vol. 34, No. 4, 1992, pp. 581-613. http://dx.doi.org/10.1137/1034116
[18]	J. Xu and J. Zou, “Some Nonoverlapping Domain Decomposition Methods,” SIAM Review, Vol. 40, No. 4, 1998, pp. 857-914. http://dx.doi.org/10.1137/S0036144596306800
[19]	S. Kim, “Domain Decomposition Iterative Procedures for Solving Scalar Waves in the Frequency Domain,” Numerische Mathematik, Vol. 79, No. 2, 1998, pp. 231-259. http://dx.doi.org/10.1007/s002110050339
[20]	S. Larsson, “A Domain Decomposition Method for the Helmholtz Equation in a Multilayer Domain,” SIAM Journal on Scientific Computing, Vol. 20, No. 5, 1999, pp. 1713-1731. http://dx.doi.org/10.1137/S1064827597325323
[21]	F. Magoulès, F. X. Roux and S. Salmon, “Optimal Discrete Transmission Conditions for a Nonoverlapping Domain Decomposition Method for the Helmholtz Equation,” SIAM Journal on Scientific Computing, Vol. 25, No. 5, 2004, pp. 1497-1515. http://dx.doi.org/10.1137/S1064827502415351
[22]	E. Heikkola, T. Rossi and J. Toivaned, “A Parallel Fictitious Domain Method for the Three-Dimensional Helmholtz Equation,” SIAM Journal on Scientific Computing, Vol. 24, No. 5, 2003, pp. 1567-1588. http://dx.doi.org/10.1137/S1064827500370305
[23]	R. Clayton and B. Engquist, “Absorbing Boundary Conditions for Acoustic and Elastic Wave Equations,” Bulletin of the Seismological Society of America, Vol. 67, No. 6, 1977, pp. 1529-1540.
[24]	J. P. Berenger, “A Perfectly Matched Layer for Absorbing of Electromagnetic Waves,” Journal of Computational Physics, Vol. 114, No. 2, 1994, pp. 185-200. http://dx.doi.org/10.1006/jcph.1994.1159
[25]	H. A. van der Vorst, “Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems”, SIAM Journal on Scientific and Statistical Computing, Vol. 13, No. 2, 1992, pp. 631- 644. http://dx.doi.org/10.1137/0913035
[26]	Y. Saad, “Iterative Methods for Sparse Linear Systems,” 2nd Edition, SIAM, Philadephia, PA, 2003. http://dx.doi.org/10.1137/1.9780898718003
[27]	W. Zhang, “Imaging Methods and Computations Based on the Wave Equation,” Science Press, Beijing, 2009.