基于多重网格预条件求解平均导数法离散的Helmholtz方程
|
摘要
有限差分法求解Helmholtz方程,依赖于两点:1差分格式的构造;2高效的求解算法.本文采用平均导数法离散Helmholtz方程.该差分格式有三点好处:1能适用于横纵不等间距采样;2在完全匹配层区域(PML),差分方程与微分方程逐点相容;3能将一个波长内的采样点数减少至少于4.求解离散的Helmholtz方程的算法一般分为直接法和迭代算法.直接法由于内存需求太大而无法适用于大规模问题;基于Krylov子空间的迭代方法结合多重网格预条件算法是一种快速高效求解方法,然而对于横纵不等间距采样(在多重网格中称为各向异性问题),经典的多重网格方法失效.本文分析了经典多重网格的三个重要组成部分:完全加权限制算子,点松弛技术以及双线性延拓算子,进而采用了半粗化技术代替全粗化技术,线松弛技术代替点松弛技术以及依赖差分算子的延拓算子代替双线性延拓算子,使得各向异性问题变得收敛;而且对于非均匀介质中-低频率的迭代问题,我们获得了较为满意的收敛速度.
An efficient finite-difference method for solving Helmholtz equation depends on two points:one is discrete scheme,the other is efficient algorithm.In this paper,we adopt theaverage-derivative scheme,which owns three advantages:Firstly,it can be applied to unequal directional sampling intervals for Helmholtz equation.Secondly,the scheme is pointwise consistent with Helmholtz equation in a perfect matched layer.And thirdly,it requires less than 4 grid points sampling per wavelength.To solve the discrete Helmholtz equation,which is extremely large and indefinite,direct methods cannot resolve well,and the Krylov subspace iterative methods,such as Bi-CGSTAB and GMRES combining a multigrid-based preconditioner,are good choices.However,the standard multigrid algorithm fails to converge when it encounters unequal directional sampling intervals,which is called anisotropy in multigrid.We analyze the most important three parts of standard multigrid:full weighting restriction operator,point relaxation methods and bilinear interpolation operator,and then we replace them with semi-coarsening,line relaxation and operator-dependent interpolation to make it convergent in anisotropic problems.Consequently,we obtain a satisfactory convergence speed for low and moderate frequency iterative problems in heterogeneous media.
An efficient finite-difference method for solving Helmholtz equation depends on two points:one is discrete scheme,the other is efficient algorithm.In this paper,we adopt theaverage-derivative scheme,which owns three advantages:Firstly,it can be applied to unequal directional sampling intervals for Helmholtz equation.Secondly,the scheme is pointwise consistent with Helmholtz equation in a perfect matched layer.And thirdly,it requires less than 4 grid points sampling per wavelength.To solve the discrete Helmholtz equation,which is extremely large and indefinite,direct methods cannot resolve well,and the Krylov subspace iterative methods,such as Bi-CGSTAB and GMRES combining a multigrid-based preconditioner,are good choices.However,the standard multigrid algorithm fails to converge when it encounters unequal directional sampling intervals,which is called anisotropy in multigrid.We analyze the most important three parts of standard multigrid:full weighting restriction operator,point relaxation methods and bilinear interpolation operator,and then we replace them with semi-coarsening,line relaxation and operator-dependent interpolation to make it convergent in anisotropic problems.Consequently,we obtain a satisfactory convergence speed for low and moderate frequency iterative problems in heterogeneous media.
引文
Bayliss A,Goldstein C I,Turkel E.1983.An iterative method for the Helmholtz equation.Journal of Computational Physics,49(3):443-457.
Bérenger J P.1994.A perfectly matched layer for the absorption of electromagnetic waves.Journal of Computational Physics,114(2):185-200.
Briggs W L,Van Emden H,McCormick S F.2000.A Multigrid Tutorial.2nd ed.Philadelphia,PA:Society for Industrial and Applied Mathematics.
Cao J,Chen J B,Cao S H.2015.Studies on iterative algorithms for modeling of frequency-domain wave equation based on multi-grid precondition.Chinese Journal of Geophysics(in Chinese),58(3):1002-1012,doi:10.6038/cjg20150325.
Cao J,Chen J B,Dai M X.2018.Modeling of frequency-domain scalar wave equation with the average-derivative optimal scheme based on a multigrid-preconditioned iterative solver.Journal of Applied Geophysics,148:70-82.
Chen J B.2012.An average-derivative optimal scheme for frequency-domain scalar wave equation.Geophysics,77(6):T201-T210.
Chen Z Y,Cheng D S,Feng W,et al.2011.A multigrid-based preconditioned Krylov subspace method for the Helmholtz equation with PML.Journal of Mathematical Analysis and Applications,383(2):522-540.
Chen Z Y,Cheng D S,Feng W,et al.2013.An optimal 9-point finite difference scheme for the helmholtz equation with PML.International Journal of Numerical Analysis&Modeling,10(2):389-410.
De Zeeuw P M.1990.Matrix-dependent prolongations and restrictions in a blackbox multigrid solver.Journal of Computational and Applied Mathematics,33(1):1-27.
Erlangga Y A,Vuik C,Oosterlee C W.2004.On a class of preconditioners for solving the Helmholtz equation.Applied Numerical Mathematics,50(3-4):409-425.
Erlangga Y A,Oosterlee C W,Vuik C.2006a.A novel multigrid based preconditioner for heterogeneous Helmholtz problems.SIAM Journal on Scientific Computing,27(4):1471-1492.
Erlangga Y A,Vuik C,Oosterlee C W.2006b.Comparison of multigrid and incomplete LU shifted-Laplace preconditioners for the inhomogeneous Helmholtz equation.Applied Numerical Mathematics,56(5):648-666.
Erlangga Y A.2008.Advances in iterative methods and preconditioners for the Helmholtz equation.Archives of Computational Methods in Engineering,15(1):37-66.
Frank J,Vuik C.2001.On the construction of deflation-based preconditioners.SIAM Journal on Scientific Computing,23(2):442-462.
Jo C H,Shin C,Suh J H.1996.An optimal 9-point,finitedifference,frequency-space,2-D scalar wave extrapolator.Geophysics,61(2):529-537.
Laird A L,Giles M.2002.Preconditioned iterative solution of the2DHelmholtz equation.Technical Report,NA 02-12,Computing Lab,Oxford University.
Morgan R B.1995.A restarted GMRES method augmented with eigenvectors.SIAM Journal on Matrix Analysis and Applications,16(4):1154-1171.
Nicolaides R A.1987.Deflation of conjugate gradients with applications to boundary value problems.SIAM Journal on Numerical Analysis,24(2):355-365.
Plessix R E.2007.A Helmholtz iterative solver for 3Dseismicimaging problems.Geophysics,72(5):SM185-SM194.
Riyanti C D,Kononov A,Erlangga Y A,et al.2007.A parallel multigrid-based preconditioner for the 3D heterogeneous highfrequency Helmholtz equation.Journal of Computational Physics,224(1):431-448.
Tsynkov S,Turkel E.2001.A cartesian perfectly matched layer for the helmholtz equation.∥Absorbing Boundaries and Layers,Domain Decomposition Methods:Applications to Large Scale Computers.Huntington,NY:Nova Science,279-309.
Van Gijzen M B,Erlangga Y A,Vuik C.2007.Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian.SIAM Journal on Scientific Computing,29(5):1942-1958.
曹健,陈景波,曹书红.2015.频率域波动方程正演基于多重网格预条件的迭代算法研究.地球物理学报,58(3):1002-1012,doi:10.6038/cjg20150325.
Bérenger J P.1994.A perfectly matched layer for the absorption of electromagnetic waves.Journal of Computational Physics,114(2):185-200.
Briggs W L,Van Emden H,McCormick S F.2000.A Multigrid Tutorial.2nd ed.Philadelphia,PA:Society for Industrial and Applied Mathematics.
Cao J,Chen J B,Cao S H.2015.Studies on iterative algorithms for modeling of frequency-domain wave equation based on multi-grid precondition.Chinese Journal of Geophysics(in Chinese),58(3):1002-1012,doi:10.6038/cjg20150325.
Cao J,Chen J B,Dai M X.2018.Modeling of frequency-domain scalar wave equation with the average-derivative optimal scheme based on a multigrid-preconditioned iterative solver.Journal of Applied Geophysics,148:70-82.
Chen J B.2012.An average-derivative optimal scheme for frequency-domain scalar wave equation.Geophysics,77(6):T201-T210.
Chen Z Y,Cheng D S,Feng W,et al.2011.A multigrid-based preconditioned Krylov subspace method for the Helmholtz equation with PML.Journal of Mathematical Analysis and Applications,383(2):522-540.
Chen Z Y,Cheng D S,Feng W,et al.2013.An optimal 9-point finite difference scheme for the helmholtz equation with PML.International Journal of Numerical Analysis&Modeling,10(2):389-410.
De Zeeuw P M.1990.Matrix-dependent prolongations and restrictions in a blackbox multigrid solver.Journal of Computational and Applied Mathematics,33(1):1-27.
Erlangga Y A,Vuik C,Oosterlee C W.2004.On a class of preconditioners for solving the Helmholtz equation.Applied Numerical Mathematics,50(3-4):409-425.
Erlangga Y A,Oosterlee C W,Vuik C.2006a.A novel multigrid based preconditioner for heterogeneous Helmholtz problems.SIAM Journal on Scientific Computing,27(4):1471-1492.
Erlangga Y A,Vuik C,Oosterlee C W.2006b.Comparison of multigrid and incomplete LU shifted-Laplace preconditioners for the inhomogeneous Helmholtz equation.Applied Numerical Mathematics,56(5):648-666.
Erlangga Y A.2008.Advances in iterative methods and preconditioners for the Helmholtz equation.Archives of Computational Methods in Engineering,15(1):37-66.
Frank J,Vuik C.2001.On the construction of deflation-based preconditioners.SIAM Journal on Scientific Computing,23(2):442-462.
Jo C H,Shin C,Suh J H.1996.An optimal 9-point,finitedifference,frequency-space,2-D scalar wave extrapolator.Geophysics,61(2):529-537.
Laird A L,Giles M.2002.Preconditioned iterative solution of the2DHelmholtz equation.Technical Report,NA 02-12,Computing Lab,Oxford University.
Morgan R B.1995.A restarted GMRES method augmented with eigenvectors.SIAM Journal on Matrix Analysis and Applications,16(4):1154-1171.
Nicolaides R A.1987.Deflation of conjugate gradients with applications to boundary value problems.SIAM Journal on Numerical Analysis,24(2):355-365.
Plessix R E.2007.A Helmholtz iterative solver for 3Dseismicimaging problems.Geophysics,72(5):SM185-SM194.
Riyanti C D,Kononov A,Erlangga Y A,et al.2007.A parallel multigrid-based preconditioner for the 3D heterogeneous highfrequency Helmholtz equation.Journal of Computational Physics,224(1):431-448.
Tsynkov S,Turkel E.2001.A cartesian perfectly matched layer for the helmholtz equation.∥Absorbing Boundaries and Layers,Domain Decomposition Methods:Applications to Large Scale Computers.Huntington,NY:Nova Science,279-309.
Van Gijzen M B,Erlangga Y A,Vuik C.2007.Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian.SIAM Journal on Scientific Computing,29(5):1942-1958.
曹健,陈景波,曹书红.2015.频率域波动方程正演基于多重网格预条件的迭代算法研究.地球物理学报,58(3):1002-1012,doi:10.6038/cjg20150325.