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

近年来，受实际应用领域中大规模科学计算问题的驱动，在大规模并行机上实现代数多重网格（AMG）算法成为数值计算领域的研究热点。本文针对经典AMG方法，提出一种新的并行网格粗化算法一多阶段并行RS算法（MPRS）。我们将新算法集成到了高性能预条件子软件包Hypre中。大量数值实验结果显示，新算法适合更广泛的问题，相对其他并行粗化算法，明显地改善了AMG并行计算的可扩展性。对三维27点格式有限差分离散的Poisson方程，在64个处理机上并行AMG求解，含8百万个未知量，新算法比RS3算法减少了近60的三维Poisson方程，近32万个未知量，在16个处理机上并行AMG—GMRES求解，新算法所需的迭代步数大约为其他粗化算法的一半，显示了很好的算法可扩展性。

A NEW GRID-COARSENING ALGORITHM FOR PARALLEL ALGEBRAIC MULTIGRID METHOD

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.