基于Delaunay三角网的克里金并行算法优化
作者:

Optimization of Kriging Parallel Algorithm Based on Delaunay Triangulation Network
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [17]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    当采样点数据量较大时, 可以采用Delaunay三角剖分建立三角网来使用局部邻域采样点进行克里金插值. 但是该算法需要对每个插值点拟合半变异函数, 插值点规模大时造成巨大开销. 为此, 本文提出了一种以三角形为单位拟合半变异函数的克里金插值方法, 采用CPU-GPU负载均衡将部分计算优化, 充分考虑不均匀样本对克里金插值效果的影响. 结果表明, 本文算法能够保证不均匀样本集的插值效果, 提升了计算性能且能够保证较高的精度.

    Abstract:

    Under a large data amount of sampling points, Delaunay triangulation can be adopted to establish a triangulation network and then employ local neighborhood sampling points for Kriging interpolation. However, this algorithm requires fitting a semi-variogram to each interpolation point, which incurs significant overhead in the condition of a large interpolation point scale. Therefore, this study proposes a Kriging interpolation method that fits the semi-variogram on a triangular basis. Additionally, it utilizes CPU-GPU load balancing to optimize some calculations and fully considers the influence of non-uniform samples on the Kriging interpolation effect. The results show that the proposed algorithm can ensure the interpolation effect of non-uniform sample sets, improve computational performance, and ensure high accuracy.

    参考文献
    [1] 王倩. 基于Delaunay的三维快速克里金插值[硕士学位论文]. 成都: 电子科技大学, 2015.
    [2] 吴博, 高超, 谢健. 基于混合并行的Kriging插值算法研究. 计算技术与自动化, 2014, 33(1): 65–68.
    [3] Zhang YH, Zheng XQ, Wang ZH, et al. Implementation of a parallel GPU-based space-time Kriging framework. ISPRS International Journal of Geo-information, 2018, 7(5): 193.
    [4] 刘义. 基于GPU的三维克里金插值算法研究与开发[硕士学位论文]. 成都: 电子科技大学, 2021.
    [5] Pesquer L, Cortés A, Pons X. Parallel ordinary Kriging interpolation incorporating automatic variogram fitting. Computers & Geosciences, 2011, 37(4): 464–473.
    [6] 孙立双, 王恩德, 王井利, 等. 基于空间分布权系数Kriging邻域选点算法. 沈阳建筑大学学报(自然科学版), 2007, 23(3): 423–426.
    [7] Bargaoui ZK, Chebbi A. Comparison of two Kriging interpolation methods applied to spatiotemporal rainfall. Journal of Hydrology, 2009, 365(1–2): 56–73.
    [8] Cressie N, Johannesson G. Fixed rank Kriging for very large spatial data sets. Journal of the Royal Statistical Society: Series B: Statistical Methodology, 2008, 70(1): 209–226.
    [9] Muhamad Ali MZ, Othman F. Selection of variogram model for spatial rainfall mapping using analytical hierarchy procedure (AHP). Scientia Iranica, 2017, 24(1): 28–39.
    [10] 杜宇健, 萧德云. Delaunay-固定距离滑动邻域Kriging算法. 工程图学学报, 2005, 26(2): 64–68.
    [11] 王金鑫, 秦子龙, 曹泽宁, 等. 基于八叉树的修正克里金空间插值算法. 郑州大学学报(工学版), 2021, 42(6): 21–27.
    [12] Wan LJ, Li KL, Liu J, et al. Efficient CPU-GPU cooperative computing for solving the subset-sum problem. Concurrency and Computation: Practice and Experience, 2016, 28(2): 492–516.
    [13] 姜春雷, 张树清. CPU-GPU协同加速Kriging插值的负载均衡方法. 国防科技大学学报, 2015, 37(5): 35–39, 148.
    [14] 卢风顺, 宋君强, 银福康, 等. CPU/GPU协同并行计算研究综述. 计算机科学, 2011, 38(3): 5–9, 46.
    [15] Coll N, Guerrieri M. Parallel constrained delaunay triangulation on the GPU. International Journal of Geographical Information Science, 2017, 31(7): 1467–1484.
    [16] Zhai ZM, Li HY, Wang XG. An adaptive sampling method for Kriging surrogate model with multiple outputs. Engineering with Computers, 2022, 38(1): 277–295.
    [17] Bowyer A. Computing Dirichlet tesselations. Computer Journal, 1981, 24: 162–166.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

陈国军,李子祥,付云鹏,李震烁.基于Delaunay三角网的克里金并行算法优化.计算机系统应用,2024,33(1):213-218

复制
分享
文章指标
  • 点击次数:475
  • 下载次数: 1415
  • HTML阅读次数: 903
  • 引用次数: 0
历史
  • 收稿日期:2023-06-23
  • 最后修改日期:2023-08-08
  • 在线发布日期: 2023-11-17
  • 出版日期: 2023-01-05
文章二维码
您是第11208960位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号