并行代数多重网格算法可扩展性能分析

对当今求解大型稀疏线性代数方程组最有效的迭代方法之一——代数多重网格(AMG)算法的并行计算进行可扩展性能分析.给出一套并行计算可扩展性能分析方法,用于分析和指导并行迭代算法及实现技术的设计与优化并应用于并行AMG算法.分析表明,网格算子的平均模式大小和迭代过程的算法效率分别制约了AMG算法启动阶段和迭代求解阶段并行性能的发挥,成为该类算法急需解决的两个关键问题.

求解大规模稀疏线性代数方程组序列的自适应AMG预条件策略

时间相关偏微分方程隐式离散后,通常需要求解一个稀疏线性代数方程组序列.利用序列中相邻方程组性质的差异性与相似性,自适应地选取预条件子,提升方程组序列的并行求解效率,从而缩短总体求解时间,是一个值得研究的问题.本文针对科学与工程计算中广泛使用的代数多重网格(AMG)预条件子,设计了方程组序列相关的自适应预条件策略.通过惯性约束聚变(ICF)的辐射流体力学数值模拟典型应用,验证了该策略的有效性.测试结果表明,在某高性能计算机的3125个CPU核上,自适应预条件策略可将并行效率从47%提升到61%,将模拟总时间从19.7 h降为14.5 h.

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

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

并行代数多重网格粗化算法的优化

近年来,随着日常生活等实际应用领域中大规模稀疏矩阵求解问题的推动,代数多重网格(AMG)算法及其并行化的研究成为了数值计算领域的热点。本文在原始AMG算法和MPRS算法的基础上,对现有的并行AMG算法提出了一种优化的动态阈值算法(DVRS)。在Visual Studio 2008环境下,数值计算实验结果表明,新算法适用于更广泛的领域,与原有的并行AMG算法相比,改善了AMG并行计算的可扩展性。