自顶向下聚集型代数多重网格预条件的边权选择

计算机工程与科学

自顶向下聚集型代数多重网格预条件的边权选择

吴建平，银福康，彭军，杨锦辉

（国防科技大学气象海洋学院,湖南长沙 410073）

收稿日期:2017-09-17 修回日期:2018-05-29 出版日期:2019-02-25 发布日期:2019-02-25
基金资助:
国家自然科学基金（61379022）

Edge weight selection of the aggregation-type

algebraic multigrid preconditioner from top to bottom

WU Jianping,YIN Fukang,PENG Jun,YANG Jinhui

（School of Meteorology and Oceanography,National University of Defense Technology,Changsha 410073,China）

Received:2017-09-17 Revised:2018-05-29 Online:2019-02-25 Published:2019-02-25

摘要/Abstract

摘要：

针对基于图划分的自顶向下聚集型代数多重网格预条件，考察了利用METIS软件包进行多重网格构建的方法，并就该软件包只能处理整型权重，不能处理实型权重的问题，提出了一种将实型边权转化为整型边权的有效方法。之后将这种转化方法应用到METIS图划分软件中的边权选择，并用其给出了对自顶向下聚集型代数多重网格预条件的一种改进算法。通过对二维与三维模型偏微分方程离散所得稀疏线性方程组的数值实验表明，带边权的改进型算法大大提高了多重网格预条件共轭斜量法的迭代效率，特别是对各向异性问题，改进效果更加显著。

关键词: 稀疏线性方程组, 聚集型代数多重网格, 预条件, 共轭斜量法, 图划分

Abstract:

Aiming at the top-bottom aggregation-type multigrid preconditioner from top to bottom based on graph partitioning, we investigate the multigrid construction method using METIS software package. Given that software package METIS can only process integer weights but not float-type weights, we propose an effective scheme to convert float-type edge weights to integer edge weights. Then it is used to select edge weights in the METIS graph partitioning software, and we propose an improved algorithm for aggregation-type multigrid preconditioner from top to bottom. Numerical experiments on the solution to the sparse linear system derived from two-dimensional and three-dimensional model partial differential equations show that the improved method with edge weights can greatly improve the iterative efficiency of the multigrid preconditioned conjugate-gradient method, and the improvement for anisotropic problems are especially significant.

Key words: sparse linear equation group, aggregation-type algebraic multigrid, preconditioner, conjugate gradient method, graph partitioning

吴建平，银福康，彭军，杨锦辉. 自顶向下聚集型代数多重网格预条件的边权选择[J]. 计算机工程与科学.

WU Jianping,YIN Fukang,PENG Jun,YANG Jinhui.

Edge weight selection of the aggregation-type

algebraic multigrid preconditioner from top to bottom

[J]. Computer Engineering & Science.

[1]	罗晓霞, 王佳, 罗香玉, 李嘉楠 . 一种基于GN算法的动态图划分方法[J]. 计算机工程与科学, 2022, 44(02): 306-311.
[2]	黄乐乐1，马慧芳1,2，李宁3，余丽1. 基于二分图划分联合聚类的协同过滤推荐算法[J]. 计算机工程与科学, 2019, 41(11): 2040-2047.
[3]	蔡兆克，鲍亮，徐冬梅. 预条件的平方Smith法求解大型Sylvester矩阵方程[J]. 计算机工程与科学, 2017, 39(08): 1425-1430.
[4]	张晓，王红. 一种改进的基于大数据集的混合聚类算法[J]. J4, 2015, 37(09): 1621-1626.
[5]	陈海亮，雷琳，周石琳. 一种基于空间规则度的谱图划分提取舰船编队方法[J]. J4, 2012, 34(5): 116-120.
[6]	骆志刚,仲妍,吴枫. 稀疏线性方程组求解中的预处理技术综述[J]. J4, 2010, 32(12): 89-93.
[7]	李晓梅[1] 吴建平[2]. 稀疏线性方程组不完全分解预条件方法[J]. J4, 2006, 28(8): 59-62.