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

• 研究、探讨 • 上一篇    下一篇

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

吴建平1,张理论1,马怀发2,宋君强1,张卫民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. 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

摘要: 对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