基于完全三叉树堆排序的波前扩展有限差分地震波走时快速算法
|
摘要
波前扩展有限差分地震波走时算法具有物理意义明确、因果稳定性强的特点,但每次波前扩展都要寻找波前面上的最小走时点。当计算网格点数较多,特别是涉及到三维走时计算时,寻找波前面上的最小走时点是一项十分耗时的工作。研究发现,波前扩展有限差分地震波走时算法的波前点具有两个突出特点:①波前点更新十分频繁,通常每次取出波前最小走时点后都要插入若干新的波前点;②新计算出的波前点的走时通常比较大。数据结构中的二叉树堆排序方法可以提高寻找波前面上最小走时点的效率,根据特点①,在原始二叉树堆排序方法的基础上,优化了插入新波前点和移除波前面上最小走时点的流程,实际计算结果表明,与原始的二叉树堆排序方法相比,改进后的二叉树堆排序方法可以提高大约20%的计算效率。根据特点②,将原始的二叉树堆排序方法推广到多叉树,实际计算结果表明,完全三叉树堆排序方法优于二叉树和四叉树堆排序方法,可以再提高5%的计算效率。
Traveltime calculation using the expanding wavefronts finite-difference method is characterized by its explicit physics meanings and causal stabilities,but the method needs to search the minimum traveltime point frequently when expanding the wavefront.The method becomes more time consuming when there are too many grid nodes,particularly for 3D calculation.Two main characteristics of the wavefront points are found through this study: ①The wavefront points is updated frequently.Generally several new points are inserted to the wavefront points set after the minimum traveltime point is removed.②The traveltime of new calculated wavefront point is often larger than that of others.The authors try to improve the efficiency of traveltime calculation by using the binary tree structure heap sorts.According to the first characteristic of the wavefront points,the original binary tree structure heap sorts is ameliorated in that the inserting and removing operations on the heap is optimized which improves the calculation efficiency by about 20%.From the second characteristic of the wavefront points,three branch structure heap sorts is introduced which improves the calculation efficiency by another 5%.
Traveltime calculation using the expanding wavefronts finite-difference method is characterized by its explicit physics meanings and causal stabilities,but the method needs to search the minimum traveltime point frequently when expanding the wavefront.The method becomes more time consuming when there are too many grid nodes,particularly for 3D calculation.Two main characteristics of the wavefront points are found through this study: ①The wavefront points is updated frequently.Generally several new points are inserted to the wavefront points set after the minimum traveltime point is removed.②The traveltime of new calculated wavefront point is often larger than that of others.The authors try to improve the efficiency of traveltime calculation by using the binary tree structure heap sorts.According to the first characteristic of the wavefront points,the original binary tree structure heap sorts is ameliorated in that the inserting and removing operations on the heap is optimized which improves the calculation efficiency by about 20%.From the second characteristic of the wavefront points,three branch structure heap sorts is introduced which improves the calculation efficiency by another 5%.
引文
[1]Gray S H,May W P.Kirchhoff migration using eikonalequation traveltimes[J].Geophysics,1994,59:810-817.
[2]孙建国,何洋.基于波前构建的射线追踪:一种Java实现[J].吉林大学学报:地球科学版,2007,37(4):814-820.SUN Jian-guo,HE Yang.Ray-tracing based on wavefrontconstruction:a Java implementation[J].Journal of JilinUniversity:Earth Science Edition,2007,37(4):814-820.
[3]Sun J.Geometrical ray theory:edge-diffracted rays andtheir traveltimes(second-order approximation of thetraveltimes)[J].Geophysics,1994,59:148-155.
[4]韩复兴,孙建国,杨昊.基于二维三次卷积插值算法的波前构建射线追踪[J].吉林大学学报:地球科学版,2008,38(2):336-340.HAN Fu-xing,SUN Jian-guo,YANG Hao.Ray-tracingof wavefront construction by bicubic convolutioninterpolation[J].Journal of Jilin University:EarthScience Edition,2008,38(2):336-340.
[5]Vidale J.Finite-difference calculation of traveltimes[J].Bull Seis Soc Am,1988,78(6):2062-2076.
[6]Van Trier J,Symes W W.Upwind finite-differencecalculation of traveltimes[J].Geophysics,1991,56:812-821.
[7]Qin F,Luo Y,Olsen K B,et al.Finite-differencesolution of the eikonal equation along expandingwavefronts[J].Geophysics,1992,57(3):478-487.
[8]杨昊,孙建国,韩复兴.波前扩展有限差分地震波走时算法的C(++)语言描述[J].吉林大学学报:地球科学版,2007,37(3):616-619.YANG Hao,SUN Jian-guo,HAN Fu-xing.An C(++)language program implement of traveltime calculation ofexpanding wavefronts finite-difference method[J].Journal of Jilin University:Earth Science Edition,2007,37(3):616-619.
[9]Sun Jian-guo,Yang Hao,Han Fu-xing.A finitedifference scheme for solving the eikonal equation withvarying grid spacing[C]//77th SEG InternationalExposition and Annual Meeting.San Antonio:SEG,2007:2120-2124.
[10]Podvin P,Lecomte I.Finite difference computaion oftraveltime in very contrasted velocity models:a massivelyparallel approach and its associated tools[J].GeophysJ Int,1991,105:271-284.
[11]王华忠,谢海兵,马在田.有限差分地震波走时计算[J].同济大学学报,1997,25(3):318-321.WANG Hua-zhong,XIE Hai-bing,MA Zai-tian.Traveltime calculation of seismic wave with finite-differencemethod[J].Journal of Tongji University,1997,25(3):318-321.
[12]Dale,Nell B.C++pluse data structure[M].3rd ed.London:Jones and Bartlett Publishers,2003:455-463.
[2]孙建国,何洋.基于波前构建的射线追踪:一种Java实现[J].吉林大学学报:地球科学版,2007,37(4):814-820.SUN Jian-guo,HE Yang.Ray-tracing based on wavefrontconstruction:a Java implementation[J].Journal of JilinUniversity:Earth Science Edition,2007,37(4):814-820.
[3]Sun J.Geometrical ray theory:edge-diffracted rays andtheir traveltimes(second-order approximation of thetraveltimes)[J].Geophysics,1994,59:148-155.
[4]韩复兴,孙建国,杨昊.基于二维三次卷积插值算法的波前构建射线追踪[J].吉林大学学报:地球科学版,2008,38(2):336-340.HAN Fu-xing,SUN Jian-guo,YANG Hao.Ray-tracingof wavefront construction by bicubic convolutioninterpolation[J].Journal of Jilin University:EarthScience Edition,2008,38(2):336-340.
[5]Vidale J.Finite-difference calculation of traveltimes[J].Bull Seis Soc Am,1988,78(6):2062-2076.
[6]Van Trier J,Symes W W.Upwind finite-differencecalculation of traveltimes[J].Geophysics,1991,56:812-821.
[7]Qin F,Luo Y,Olsen K B,et al.Finite-differencesolution of the eikonal equation along expandingwavefronts[J].Geophysics,1992,57(3):478-487.
[8]杨昊,孙建国,韩复兴.波前扩展有限差分地震波走时算法的C(++)语言描述[J].吉林大学学报:地球科学版,2007,37(3):616-619.YANG Hao,SUN Jian-guo,HAN Fu-xing.An C(++)language program implement of traveltime calculation ofexpanding wavefronts finite-difference method[J].Journal of Jilin University:Earth Science Edition,2007,37(3):616-619.
[9]Sun Jian-guo,Yang Hao,Han Fu-xing.A finitedifference scheme for solving the eikonal equation withvarying grid spacing[C]//77th SEG InternationalExposition and Annual Meeting.San Antonio:SEG,2007:2120-2124.
[10]Podvin P,Lecomte I.Finite difference computaion oftraveltime in very contrasted velocity models:a massivelyparallel approach and its associated tools[J].GeophysJ Int,1991,105:271-284.
[11]王华忠,谢海兵,马在田.有限差分地震波走时计算[J].同济大学学报,1997,25(3):318-321.WANG Hua-zhong,XIE Hai-bing,MA Zai-tian.Traveltime calculation of seismic wave with finite-differencemethod[J].Journal of Tongji University,1997,25(3):318-321.
[12]Dale,Nell B.C++pluse data structure[M].3rd ed.London:Jones and Bartlett Publishers,2003:455-463.
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心