Computer Science ›› 2018, Vol. 45 ›› Issue (7): 299-306.doi: 10.11896/j.issn.1002-137X.2018.07.051

• Interdiscipline & Frontier • Previous Articles     Next Articles

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

CHENG Dong-sheng1,2,LIU Zhi-yong3,XUE Guo-wei1,GAO Yue-fang1   

  1. Department of Software Engineering,Shenzhen Institute of Information and Technology,Shenzhen,Guangdong 518172,China1;
    Guangdong Province Key Laboratory of Computational Science,Sun Yat-sen University,Guangzhou 510275,China2;
    Industrial Center,Shenzhen Polytechnic,Shenzhen,Guangdong 518055,China3
  • Received:2017-05-18 Online:2018-07-30 Published:2018-07-30

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: Helmholtz equation, Parallel, Preconditioner, Bi-CGSTAB, Multigrid

CLC Number: 

  • O246
[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.
[1] MA Meng-yu, WU Ye, CHEN Luo, WU Jiang-jiang, LI Jun, JING Ning. Display-oriented Data Visualization Technique for Large-scale Geographic Vector Data [J]. Computer Science, 2020, 47(9): 117-122.
[2] CHEN Guo-liang, ZHANG Yu-jie, . Development of Parallel Computing Subject [J]. Computer Science, 2020, 47(8): 1-4.
[3] YANG Wang-dong, WANG Hao-tian, ZHANG Yu-feng, LIN Sheng-le, CAI Qin-yun. Survey of Heterogeneous Hybrid Parallel Computing [J]. Computer Science, 2020, 47(8): 5-16.
[4] GUO Jie, GAO Xi-ran, CHEN Li, FU You, LIU Ying. Parallelizing Multigrid Application Using Data-driven Programming Model [J]. Computer Science, 2020, 47(8): 32-40.
[5] LI Yu-rong, LIU Jie, LIU Ya-lin, GONG Chun-ye, WANG Yong. Parallel Algorithm of Deep Transductive Non-negative Matrix Factorization for Speech Separation [J]. Computer Science, 2020, 47(8): 49-55.
[6] CHENG Sheng-gan, YU Hao-ran, WEI Jian-wen, James LIN. Design and Optimization of Two-level Particle-mesh Algorithm Based on Fixed-point Compression [J]. Computer Science, 2020, 47(8): 56-61.
[7] ZHUANG Yuan, GUO Qiang, ZHANG Jie, ZENG Yun-hui. Large Scalability Method of 2D Computation on Shenwei Many-core [J]. Computer Science, 2020, 47(8): 87-92.
[8] WANG Liang, ZHOU Xin-zhi, YNA Hua. Real-time SIFT Algorithm Based on GPU [J]. Computer Science, 2020, 47(8): 105-111.
[9] FENG Kai, LI Jing. Study on Subnetwork Reliability of k-ary n-cubes [J]. Computer Science, 2020, 47(7): 31-36.
[10] LV Xiao-jing, LIU Zhao, CHU Xue-sen, SHI Shu-peng, MENG Hong-song, HUANG Zhen-chun. Extreme-scale Simulation Based LBM Computing Fluid Dynamics Simulations [J]. Computer Science, 2020, 47(4): 13-17.
[11] ZUO Xian-yu, ZHANG Zhe, SU Yue-han, LIU Yang, GE Qiang, TIAN Jun-feng. Extraction Algorithm of NDVI Based on GPU Multi-stream Parallel Model [J]. Computer Science, 2020, 47(4): 25-29.
[12] YANG Zong-lin, LI Tian-rui, LIU Sheng-jiu, YIN Cheng-feng, JIA Zhen, ZHU Jie. Streaming Parallel Text Proofreading Based on Spark Streaming [J]. Computer Science, 2020, 47(4): 36-41.
[13] DONG Hail, XU Xiao- peng, XIE Xie. Solving Multi-flexible Job-shop Scheduling by Multi-objective Algorithm [J]. Computer Science, 2020, 47(12): 239-244.
[14] ZHOU Wen-xiang, QIAO Xue-gong. Anycast Routing Algorithm for Wireless Sensor Networks Based on Energy Optimization [J]. Computer Science, 2020, 47(12): 291-295.
[15] DENG Ding-sheng. Application of Improved DBSCAN Algorithm on Spark Platform [J]. Computer Science, 2020, 47(11A): 425-429.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .