自顶向下聚集型代数多重网格预条件的边权选择
|
摘要
针对基于图划分的自顶向下聚集型代数多重网格预条件,考察了利用METIS软件包进行多重网格构建的方法,并就该软件包只能处理整型权重,不能处理实型权重的问题,提出了一种将实型边权转化为整型边权的有效方法。之后将这种转化方法应用到METIS图划分软件中的边权选择,并用其给出了对自顶向下聚集型代数多重网格预条件的一种改进算法。通过对二维与三维模型偏微分方程离散所得稀疏线性方程组的数值实验表明,带边权的改进型算法大大提高了多重网格预条件共轭斜量法的迭代效率,特别是对各向异性问题,改进效果更加显著。
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.
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.
引文
[1] Saad Y.Iterative methods for sparse linear systems[M].Boston:PWS Pub Co,1996.
[2] Wu Jian-ping,Wang Zheng-hua,Li Xiao-mei.Highly efficient solution and parallel computation for sparse linear systems [M].Changsha:Hunan Science and Technology Press,2004.(in Chinese)
[3] Wagner C. Introduction to algebraic multigrid[EB/OL].[2017-01-15].http://www.iwr.uni-heidelberg.de/Christian.Wagner/.
[4] Kim H,Xu J,Zikatanov L.A multigrid method based on graph matching for convection-diffusion equations[J].Numerical Linear Algebra With Applications,2003,10(1-2):181-195.
[5] Notay Y. Aggregation-based algebraic multigrid for convection-diffusion equations[J].SIAM Journal of Scientific Computing, 2012,34(4):A2288-A2316.
[6] Dendy J E, Moulton J D.Black box multigrid with coarsening by a factor of three[J].Numerical Linear Algebra With Applications,2010,17(2-3):577-598.
[7] Braess D.Towards algebraic multigrid for elliptic problems of second order[J].Computing,1995,55(4):379-393.
[8] Wu Jian-ping,Yin Fu-kang,Peng Jun,et al.Research on aggregations for algebraic multigrid preconditioning methods[C]//Proc of 2017 2nd International Conference on Computer Science and Technology,2017:39-48.
[9] Wu Jian-ping,Yin Fu-kang,Peng Jun,et al.An algebraic multigrid preconditioner based on aggregation from top to bottom[C]//Proc of the 4th Annual International Conference on Information Technology and Applications,2017:192-204.
[10] Karypis G,Kumar V.METIS—A software package for partitioning unstructured graphs,partitioning meshes,and computing fill-reducing orderings of sparse matrices-version 4.0[R].Minneapolis:University of Minnesota,1998.附中文参考文献:
[2] 吴建平,王正华,李晓梅.稀疏线性方程组的高效求解与并行计算[M].长沙:湖南科学技术出版社,2004.
[2] Wu Jian-ping,Wang Zheng-hua,Li Xiao-mei.Highly efficient solution and parallel computation for sparse linear systems [M].Changsha:Hunan Science and Technology Press,2004.(in Chinese)
[3] Wagner C. Introduction to algebraic multigrid[EB/OL].[2017-01-15].http://www.iwr.uni-heidelberg.de/Christian.Wagner/.
[4] Kim H,Xu J,Zikatanov L.A multigrid method based on graph matching for convection-diffusion equations[J].Numerical Linear Algebra With Applications,2003,10(1-2):181-195.
[5] Notay Y. Aggregation-based algebraic multigrid for convection-diffusion equations[J].SIAM Journal of Scientific Computing, 2012,34(4):A2288-A2316.
[6] Dendy J E, Moulton J D.Black box multigrid with coarsening by a factor of three[J].Numerical Linear Algebra With Applications,2010,17(2-3):577-598.
[7] Braess D.Towards algebraic multigrid for elliptic problems of second order[J].Computing,1995,55(4):379-393.
[8] Wu Jian-ping,Yin Fu-kang,Peng Jun,et al.Research on aggregations for algebraic multigrid preconditioning methods[C]//Proc of 2017 2nd International Conference on Computer Science and Technology,2017:39-48.
[9] Wu Jian-ping,Yin Fu-kang,Peng Jun,et al.An algebraic multigrid preconditioner based on aggregation from top to bottom[C]//Proc of the 4th Annual International Conference on Information Technology and Applications,2017:192-204.
[10] Karypis G,Kumar V.METIS—A software package for partitioning unstructured graphs,partitioning meshes,and computing fill-reducing orderings of sparse matrices-version 4.0[R].Minneapolis:University of Minnesota,1998.附中文参考文献:
[2] 吴建平,王正华,李晓梅.稀疏线性方程组的高效求解与并行计算[M].长沙:湖南科学技术出版社,2004.