地图代数中的双重网格计算方法
|
摘要
当今数据量级的骤增以及高精度要求的剧升是科学计算的新特点。随着物联网、云计算的发展,对全球范围分析计算的米级、亚米级以上高精度的要求已经出现。因为倍缩的颗粒度意味着计算量和空间复杂性几何级数般地飙升,因此机械地缩小栅格尺寸以实现计算精度和效率保证的自然途径理论和实践上都遇到极大困难。本文首先论述了实际计算中双重网格计算的原理和关键。它是在通常地图代数粗栅格距离变换后,充分利用其中心间长距离准确计算的基础,运用两端点间度量计算中的微分公式,在两端点粗栅格内各有微小位移时简易并准确计算位移后距离,以完成所有相关端点粗栅格中各细栅格阵的距离变换运算,从而实现高分辨率度量下的目标计算。并在此基础上详细阐述了实际应用中双重网格计算的具体实施方案,并讨论了它的计算复杂性。结果表明,双重网格计算方法极大地降低了计算开销,在理论和实践上突破了栅格方法对于大区域度量计算的适用性问题。
Large data amount and high precision requirements become new characteristics of scientific computing.With the development of cloud computing,spatial calculation with the requirement for precision at the meter and even sub-meter level becomes more and more common.Because small particle size means that the amount of calculation and the space complexity soar,it is difficult to meet the requirements of the calculation accuracy and efficiency through the mechanical reduction of grid size.This paper first discussed the principle and the key of double grid calculation in the practical calculation.This method made full use of the high accuracy of long distance calculation of map algebra and it is based on the differential formula in the metric calculation,which has a rigorous theoretical foundation.Its implementation,computational complexity and experiment results were analyzed and discussed through the theoretical analysis and experimental research.Then the implementation scheme of double grid computation in practical application was elaborated and discussed in detail.The results showed that this method realized the distance calculation at the high resolution measurement scale and broke through the problem of the applicability of grid methods in the large area calculation in theory and practice.
Large data amount and high precision requirements become new characteristics of scientific computing.With the development of cloud computing,spatial calculation with the requirement for precision at the meter and even sub-meter level becomes more and more common.Because small particle size means that the amount of calculation and the space complexity soar,it is difficult to meet the requirements of the calculation accuracy and efficiency through the mechanical reduction of grid size.This paper first discussed the principle and the key of double grid calculation in the practical calculation.This method made full use of the high accuracy of long distance calculation of map algebra and it is based on the differential formula in the metric calculation,which has a rigorous theoretical foundation.Its implementation,computational complexity and experiment results were analyzed and discussed through the theoretical analysis and experimental research.Then the implementation scheme of double grid computation in practical application was elaborated and discussed in detail.The results showed that this method realized the distance calculation at the high resolution measurement scale and broke through the problem of the applicability of grid methods in the large area calculation in theory and practice.
引文
[1]LONGLEY P A,GOODCHILD M F,MAGUIRE D J,等.地理信息系统(上卷)——原理与技术[M].唐中实,译.2版.北京:电子工业出版社,2004:99-109,113-142,163-173.LONGLEY P A,GOODCHILD M F,MAGUIRE D J,et al.Geographical Information Systems.Volume 1:Principles and Technical Issues[M].TANG Zhongshi,trans.2nd ed.Beijing:Publishing House of Electronics Industry,2004:99-109,113-142,163-173.
[2]史文中.空间数据与空间分析不确定性原理[M].北京:科学出版社,2015.SHI Wenzhong.Principles of Modeling Uncertainties in Spatial Data and Spatial Analyses[M].Beijing:Science Press,2015.
[3]胡鹏,杨传勇,胡海,等.GIS的基本理论问题——地图代数的空间观[J].武汉大学学报(信息科学版),2002,27(6):616-621.HU Peng,YANG Chuanyong,HU Hai,et al.Space View of Map Algebra[J].Geomatics and Information Science of Wuhan University,2002,27(6):616-621.
[4]蒋会平,谭树东,胡海.椭球面三角形外心的地图代数解法[J].测绘学报,2016,45(2):241-249.DOI:10.11947/j.AGCS.2016.20140503.JIANG Huiping,TAN Shudong,HU Hai.Determination of Circumcenter of Triangle on Ellipsoidal Surface Based on Map Algebra[J].Acta Geodaetica et Cartographica Sinica,2016,45(2):241-249.DOI:10.11947/j.AGCS.2016.20140503.
[5]《现代数学手册》编纂委员会.现代数学手册·计算机数学卷[M].武汉:华中科技大学出版社,2001:265.Editorial Committee of Handbook of Modern Mathematics.Handbook of Modern Mathematics.Computer Mathematics Volume[M].Wuhan:Huazhong University of Science and Technology Press,2001:265.
[6]HACKBUSCH W.Multi-grid Methods and Applications[M].Berlin,Heidelberg:Springer,1985:558-575.
[7]BRANDT A.Multi-level Adaptive Solutions to Boundaryvalue Problems[J].Mathematics of Computation,1977,31(138):333-390.
[8]NICOLAIDES R A.On Multiple Grid and Related Techniques for Solving Discrete Elliptic Systems[J].Journal of Computational Physics,1975,19(4):418-431.
[9]宋印军,岳天祥.基于多重网格法求解的高精度曲面建模模型[J].武汉大学学报(信息科学版),2009,34(6):711-714.SONG Yinjun,YUE Tianxiang.An Ontology-driven Discovering Model of Geographical Information Services[J].Geomatics and Information Science of Wuhan University,2009,34(6):711-714.
[10]HIPTMAIR R.Multigrid Method for Maxwell's Equations[J].Siam Journal on Numerical Analysis,1998,36(1):204-225.
[11]史文娇,杜正平,宋印军,等.基于多重网格求解的土壤属性高精度曲面建模[J].地理研究,2011,30(5):861-870.SHI Wenjiao,DU Zhengping,SONG Yinjun,et al.High Accuracy Surface Modeling of Soil Properties Based on Multi-grid[J].Geographical Research,2011,30(5):861-870.
[12]MATVEEV A D.Multigrid Finite Element Method in Calculation of 3D Homogeneous and Composite Solids[M].Kazan:Kazan University,2016:530-543.
[13]CHEN Chao,BIRO O.Geometric Multigrid With Plane Smoothing for Thin Elements in 3D Magnetic Fields Calculation[J].IEEE Transactions on Magnetics,2012,48(2):443-446.
[14]ARNONE A,LIOU M S,POVINELLI L A.Multigrid Calculation of Three-dimensional Viscous Cascade Flows[J].Journal of Propulsion and Power,1993,9(4):605-614.
[15]CORNELIUS C,VOLGMANN W,STOFF H.Calculation of Three Dimensional Turbulent Flow with a Finite Volume Multigrid Method[J].International Journal for Numerical Methods in Fluids,1999,31(4):703-720.
[16]渡部隆一.泰勒展开[M].胡复,译.北京:科学普及出版社,1980.Du Bulonglong.Talyor Expansion[M].HU Fu,trans.Beijing:Popular Science Press,1980.
[17]刘经南.三维基线向量与大地坐标差间的微分公式及其应用[J].武汉大学学报(信息科学版),1991,16(3):70-78.LIU Jingnan.The Formula Eetween 3D Baseline Vector and Geodetic Coordinate Differences and Its Application[J].Journal of Wuhan Technical University of Surveying and Mapping,1991,16(3):70-78.
[18]施一民,朱紫阳.测地坐标系中大地线的微分方程及微分关系式[J].同济大学学报,2003,31(1):40-43.SHI Yimin,ZHU Ziyang.Differential Equations and Differential Relationship of Geodesic Lines in Geodesic Coordinate System[J].Journal of Tongji University,2003,31(1):40-43.
[19]陈健,晁定波.椭球大地测量学[M].北京:测绘出版社,1989:81-145,229-262.CHEN Jian,CHAO Dingbo.Ellipsoid Geodesy[M].Beijing:Surveying and Mapping Press,1989:81-145,229-262.
[20]胡鹏,游涟,杨传勇,等.地图代数[M].武汉:武汉大学出版社,2002:1-297.HU Peng,YOU Lian,YANG Chuanyong,et al.Map Algebra[M].Wuhan:Wuhan University Press,2002:1-297.
[21]胡鹏,游涟,胡海.地图代数概论[M].北京:测绘出版社,2008:167-189.HU Peng,YOU Lian,HU Hai.The Introduction of Map Algebra[M].Beijing:Surveying and Mapping Press,2008:167-189.
[22]胡海,杨传勇,胡鹏.自然图形间的中间线和比例线方法[J].海洋测绘,2009,29(5):15-18.HU Hai,YANG Chuanyong,HU Peng.Methods of Midline and Scale Line Between Nature Figures[J].Hydrographic Surveying and Charting,2009,29(5):15-18.
[23]胡海.自然图形k阶Voronoi图生成和应用[D].武汉:武汉大学,2007:1-120.HU Hai.Generation and Application of Natural Graph K-order Voronoi Diagram[D].Wuhan:Wuhan University,2007:1-120.
[24]胡鹏,杨传勇,胡海.障碍空间最短路径的地图代数解法[M].北京:测绘出版社,2007.HU Peng,YANG Chuanyong,HU Hai.Solution on ESPO Using Map Algebra[M].Beijing:Surveying and Mapping Press,2007.
[25]杨传勇,胡海,胡鹏,等.欧氏障碍空间的最短路径问题解法[J].武汉大学学报(信息科学版),2012,37(12):1495-1499.YANG Chuanyong,HU Hai,HU Peng,et al.Solution of Euclidean Shortest Path Problem Space with Obstacles[J].Geomatics and Information Science of Wuhan University,2012,37(12):1495-1499.
[26]HU Hai,LIU Xiaohang,HU Peng.Voronoi Diagram Generation on the Ellipsoidal Earth[J].Computers&Geosciences,2014,73:81-87.
[2]史文中.空间数据与空间分析不确定性原理[M].北京:科学出版社,2015.SHI Wenzhong.Principles of Modeling Uncertainties in Spatial Data and Spatial Analyses[M].Beijing:Science Press,2015.
[3]胡鹏,杨传勇,胡海,等.GIS的基本理论问题——地图代数的空间观[J].武汉大学学报(信息科学版),2002,27(6):616-621.HU Peng,YANG Chuanyong,HU Hai,et al.Space View of Map Algebra[J].Geomatics and Information Science of Wuhan University,2002,27(6):616-621.
[4]蒋会平,谭树东,胡海.椭球面三角形外心的地图代数解法[J].测绘学报,2016,45(2):241-249.DOI:10.11947/j.AGCS.2016.20140503.JIANG Huiping,TAN Shudong,HU Hai.Determination of Circumcenter of Triangle on Ellipsoidal Surface Based on Map Algebra[J].Acta Geodaetica et Cartographica Sinica,2016,45(2):241-249.DOI:10.11947/j.AGCS.2016.20140503.
[5]《现代数学手册》编纂委员会.现代数学手册·计算机数学卷[M].武汉:华中科技大学出版社,2001:265.Editorial Committee of Handbook of Modern Mathematics.Handbook of Modern Mathematics.Computer Mathematics Volume[M].Wuhan:Huazhong University of Science and Technology Press,2001:265.
[6]HACKBUSCH W.Multi-grid Methods and Applications[M].Berlin,Heidelberg:Springer,1985:558-575.
[7]BRANDT A.Multi-level Adaptive Solutions to Boundaryvalue Problems[J].Mathematics of Computation,1977,31(138):333-390.
[8]NICOLAIDES R A.On Multiple Grid and Related Techniques for Solving Discrete Elliptic Systems[J].Journal of Computational Physics,1975,19(4):418-431.
[9]宋印军,岳天祥.基于多重网格法求解的高精度曲面建模模型[J].武汉大学学报(信息科学版),2009,34(6):711-714.SONG Yinjun,YUE Tianxiang.An Ontology-driven Discovering Model of Geographical Information Services[J].Geomatics and Information Science of Wuhan University,2009,34(6):711-714.
[10]HIPTMAIR R.Multigrid Method for Maxwell's Equations[J].Siam Journal on Numerical Analysis,1998,36(1):204-225.
[11]史文娇,杜正平,宋印军,等.基于多重网格求解的土壤属性高精度曲面建模[J].地理研究,2011,30(5):861-870.SHI Wenjiao,DU Zhengping,SONG Yinjun,et al.High Accuracy Surface Modeling of Soil Properties Based on Multi-grid[J].Geographical Research,2011,30(5):861-870.
[12]MATVEEV A D.Multigrid Finite Element Method in Calculation of 3D Homogeneous and Composite Solids[M].Kazan:Kazan University,2016:530-543.
[13]CHEN Chao,BIRO O.Geometric Multigrid With Plane Smoothing for Thin Elements in 3D Magnetic Fields Calculation[J].IEEE Transactions on Magnetics,2012,48(2):443-446.
[14]ARNONE A,LIOU M S,POVINELLI L A.Multigrid Calculation of Three-dimensional Viscous Cascade Flows[J].Journal of Propulsion and Power,1993,9(4):605-614.
[15]CORNELIUS C,VOLGMANN W,STOFF H.Calculation of Three Dimensional Turbulent Flow with a Finite Volume Multigrid Method[J].International Journal for Numerical Methods in Fluids,1999,31(4):703-720.
[16]渡部隆一.泰勒展开[M].胡复,译.北京:科学普及出版社,1980.Du Bulonglong.Talyor Expansion[M].HU Fu,trans.Beijing:Popular Science Press,1980.
[17]刘经南.三维基线向量与大地坐标差间的微分公式及其应用[J].武汉大学学报(信息科学版),1991,16(3):70-78.LIU Jingnan.The Formula Eetween 3D Baseline Vector and Geodetic Coordinate Differences and Its Application[J].Journal of Wuhan Technical University of Surveying and Mapping,1991,16(3):70-78.
[18]施一民,朱紫阳.测地坐标系中大地线的微分方程及微分关系式[J].同济大学学报,2003,31(1):40-43.SHI Yimin,ZHU Ziyang.Differential Equations and Differential Relationship of Geodesic Lines in Geodesic Coordinate System[J].Journal of Tongji University,2003,31(1):40-43.
[19]陈健,晁定波.椭球大地测量学[M].北京:测绘出版社,1989:81-145,229-262.CHEN Jian,CHAO Dingbo.Ellipsoid Geodesy[M].Beijing:Surveying and Mapping Press,1989:81-145,229-262.
[20]胡鹏,游涟,杨传勇,等.地图代数[M].武汉:武汉大学出版社,2002:1-297.HU Peng,YOU Lian,YANG Chuanyong,et al.Map Algebra[M].Wuhan:Wuhan University Press,2002:1-297.
[21]胡鹏,游涟,胡海.地图代数概论[M].北京:测绘出版社,2008:167-189.HU Peng,YOU Lian,HU Hai.The Introduction of Map Algebra[M].Beijing:Surveying and Mapping Press,2008:167-189.
[22]胡海,杨传勇,胡鹏.自然图形间的中间线和比例线方法[J].海洋测绘,2009,29(5):15-18.HU Hai,YANG Chuanyong,HU Peng.Methods of Midline and Scale Line Between Nature Figures[J].Hydrographic Surveying and Charting,2009,29(5):15-18.
[23]胡海.自然图形k阶Voronoi图生成和应用[D].武汉:武汉大学,2007:1-120.HU Hai.Generation and Application of Natural Graph K-order Voronoi Diagram[D].Wuhan:Wuhan University,2007:1-120.
[24]胡鹏,杨传勇,胡海.障碍空间最短路径的地图代数解法[M].北京:测绘出版社,2007.HU Peng,YANG Chuanyong,HU Hai.Solution on ESPO Using Map Algebra[M].Beijing:Surveying and Mapping Press,2007.
[25]杨传勇,胡海,胡鹏,等.欧氏障碍空间的最短路径问题解法[J].武汉大学学报(信息科学版),2012,37(12):1495-1499.YANG Chuanyong,HU Hai,HU Peng,et al.Solution of Euclidean Shortest Path Problem Space with Obstacles[J].Geomatics and Information Science of Wuhan University,2012,37(12):1495-1499.
[26]HU Hai,LIU Xiaohang,HU Peng.Voronoi Diagram Generation on the Ellipsoidal Earth[J].Computers&Geosciences,2014,73:81-87.