Fast Algorithm of the Expanding Wavefronts Finite-Difference Traveltime Calculation Based on the Three Branch Tree Structure Heap Sorts
MA Shu-fang · Journal of Jilin University · 2010
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%.