一种基于正弦变换的三维泊松方程并行求解算法

计算机工程与科学

一种基于正弦变换的三维泊松方程并行求解算法

林士伟1,2,3，张卫民1,2，方民权1,2，李松1,2

（1.国防科技大学计算机学院,湖南长沙 410073;2.海军海洋水文气象中心，北京 100161；

3.国防科技大学海洋科学与工程研究院,湖南长沙 410073）

收稿日期:2017-01-11 修回日期:2017-03-26 出版日期:2017-08-25 发布日期:2017-08-25
基金资助:
国家自然科学基金（41375113）

A parallel 3D poisson equation solver

based on discrete sine transform

LIN Shi-wei1,2,3，ZHANG Wei-min1,2，FANG Min-quan1,2，LI Song1,2

（1.College of Computer,National University of Defense Technology,Changsha 410073;

2.Naval Hydrologic Meteorological Center,Beijing 100161;

3.Academy of Ocean Science and Engineering,National University of Defense Technology,Changsha 410073,China）

Received:2017-01-11 Revised:2017-03-26 Online:2017-08-25 Published:2017-08-25

摘要/Abstract

摘要：

泊松方程的数值解法在许多物理或者工程问题上得到广泛应用，但是由于大部分三维泊松方程的离散化格式不具有明显的并行性，实际中使用整体迭代的思想，这使得计算效率和稳定性受到了限制。摒弃了传统数值解法中整体迭代的思想，结合离散正弦变换理论（DST），基于27点四阶差分格式，将三维泊松方程求解算法在算法级进行修改和并行优化，把整个求解问题转化成多个独立的问题进行求解，稳定性和并行性能得到大幅提升。对于确定的离散化形式，可以使用同一套参数解决不同的泊松方程，大大提高了编程效率。基于共享存储并行模型实现了该算法，实验结果显示，对于给出的实例，新算法具有较好的加速效果，计算结果精度误差约为10e-5，在可接受范围内，并且计算精度随着维数的升高具有一定提升。

关键词: 三维泊松方程, 离散正弦变换, 并行, OpenMP

Abstract:

Poisson equations are widely applied in physical and engineering problems. Most of numerical methods for solving 3D Poisson equations have no remarkable parallelism, and use the global iteration methods which limit the computational efficiency and stability. We abandon the idea of global iteration and combine the discrete sine transform theory (DST) with 27-point four-order difference scheme to modify and parallelize the 3D Poisson equation solver at the algorithm level, which separates the whole problem to several smaller independent ones and greatly improves the stability and parallel performance. For a given discrete form, common parameters can be used to solve different Possion equations so that the programming efficiency is greatly improved. The algorithm is implemented on the basis of the shared memory parallel model. Experimental results show that for the given instance, the new algorithm has a good acceleration effect and the final error of the computing result is about 10e-5, within an acceptable rang. And the result accuracy gets improved with the increase of problem scale.

Key words: 3D poisson equation, discrete sine transform, parallel, OpenMP

林士伟1,2,3，张卫民1,2，方民权1,2，李松1,2. 一种基于正弦变换的三维泊松方程并行求解算法[J]. 计算机工程与科学.

LIN Shi-wei1,2,3，ZHANG Wei-min1,2，FANG Min-quan1,2，LI Song1,2.

A parallel 3D poisson equation solver

based on discrete sine transform

[J]. Computer Engineering & Science.

[1]	杨仕琦, 武优西, 耿萌, 李艳. 一次性条件下的三支序列模式挖掘[J]. 计算机工程与科学, 2024, 46(07): 1286-1295.
[2]	郭宸良, 阎少宏, 宗晨琪. 线云隐私攻击算法的并行加速研究[J]. 计算机工程与科学, 2024, 46(04): 615-625.
[3]	肖调杰, 周峰, 郑翾宇, 刘剑, 陈琳, 刘杰, 易明宽, 陈旭光, 龚春叶, 杨博, 甘新标, 李胜国, 左克, . 大规模三维频率域电磁积分方程法数值模拟[J]. 计算机工程与科学, 2023, 45(11): 1901-1910.
[4]	王继昌, 吕高锋, 刘忠沛, 杨翔瑞. 基于数据处理器的QUIC加密/解密卸载[J]. 计算机工程与科学, 2023, 45(11): 1960-1969.
[5]	吴超, 卫谦, 周俊伟, 李会民, 孙广中. 基于异构计算平台的背景噪声预处理并行算法[J]. 计算机工程与科学, 2023, 45(10): 1711-1719.
[6]	王鑫, 彭健. 基于HYB格式SpMV在新一代申威架构上的实现与优化[J]. 计算机工程与科学, 2023, 45(10): 1754-1762.
[7]	朱文龙, 江嘉治, 黄聃, 肖侬. ParM:基于国产处理器的异构并行编程模型[J]. 计算机工程与科学, 2023, 45(09): 1521-1531.
[8]	刘屹成, 刘晓燕, 严馨. 并行平衡级联支持向量机[J]. 计算机工程与科学, 2023, 45(07): 1170-1177.
[9]	孙国璋, 黄山, 艾力卡木·再比布拉, 徐浩桐, 段晓东, . 基于Flink的k-支配skyline体并行求解算法[J]. 计算机工程与科学, 2023, 45(01): 17-27.
[10]	管延霞, 刘逊韵, 刘运韬, 谢旻, 徐新海. 面向多智能体博弈的并行蒙特卡洛树搜索算法研究[J]. 计算机工程与科学, 2022, 44(12): 2128-2133.
[11]	臧照虎, 李晨, 王耀华, 陈小文, 郭阳. 面向众核系统的层次化栅栏同步机制[J]. 计算机工程与科学, 2022, 44(11): 1901-1908.
[12]	张勇, 张曦, 万云博, 何先耀, 赵钟, 卢宇彤. 非结构有限体积CFD计算的网格重排序优化[J]. 计算机工程与科学, 2022, 44(10): 1721-1729.
[13]	葛旭冉, 刘洋, 陈志广, 肖侬. 基于MPI的并行大数据集生成器[J]. 计算机工程与科学, 2022, 44(07): 1152-1161.
[14]	陈奉贤. 基于NR-Transformer的集群作业运行时间预测[J]. 计算机工程与科学, 2022, 44(07): 1181-1190.
[15]	许晓阳, 王斯棋. 基于粒子分解的SPH并行算法研究与应用[J]. 计算机工程与科学, 2022, 44(06): 964-970.