排序对重叠区域分解型并行ILU的影响分析

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (33): 49-55.

排序对重叠区域分解型并行ILU的影响分析

吴建平1，张理论1，马怀发2，宋君强1，张卫民1

1.国防科技大学计算机学院，长沙 410073
2.中国水利水电科学研究院，北京 100044

出版日期:2012-11-21 发布日期:2012-11-20

Analyses of effects of sorting schemes to overlapped domain decomposition based parallel ILUs

WU Jianping1, ZHANG Lilun1, MA Huaifa2, SONG Junqiang1, ZHANG Weimin1

1.School of Computer Science, National University of Defense Technology, Changsha 410073, China
2.China Institute of Water Resources and Hydropower Research, Beijing 100044, China

Online:2012-11-21 Published:2012-11-20

摘要/Abstract

摘要： 对Krylov子空间迭代法，高效预条件的构造是核心问题之一，而重叠区域分解是一种很有效的并行化技术。通过模型偏微分方程离散求解以及混凝土细观数值模拟中的线性方程组求解，对商图，就自然排序、RCM排序、Sloan排序、GPS排序、谱排序和随机排序等多种重排算法进行了比较。对子区域内顶点的重排方案，进行了自然排序、RCM排序、谱排序、随机排序和一种新排序算法间的比较。结果表明，预条件效果对商图排序不敏感。局部排序对预条件质量具有明显影响，局部采用随机排序时效果一般较差，而带宽缩减算法对加性Schwarz影响很小，对块Jacobi并行化预条件影响较大，对因子组合型并行预条件采用自然排序和新排序时效果较好。

关键词: 并行计算, 稀疏线性方程组, 预条件, 不完全LU分解, 混凝土细观数值模拟

Abstract: For Krylov subspace iterations, the construction of highly efficient preconditioners is one of the key issues. The overlapped domain decomposition is an effective parallelization technique. Through the solution of the linear systems from model partial differential equations and meso-scale numerical simulation of concrete, several reordering schemes for the quotient graph, including natural, RCM, Sloan, GPS, spectral and random, are compared. For the nodes of each sub-domain, the reordering schemes, including natural, RCM, spectral, random and a new one, are compared. The results show that the quality of preconditioners is insensitive to the quotient graph reordering, and is significantly affected by local reordering. For local reordering, random scheme is worse in general, the bandwidth reduction scheme has no significant effects on the additive Schwarz but has on block Jacobi analog, while the natural and the new scheme are better for the factors combination based preconditioner.

Key words: parallel computing, sparse linear system, preconditioner, incomplete LU factorization, meso-scale numerical simulation of concrete

吴建平1，张理论1，马怀发2，宋君强1，张卫民1. 排序对重叠区域分解型并行ILU的影响分析[J]. 计算机工程与应用, 2012, 48(33): 49-55.

WU Jianping1, ZHANG Lilun1, MA Huaifa2, SONG Junqiang1, ZHANG Weimin1. Analyses of effects of sorting schemes to overlapped domain decomposition based parallel ILUs[J]. Computer Engineering and Applications, 2012, 48(33): 49-55.

[1]	冯凯，李婧. k元n方体网络的子网络可靠性[J]. 计算机工程与应用, 2021, 57(16): 83-89.
[2]	李健，张大伟，姜晓明，向立云. 并行化洪水演进模拟研究综述[J]. 计算机工程与应用, 2021, 57(13): 1-7.
[3]	孙明，陈昕. 面向卷积神经网络的硬件加速器设计方法[J]. 计算机工程与应用, 2021, 57(13): 77-84.
[4]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[5]	杜伟，傅游. 基于GPU的最小二乘蒙特卡罗算法期权定价[J]. 计算机工程与应用, 2020, 56(4): 225-229.
[6]	金之雁，杨磊，林隽民，王哲. 广义共轭余差法的通信避免算法[J]. 计算机工程与应用, 2020, 56(3): 74-79.
[7]	刘家华，陈靖宇. 多核并行脉冲神经网络模拟器的设计[J]. 计算机工程与应用, 2020, 56(22): 244-250.
[8]	邬阳阳，汤建国. 大数据背景下粗糙集属性约简研究进展[J]. 计算机工程与应用, 2019, 55(6): 31-38.
[9]	刘军，李威，吴梦婷，陈起凤. Hadoop平台下新型图像并行处理模型设计[J]. 计算机工程与应用, 2019, 55(6): 186-190.
[10]	刘洋，陈经纬，冯勇，吴文渊. 并行LLL算法研究综述[J]. 计算机工程与应用, 2019, 55(16): 36-41.
[11]	曾有灵，陈耿铎，熊威，李喆. 基于Spark的CT图像FBP重建算法程序并行设计[J]. 计算机工程与应用, 2019, 55(10): 218-224.
[12]	姜悦宁1，2，3，贾宏光1，3，厉明1，3. 基于多核并行计算的无人机CFD数值模拟[J]. 计算机工程与应用, 2018, 54(7): 221-225.
[13]	魏子衿1，2，3，肖丽2，3. 基于区域分解的并行动态LOD构建算法[J]. 计算机工程与应用, 2018, 54(6): 168-177.
[14]	袁冬芳，曹富军. 三维对流扩散方程的稀疏存储及预条件迭代[J]. 计算机工程与应用, 2018, 54(4): 56-59.
[15]	覃金帛1，曾志强1，2，梁藉1，杨明祥2，张健1. GPU并行优化技术在水利计算中的应用综述[J]. 计算机工程与应用, 2018, 54(3): 23-29.