一种新的并行代数多重网格粗化算法  

A NEW GRID-COARSENING ALGORITHM FOR PARALLEL ALGEBRAIC MULTIGRID METHOD

作　　者：徐小文[1] 莫则尧[2] 

机构地区：[1]中国工程物理研究院研究生部,北京100088 [2]北京应用物理与计算数学研究所高性能计算中心,北京100088

出　　处：《计算数学》2005年第3期325-336,共12页Mathematica Numerica Sinica

基　　金：国家杰出青年基金(60425205)中物院双百人才基金资助.

摘　　要：近年来,受实际应用领域中大规模科学计算问题的驱动,在大规模并行机上实现代数多重网格(AMG)算法成为数值计算领域的研究热点。本文针对经典AMG方法,提出一种新的并行网格粗化算法——多阶段并行RS算法(MPRS)。我们将新算法集成到了高性能预条件子软件包Hypre中。大量数值实验结果显示,新算法适合更广泛的问题,相对其他并行粗化算法,明显地改善了AMG并行计算的可扩展性。对三维27点格式有限差分离散的Poisson方程,在64个处理机上并行AMG求解,含8百万个未知量,新算法比RS3算法减少了近60的三维Poisson方程,近32万个未知量,在16个处理机上并行AMG-GMRES求解,新算法所需的迭代步数大约为其他粗化算法的一半,显示了很好的算法可扩展性。In recent years, the need to solve linear systems arising from problems posed on large scale, unstructured grids has sparked great interest in parallelizing algebraic multigrid （AMG）. In this paper, based on classical AMG method, we introduce a new parallel algorithm for selecting coarse-grid points, a crucial component of AMG. At the same time, we integrated this new algorithm into the Hypre, which is a high performance preconditioner package. Various numerical experiments based on Hypre are presented, and experimental results show that our method improves the algorithmic scalability of the parallel AMG computing remarkably. For the linear equations with 8 millions variables discretized from 3-D Poisson equation, comparing with RS3 coarsening algorithm, our method reduces the computing time by nearly 60% using 64 processors on one parallel computer. For unstructured grids problem with about 0.32 millions variables, the number of iterations of our method is about as half as that of RS3 algorithm using 16 processors on the same parallel computer.

关 键 词：代数多重网格(AMG) 并行计算 网格粗化 大规模并行机 代数多重网格 粗化算法 POISSON方程 可扩展性 GMRES 新算法 

分 类 号：O246[理学—计算数学]