一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

doi:10.11896／j.issn.1002-137X.2018.07.051

计算机科学 ›› 2018, Vol. 45 ›› Issue (7): 299-306.doi: 10.11896／j.issn.1002-137X.2018.07.051

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

程东升^1,2,刘志勇³,薛国伟¹,高月芳¹

深圳信息职业技术学院软件学院广东深圳 518172¹;
中山大学广东省科学重点实验室广州 510275²;
深圳职业技术学院工业中心广东深圳 518055³

收稿日期:2017-05-18 出版日期:2018-07-30 发布日期:2018-07-30
作者简介:程东升(1983－),男,博士,副教授,主要研究方向为偏微分方程数值解、并行计算、图像处理、大数据应用技术,E-mail:chengds@sziit.edu.cn;刘志勇(1975－),男,博士,副教授,主要研究方向为模式识别、计算机视觉,E-mail:liuzhiyong@szpt.edu.cn(通信作者);薛国伟(1982－),男,博士,高级工程师,主要研究方向为并行计算、图像处理;高月芳(1979－),女,博士,副教授,主要研究方向为智能控制。
基金资助:
本文受国家自然科学基金项目(11701389),广东省自然科学基金项目(2015A030313592),中山大学广东省计算科学重点实验室,深圳市科技计划项目(JCYJ20160527102119211,JCYJ20150630114140642),广东省优秀青年教师项目(YQ2014122),深圳信息职业技术学院科研培育项目(QN201710)资助。

High-performance Parallel Preconditioned Iterative Solver for Helmholtz Equation with Large Wavenumbers

CHENG Dong-sheng^1,2,LIU Zhi-yong³,XUE Guo-wei¹,GAO Yue-fang¹

Department of Software Engineering,Shenzhen Institute of Information and Technology,Shenzhen,Guangdong 518172,China¹;
Guangdong Province Key Laboratory of Computational Science,Sun Yat-sen University,Guangzhou 510275,China²;
Industrial Center,Shenzhen Polytechnic,Shenzhen,Guangdong 518055,China³

Received:2017-05-18 Online:2018-07-30 Published:2018-07-30

摘要/Abstract

摘要： 针对传统串行迭代法求解大波数Helmholtz方程存在效率低下且受限于单机内存的问题,提出了一种基于消息传递接口(Message Passing Interface,MPI) 的并行预条件迭代法。该算法利用复移位拉普拉斯算子对Helmholtz方程进行预条件处理,联合稳定双共轭梯度法和基于矩阵的多重网格法来求解预条件方程离散后的大规模线性系统,在Linux集群系统上基于 MPI环境实现了求解算法的并行计算,重点解决了多重网格的并行划分、信息传递和多重网格组件的构建问题。数值实验表明,对于大波数问题,提出的算法具有良好的并行加速比,相较于串行算法极大地提高了计算效率。

关键词: Helmholtz方程, 并行, 多重网格, 稳定双共轭梯度法, 预条件子

Abstract: For solving the Helmholtz equation with a large wavenumber,the traditional sequential iterative solver is inefficient and limited to the memory of a single computer.To deal with these problems,a parallel preconditioned iterative solver was proposed based on the message passing interface(MPI).The complex shifted-Laplacian is used to precondition the Helmholtz equation,and the Krylov subspace method Bi-CGSTAB combined with the matrix-based multigrid method is employed to solve the large linear system resulted from discretization of the preconditioned equation.Paral-lelization of the preconditioned solver is achieved under the environment of MPI on the Linux cluster system,and the problems of parallel partition of the multigrid,information transfer and construction of the multigrid components are mainly tackled.Finally,numerical experiments were given.The results show that the proposed method contributes to an excellent parallel speedup,and improves the computing efficiency considerably compared with the sequential iterative solver.

Key words: Bi-CGSTAB, Helmholtz equation, Multigrid, Parallel, Preconditioner

中图分类号:

O246

程东升,刘志勇,薛国伟,高月芳. 一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法[J]. 计算机科学, 2018, 45(7): 299-306. https://doi.org/10.11896／j.issn.1002-137X.2018.07.051

CHENG Dong-sheng,LIU Zhi-yong,XUE Guo-wei,GAO Yue-fang. High-performance Parallel Preconditioned Iterative Solver for Helmholtz Equation with Large Wavenumbers[J]. Computer Science, 2018, 45(7): 299-306. https://doi.org/10.11896／j.issn.1002-137X.2018.07.051

参考文献

[1]IHLENBURG F,BABUKA I.Finite Element Solution of the Helmholtz Equation with High Wave Number,Part I:The h-version of the FEM[J].Compute & Mathematics with Applications,1995,30(9):9-37.
[2]ERLANGGA Y,OOSTERLEE C,VUIK C.A Novel Multigrid Based Preconditioner for Heterogeneous Helmholtz Problem[J].SIAM Journal on Scientific Computing,2006,27(4):1471-1492.
[3]CHENG D S,LIU Z Y,WU T T.A Multigrid Based Preconditioned Solver for the Helmholtz Equation with a Discretization By 25-point Difference Scheme[J].Mathematics and Computers in Simulation,2015,117(11):54-67.
[4]KE R H,LI W.Numerical Method for the Two-dimensionalHelmholtz Equation Discretized By CCD Scheme[J].Journal on Numerical Method and Computer Application,2013,34(3):221-230.(in Chinese)
柯日焕,黎稳.用CCD法离散求解二维Helmholtz方程的数值方法[J].数值计算与计算机应用,2013,34(3):221-230.
[5]CAO J,CHEN J B,CAO S H.Studies on Iterative Algorithms for Modeling of Frequency-domain Wave Equation Based on Multi-grid Precondition[J].Chinese Journal of Geophysics,2015,58(3):1002-1012.(in Chinese)
曹健,陈景波,曹书红.频率域波动方程正演基于多重网格预条件的迭代算法研究[J].地球物理学报,2015,58(3):1002-1012.
[6]张林波,迟学斌,莫则尧,等.并行计算导论[M].北京:清华大学出版社,2006:1-520.
[7]COOK S.CUDA Programming:A Developer’s Guide to Parallel Computing with GPUs[M].San Francisco:Morgan Kaufmann publishers inc,2012:1-600.
[8]RIYANTI C D,KONONOV A,ERLANGGA Y A,et al.A pa-rallel multigrid-based preconditioner for the 3D heterogeneous high-frequency Helmholtz equation[J].Journal of Computatio-nal Physics,2007,224(1):431-448.
[9]ZHANG L L,GONG X P,SONG J Q.Parallel Preconditioned GMRES Solvers for 3-D Helmholtz Equations in Regional Non-hydrostatic Atmosphere Model[C]∥International Conference on Computer Science and Software Engineering.Washington,DC:IEEE Computer Society,2008:287-290.
[10]KNIBBE H,OOSTERLEE C W,VUIK C.GPU implementation of a Helmholtz Krylov solver preconditioned by a shifted Laplace multigrid method[J].Journal of Computational and Applied Mathematics,2011,236(3):281-293.
[11]LENG W.A Fast Propagation Method for the Helmholtz Equation[J].Chinese Journal of Engineering Mathematics,2015,32(5):726-742.
[12]CHEN Z Y,CHENG D S,WU T T.An Optimal 9-point Finite Difference Scheme for the Helmholtz Equation with PML[J].International Journal of Numerical Analysis and Modeling,2013,10(2):389-410.
[13]LI X M,WU J P.Krylov Subapce Methods and Parallel Computation[J].Computer Science,2005,32(1):19-20.(in Chinese)
李晓梅,吴建平.Krylov子空间方法及其并行计算[J].计算机科学,2005,32(1):19-20.
[14]BRIGGS W L,HENSON V E,MCCORMICKS F.A Multigrid Tutorial[M].California:SIAM,2000:1-192.
[15]BRENGER J P.A Perfectly Matched Layer for the Absorption of Electromagnetic Waves[J].Journal of Computational Phy-sics,1994,114(2):185-200.
[16]GORDON D,GORDON R.Robust and highly scalable parallel solution of the Helmholtz equation with large wave numbers[J].Journal of Computational & Applied Mathematics,2013,237(1):182-196.

相关文章 15

[1]	王子凯, 朱健, 张伯钧, 胡凯. 区块链与智能合约并行方法研究与实现 Research and Implementation of Parallel Method in Blockchain and Smart Contract 计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102
[2]	魏恺轩, 付莹. 基于重参数化多尺度融合网络的高效极暗光原始图像降噪 Re-parameterized Multi-scale Fusion Network for Efficient Extreme Low-light Raw Denoising 计算机科学, 2022, 49(8): 120-126. https://doi.org/10.11896/jsjkx.220200179
[3]	宗迪迪, 谢益武. 基于法线迭代的模型中轴生成方法 Model Medial Axis Generation Method Based on Normal Iteration 计算机科学, 2022, 49(6A): 764-770. https://doi.org/10.11896/jsjkx.210400050
[4]	陈鑫, 李芳, 丁海昕, 孙唯哲, 刘鑫, 陈德训, 叶跃进, 何香. 面向国产异构众核架构的CFD非结构网格计算并行优化方法 Parallel Optimization Method of Unstructured-grid Computing in CFD for DomesticHeterogeneous Many-core Architecture 计算机科学, 2022, 49(6): 99-107. https://doi.org/10.11896/jsjkx.210400157
[5]	刘江, 刘文博, 张矩. OpenFoam中多面体网格生成的MPI＋OpenMP混合并行方法 Hybrid MPI+OpenMP Parallel Method on Polyhedral Grid Generation in OpenFoam 计算机科学, 2022, 49(3): 3-10. https://doi.org/10.11896/jsjkx.210700060
[6]	李家振, 纪庆革. 动态低采样环境光遮蔽的实时光线追踪分子渲染 Dynamic Low-sampling Ambient Occlusion Real-time Ray Tracing for Molecular Rendering 计算机科学, 2022, 49(1): 175-180. https://doi.org/10.11896/jsjkx.210200042
[7]	傅天豪, 田鸿运, 金煜阳, 杨章, 翟季冬, 武林平, 徐小文. 一种面向构件化并行应用程序的性能骨架分析方法 Performance Skeleton Analysis Method Towards Component-based Parallel Applications 计算机科学, 2021, 48(6): 1-9. https://doi.org/10.11896/jsjkx.201200115
[8]	何亚茹, 庞建民, 徐金龙, 朱雨, 陶小涵. 基于神威平台的Floyd并行算法的实现和优化 Implementation and Optimization of Floyd Parallel Algorithm Based on Sunway Platform 计算机科学, 2021, 48(6): 34-40. https://doi.org/10.11896/jsjkx.201100051
[9]	季琰, 戴华, 姜莹莹, 杨庚, 易训. 面向混合云的可并行多关键词Top-k密文检索技术 Parallel Multi-keyword Top-k Search Scheme over Encrypted Data in Hybrid Clouds 计算机科学, 2021, 48(5): 320-327. https://doi.org/10.11896/jsjkx.200300160
[10]	冯凯, 马鑫玉. (n,k)-冒泡排序网络的子网络可靠性 Subnetwork Reliability of (n,k)-bubble-sort Networks 计算机科学, 2021, 48(4): 43-48. https://doi.org/10.11896/jsjkx.201100139
[11]	李繁, 严星, 张晓宇. 基于GPU的特征脸算法优化研究 Optimization of GPU-based Eigenface Algorithm 计算机科学, 2021, 48(4): 197-204. https://doi.org/10.11896/jsjkx.200600033
[12]	陈自民, 卢艺文, 郭燕. 基于区块并行的以太坊智能合约高速重放 High-speed Replay of Ethereum Smart Contracts Based on Block Parallel 计算机科学, 2021, 48(2): 289-294. https://doi.org/10.11896/jsjkx.200500105
[13]	胡蓉, 阳王东, 王昊天, 罗辉章, 李肯立. 基于GPU加速的并行WMD算法 Parallel WMD Algorithm Based on GPU Acceleration 计算机科学, 2021, 48(12): 24-28. https://doi.org/10.11896/jsjkx.210600213
[14]	马梦宇, 吴烨, 陈荦, 伍江江, 李军, 景宁. 显示导向型的大规模地理矢量实时可视化技术 Display-oriented Data Visualization Technique for Large-scale Geographic Vector Data 计算机科学, 2020, 47(9): 117-122. https://doi.org/10.11896/jsjkx.190800121
[15]	陈国良, 张玉杰. 并行计算学科发展历程 Development of Parallel Computing Subject 计算机科学, 2020, 47(8): 1-4. https://doi.org/10.11896/jsjkx.200600027

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

High-performance Parallel Preconditioned Iterative Solver for Helmholtz Equation with Large Wavenumbers

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0