AN UNSTRUCTURED GEOMETRIC MULTIGRID GENERATION ALGORITHM FOR ARBITRARY GEOELECTRIC MODEL

doi:10.3969/j.issn.0253-4967.2015.03.014

Abstract

Abstract:

With the growing number of observational data, increasingly complex geoelectric model, and high-dimensional magnetotelluric method, the efficient and stable forward and inversion technologies become more and more required. Multigrid method enables the asymptotically optimal approximate numerical solution to elliptic partial differential equations including the MT 2D forward modeling problem. Currently, the coarsening and refining operations are based on regular grid which is easy to understand and implement. However, when the geometry of a region is complex or the region needs local refinements, regular grid becomes not well applicable. Unstructured triangular grid has better geometrical adaptability than structured grid. The Delaunay triangulation ensures that each triangle is generated to be Delaunay. This property is particularly suitable for numerical interpolation and FEM calculation. Besides, the Delaunay triangulation has a strong mathematical theory foundation which makes it very convenient for local refinement and sparseness. The key to solve the complicated geoelectric model using multigrid method is the automatic generation of unstructured multi-level grids. In this paper, we present an algorithm for generating unstructured grid for Multigrid method based on Delaunay triangulation. The algorithm will automatically generate the coarse and fine grid for complex input region, and all the triangle elements abide by the Delaunay criteria which ensure numerical accuracy and high convergence rate.

Key words: magnetotelluric, arbitrary geoelectric model, multigrid method, Delaunay triangulation, mesh refinement

摘要：

面对越来越多的观测数据、越来越复杂的地电模型, 大地电磁法的高维正反演需要发展高效、稳定的正、反演计算新技术.多重网格法是求解椭圆型偏微分方程最优化的方法之一, 近些年来被广泛地用作大规模、高精度方程求解的加速器.目前, 多重网格法多基于矩形网格来构造粗细不同的层次网格组, 但是矩形网格不能适应几何形状复杂的区域并且不支持局部加密细化从而限制了多重网格法的应用.文中提出一种采用Delaunay三角网的非结构化多重网格生成算法, 该算法能够自动对复杂区域生成粗细不同的网格, 并且每层网格单元具有良好的形状比和可控的尺寸大小.文中采用该算法实现了对复杂地电模型的非结构多重网格的自动生成, 解决了大地电磁多重网格正反演计算中复杂模型离散化这一关键的技术问题.

关键词: 大地电磁, 复杂地电模型, 多重网格法, Delaunay三角网, 网格细化

CLC Number:

P315.72⁺2

QIAO Liang, CHEN Xiao-bin. AN UNSTRUCTURED GEOMETRIC MULTIGRID GENERATION ALGORITHM FOR ARBITRARY GEOELECTRIC MODEL[J]. SEISMOLOGY AND GEOLOGY, 2015, 37(3): 840-850.

乔亮, 陈小斌. 复杂地电模型的非结构多重网格剖分算法[J]. 地震地质, 2015, 37(3): 840-850.

References

陈小斌. 1999. 有限元直接迭代算法［J］. 物探化探计算技术, 2: 70—76.
CHEN Xiao-bin. 1999. Direct iterative algorithm of the finite element［J］. Computing Techniques for Geophysical and Geochemical Exploration, 2: 70—76(in Chinese).
陈小斌, 胡文宝. 2002. 有限元直接迭代算法及其在线源频率域电磁响应计算中的应用［J］. 地球物理学报, 1: 119—130.
CHEN Xiao-bin, HU Wen-bao. 2002. Direct iterative finite element(DIFE)algorithm and its application to electromagnetic response modeling of line current source［J］. Chinese Journal of Geophysics, 1: 119—130(in Chinese).
陈小斌, 赵国泽. 2009. 自动构建大地电磁二维反演的测点中心网格［J］. 地球物理学报, 6: 1564—1572.
CHEN Xiao-bin, ZHAO Guo-ze. 2009. Automatic construction of a site-centered grid(SCG)for 2D magnetotelluric inversion［J］. Chinese Journal of Geophysics, 6: 1564—1572(in Chinese).
陈小宏, 牟永光. 1995. 地震波动方程反演的多重网格方法［A］. 见: 1995年中国地球物理学会第十一届学术年会论文集.
CHEN Xiao-hong, MOU Yong-guang. 1995. Multigrid method inversion of seismic wave equation［A］. In: Proceedings of Eleventh Annual Conference of the Chinese Geophysical Society, 1995(in Chinese).
许和勇, 叶正寅. 2011. 三维非结构自适应多重网格技术［J］. 空气动力学学报, 29(3): 365—369.
XU He-yong, YE Zheng-yin. 2011. A technique of three dimensional unstructured adaptive multigrid［J］. Acta Aerodynamica Sinica, 29(3): 365—369(in Chinese).
杨钦. 2005. 限定Delaunay三角网格剖分技术［M］. 北京: 电子工业出版社.
YANG Qin. 2005. Constrained Delaunay Triangular Mesh Generation Techniques［M］. Electronic Industry Press, Beijing(in Chinese).
叶涛, 陈小斌, 严良俊. 2013. 大地电磁资料精细处理和二维反演解释技术研究(三): 构建二维反演初始模型的印模法［J］. 地球物理学报, 10: 3596—3606.
YE Tao, CHEN Xiao-bin, YAN Liang-jun. 2013. Refined techniques for data processing and two-dimensional inversion in magnetotelluric(Ⅲ): Using the impressing method to construct starting model of 2D magnetotelluric inversion［J］. Chinese Journal of Geophysics, 10: 3596—3606(in Chinese).
赵国泽, 陈小斌, 汤吉. 2007. 中国地球电磁法新进展和发展趋势［J］. 地球物理学进展, 4: 1171—1180.
ZHAO Guo-ze, CHEN Xiao-bin, TANG Ji. 2007. Advanced geo-electromagnetic methods in China［J］. Progress in Geophysics, 4: 1171—1180(in Chinese).
赵国泽, 詹艳, 王立凤, 等. 2010. 鄂尔多斯断块地壳电性结构［J］. 地震地质, 32(3): 345—359.
ZHAO Guo-ze, ZHAN Yan, WANG Li-feng, et al. 2010. Electric structure of the crust beneath the Ordos fault block［J］. Seismology and Geology, 32(3): 345—359(in Chinese).
赵延文, 聂在平, 卢涛, 等. 2002. 基于变形玻恩迭代法的多重网格反演方法［J］. 电子科技大学学报, 31(4): 340—344.
ZHAO Yan-wen, NIE Zai-ping, LU Tao, et al. 2002. Multi-grid inversion method based on distorted Born iterative method［J］. Journal of UEST of China, 31(4): 340—344(in Chinese).
Achi Brandt. 1997. Multi-level adaptive solutions to boundary-value problems［J］. Mathematics of Computation, 31: 333—90.
Bowyer A. 1981. Computing dirichlet tessellations［J］. Comput J, 24(2): 162—166. doi: 10.1093/comjnl/24.2.162.
Cheng S W, Dey T K, Shewchuk J. 2012. Delaunay Mesh Generation［M］. Taylor & Francis.
Chew P L. 1989. Constrained Delaunay triangulations［J］. Algorithmica, 4(1-4): 97—108.
Delaunay B. 1934. Sur la sphère vide. A la mémoire de Georges Voronoï, Bulletin de l'Académie des Sciences de l'URSS［J］. Classe des sciences mathématiques et naturelles, 6: 793—800.
George P L, Borouchaki H. 1998. Delaunay Triangulation and Meshing: Application to Finite Elements［M］. Butterworth-Heinemann.
Mark de Berg, Marc van Kreveld, et al. 2008. Computational Geometry: Algorithms and Applications［M］. Springer-Verlag, ISBN 978-3-540-77973—5.
Miller G L, Talmor D, Teng S H. 1999. Optimal coarsening of unstructured meshes［J］. Journal of Algorithms, 31(1): 29—65.
Rand A. 2009. Delaunay Refinement Algorithms for Numerical Methods［M］. Carnegie Mellon University.
Rebay S. 1993. Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer-Watson algorithm［J］. Journal of Computational Physics, 106(1): 125—138.
Rineau L, Yvinec M. 2007. A generic software design for Delaunay refinement meshing［J］. Computational Geometry, 38(1-2): 100—110.
Ruppert J. 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation［J］. Journal of Algorithms, 18(3): 548—585.
Shewchuk J R. 2002. Delaunay refinement algorithms for triangular mesh generation［J］. Computational Geometry, 22(1-3): 21—74.
Trottenberg U, Oosterlee C W, Schüller A. 2001. Multigrid［M］. Academic Press.
Watson, David F. 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes［J］. Comput J, 24(2): 167—172. doi: 10.1093/comjnl/24.2.162.
Wesseling P. 2004. An Introduction to Multigrid Methods［M］. R T Edwards, Inc.
Zhu Y. 2006. Multigrid Finite Element Methods for Electromagnetic Field Modeling［M］. Cangellaris, A.C.

[1]	ZHAO Ling-qiang, HU Ya-xuan, WANG Qing-liang, ZHU Yi-qing, CAO Cong, LI Zhong-wei, QI Wei, WEN Yu-long. THE CHARACTERISTICS OF DEEP ELECTRICAL STRUCTURE IN LONGGANG VOLCANIC AREA, JILIN PROVINCE [J]. SEISMOLOGY AND GEOLOGY, 2022, 44(4): 845-858.
[2]	DONG Ze-yi, TANG Ji, ZHAO Guo-ze, CHEN Xiao-bin, CUI Teng-fa, HAN Bing, JIANG Feng, WANG Li-feng. PROBING THE SUBSURFACE ELECTRIC STRUCTURE FOR CSELF NETWORK IN CAPITAL CIRCLE REGION [J]. SEISMOLOGY AND GEOLOGY, 2022, 44(3): 649-668.
[3]	ZHAO Ling-qiang, ZHAN Yan, WANG Qing-liang, SUN Xiang-yu, HAN Jing, CAO Cong, ZHANG Song, CAI Yan. THE SEISMOGENIC STRUCTURE OF THE 1303 HONGTONG M8 EARTHQUAKE INFERRED FROM MAGNETOTELLURIC IMAGING [J]. SEISMOLOGY AND GEOLOGY, 2022, 44(3): 686-700.
[4]	HAN Jing, ZHAN Yan, SUN Xiang-yu, ZHAO Guo-ze, LIU Xue-hua, BAO YU-xin, SUN Jian-bao, PENG Yuan-qian. CHARACTERISTICS AND PROCESSING OF MAGNETOTELLURIC DATA UNDER STRONG ELECTROMAGNETIC INTERFERENCE ENVIRONMENT [J]. SEISMOLOGY AND GEOLOGY, 2022, 44(3): 736-752.
[5]	ZHANG Yun-yun, WANG Pei-jie, CHEN Xiao-bin, ZHAN Yan, HAN Bing, WANG Li-feng, ZHAO Guo-ze. MAGNETOTELLURIC TIME SERIES PROCESSING IN STRONG INTERFERENCE ENVIRONMENT [J]. SEISMOLOGY AND GEOLOGY, 2022, 44(3): 786-801.
[6]	LIU Zhong-yin, CHEN Xiao-bin, CAI Jun-tao, CUI Teng-fa, ZHAO Guo-ze, TANG Ji, OUYANG Biao. THE DESIGN AND APPLICATION OF TOPEAK: A THREE-DIMENSIONAL MAGNETOTELLURIC INVERSION CLOUD COMPUTING SYSTEM [J]. SEISMOLOGY AND GEOLOGY, 2022, 44(3): 802-820.
[7]	RUAN Shuai, TANG Ji, DONG Ze-yi, WANG Li-feng, DENG Yan, HAN Bing. ELECTRIC STRUCTRUE MODEL OF TIANCHI VOLCANO IN CHANGBAI MOUNTAINS BASED ON THREE-DIMENSIONAL AR-QN MAGNETOTELLURIC INVERSION [J]. SEISMOLOGY AND GEOLOGY, 2020, 42(6): 1282-1300.
[8]	SUN Xiang-yu, ZHAN Yan, ZHAO Guo-ze, ZHAO Ling-qiang, DENG Yan, HU Ya-xuan, HU Jiu-chang, XIANG Xiao-juan. MAGNETOTELLURIC IMAGING OF MAGMA DISTRIBUTION BENEATH MA'ANLING AND LEIHULING VOLCANOES OF NORTHEASTERN HAINAN, CHINA [J]. SEISMOLOGY AND GEOLOGY, 2020, 42(3): 640-653.
[9]	SUN Xiang-yu, ZHAN Yan, ZHAO Ling-qiang, CHEN Xiao-bin, LI Chen-xia, SUN Jian-bao, HAN Jing, CUI Teng-fa. ELECTRICAL STRUCTURE OF THE 2017 M_S7.0 JIUZHAIGOU EARTHQUAKE REGION AND THE EASTERN TERMINUS OF THE EAST KUNLUN FAULT [J]. SEISMOLOGY AND GEOLOGY, 2020, 42(1): 182-197.
[10]	JIANG Feng, CHEN Xiao-bin, DONG Ze-yi, CUI Teng-fa, LIU Zhong-yin, WANG Pei-jie. APPLYING 3D INVERSION OF SINGLE-PROFILE MAGNETOTELLURIC DATA TO IDENTIFY THE SHADE AND YUNONGXI FAULTS [J]. SEISMOLOGY AND GEOLOGY, 2019, 41(6): 1444-1463.
[11]	ZHANG Ji-hong, ZHAO Guo-ze, DONG Ze-yi, WANG Li-feng, HAN Bing, WANG Qing-lin, TANG Ting-mei, WANF Mei. STUDY ON THE ELECTRICAL STRUCTURE OF THE ANQIU AND JUXIAN ELECTROMAGNETIC STATIONS IN THE TANLU FAULT ZONE [J]. SEISMOLOGY AND GEOLOGY, 2019, 41(5): 1239-1253.
[12]	ZHAO Ling-qiang, ZHAN Yan, WANG Qing-liang, SUN Xiang-yu, YANG Hao, CHEN Xiao-bin. DEEP ELECTRICAL STRUCTURE BENEATH THE 1954 M_S7.0 MINQIN, GANSU EARTHQUAKE AND ITS SEISMOTECTONIC ENVIRONMENT [J]. SEISMOLOGY AND GEOLOGY, 2018, 40(3): 552-565.
[13]	HAN Jiang-tao, WANG Tian-qi, LIU Wen-yu, LIU Guo-xing, HAN Song, LIU Li-jia. DEEP “ARCH-BRIDGE” MAGMATIC SYSTEM OF THE AERSHAN VOLCANIC GROUP AND ITS STABILITY ANALYSIS [J]. SEISMOLOGY AND GEOLOGY, 2018, 40(3): 590-610.
[14]	ZHOU Yao-ming, ZHU Wen-bin, CHEN Zheng-le, ZHU Bing-yu, XUE Feng. THE INTERPRETATION OF GRAVITATIONAL AND MAGNETIC DATA FOR THE VOLCANIC ROCKS DISTRIBUTION IN KE-BAI FAULT ZONE, JUNGGAR BASIN [J]. SEISMOLOGY AND GEOLOGY, 2018, 40(3): 641-655.
[15]	WENG Ai-hua, LI Jian-ping, FAN Xiao-ping, LI Si-rui, HAN Jiang-tao, LI Da-jun, LI Ya-bin, ZHAO Xiang-yang, TANG Yu. FINE ELECTRICAL STRUCTURE BENEATH THE EPICENTER OF 1668 TANCHENG M_S8.5 EARTHQUAKE REVEALED BY MT SOUNDING [J]. SEISMOLOGY AND GEOLOGY, 2018, 40(2): 396-409.